[pyar] Crear una lista gigante

[Daniel Moisset]

2010/6/5 Jesús Francisco <jgomo3 en gmail.com>:
> ¿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?

No sé cual es la forma más rápida, pero tengo varios comentarios relevantes:

El primero, es que calloc no es O(1). En serio alguien tiene que
setear todos esos bytes a 0, y setear N bytes a 0 es... O(N).
Algunas bibliotecas de C, en sistemas basados en Unix(), implementan
calloc() de bloques grandes con un mmap de /dev/zero. Eso retorna en
O(1), aunque es hacer un poco de trampa... en realidad es O(N) pero
estas difiriendo la inicializacion al momento en que se usa la memoria
(es decir, cuando se producen page faults en las paginas no mapeadas)
en vez de al momento en que pedis alojarla.[1]

Lo segundo, es que no vas a conseguir alguna optimizacion en python
para x==0. Eso se debe a que  es muy distinto un array de int's de C
en 0 (que son esencialmente 32 o 64 o alguna cantidad de bits en 0,
todos puestos juntos) y que podes aprovechar muchos trucos de bajo
nivel para inicializar eso rapido (si te fijas en las implementaciones
usuales de memset o bzero). Una lista en python, por abajo es un
arreglo de punteros a objetos int(), que no son para nada una bosa
uniforme de bits en 0 (ni los punteros ni los objetos int). Por suerte
el objeto int() para el 0 se comparte, asi que en realidad ya va a
estar creado (sino tendrias N malloc()s+N inicializaciones de objeto),
pero igual hay que setear todos los punteros en la lista a la
direccion de int(0). y

Seguramente se podría hacer una extension en C que haga esto un poco
más rápido que [x]*N, sabiendo por ejemplo que el objeto 0 ya existe,
con algun truquito de bajo nivel para llenar un bafer con un patron de
4/8/sizeof(PyObject *) bytes, que se le pueden hacer todos los
incref() de un saque (capaz el * de listas ya se aviva de eso, no vi
la implementacion) y un par de suposiciones fuertes. Pero no creo que
sea _una barbaridad_ mas rapido.

Y lo que es seguro, no creo que vayas a conseguir que sea mas rapido
hacerlo con 0 que con None, o con 17, o con "Hola". Pero me encantaría
que me demuestren que me equivoque :)

Todo esto suponiendo que queres una lista de python. Si usaras numpy,
ahi podes tener un arreglo con ceros de verdad, donde podes
inicializar todo junto con algunas tecnicas mas piolas(depende de tu
micro, pero probablemente usando instrucciones vectoriales [2]

Saludos,

D.

[1] Por ejemplo, en
http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/stdlib/malloc.c?rev=1.48.8.2&content-type=text/x-cvsweb-markup
podes ver el fuente de calloc() que es un malloc() seguido de un
memset()
[2] pondría un link a fuente de memset, pero la mayoría de los
compiladores modernos si optimizas, reemplazan llamadas a memset(0)
con codigo especifico del target CPU, con lo caul es codigo fuente que
no calienta aca