[pyar] Crear una lista gigante

[Roberto Alsina]

On Sunday 06 June 2010 14:12:48 Alejandro Santos wrote:
> Roberto Alsina wrote:
> > On Saturday 05 June 2010 23:29:11 Alejandro Santos wrote:
> >> Jesús Francisco wrote:
> >>> ¿cómo es la forma más rápida en Python de crear una lista de N
> >>> 
> >>> elementos y todos inicializados en un valor x? Una forma es:
> >>> 
> >>> 
> >>> [x]*N
> >>> 
> >>> 
> >>> 
> >>> Pero me gustaría algo tan rápido como el calloc de C en el caso x==0.
> >>> Esto porque la versión que escribí es O(N) y si no me equivoco calloc
> >>> es O(1). No puedo usar numpy, solo la Biblioteca estándar de Python.
> >>> ¿es lo que escribí la forma más rápida?
> >> 
> >> Crear e inicializar un array o lista de N elemento siempre va a ser O(N)
> >> de una forma u otra. Capaz puedas bajar cuánto afectan las constantes
> >> pero... siempre vas a tener que procesar esos N elementos.
> > 
> > Hmmm.... no sé, che.
> > O sea, si cuando decimos una lista hablamos de list() sí, pero si hacés
> > una lista sparse con un valor default debería ser O(1) o estoy muy
> > dormido todavía?
> > 
> > Claro, no tengo una implementación de esa estructura a mano ;-)
> 
> No entendí lo de la lista sparse, yo tambien estoy muy dormido...
> 
> Que algo sea O(1) ú O(N) es muy subjetivo. Por ejemplo esto es O(N):
> 
> z = 0
> for x in xrange(N):
>     for a in xrange(1000000):
>         for b in xrange(1000000):
>             z += calcular_algo(x, a, b)
> 
> Los dos ciclos for de más adentro son constantes.

Una estructura de lista sparse es una que no te guarda todos los elementos 
sino solo aquellos que se inicializan, algo como esto: 
http://en.wikipedia.org/wiki/Sparse_matrix

Una implementacion pavota es basada un diccionario, algo como una cruza de un 
diccionario ordenado con un diccionario con valor default.

De hecho no sería siquiera necesario asignarle un tamaño, a menos que 
quisieras usar índices negativos o iterar sobre toda la lista.