[pyar] Crear una lista gigante

[Alejandro Santos]

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.

-- 
Alejandro Santos
http://www.alejolp.com.ar