¿Arreglo eficiente de Python con 100 millones de ceros?

Question

¿Cuál es una forma eficiente de inicializar y acceder a los elementos de una gran matriz en Python?

Quiero crear una matriz en Python con 100 millones de entradas, enteros sin signo de 4 bytes, inicializados a cero. Quiero acceso rápido a la matriz, preferiblemente con memoria contigua.

Extrañamente, NumPy las matrices parecen estar funcionando muy lento. ¿Hay alternativas que pueda probar?

Existe el módulo array.array, pero no veo un método para asignar eficientemente un bloque de 100 millones de entradas.

Respuestas a los comentarios:

• no pueden utilizar una matriz dispersa. Será demasiado lento para este algoritmo porque la matriz se vuelve muy rápida.
• Sé que se interpreta Python, pero seguramente hay una manera de hacer operaciones rápidas de matriz?
• Hice algunos perfiles, y obtengo unos 160K accesos a la matriz (buscando o actualizando un elemento por índice) por segundo con NumPy. Esto parece muy lento.

Answer 1

He hecho algunos perfiles, y los resultados son completamente contradictorios. Para operaciones simples de acceso a la matriz, numpy y array.array son 10 veces más lentos que las matrices nativas de Python.

Tenga en cuenta que para el acceso a la matriz, que estoy haciendo las operaciones de la forma:

a[i] += 1 

Perfiles:

• [0] * 20000000

  • acceso: 2,3 M/seg
  • Inicialización: 0.8s

• numpy.zeros (forma = (20000000,), dtype = numpy.int32)

  • acceso: 160K/seg
  • Inicialización: 0.2s

• matriz. array ('L', [0] * 20000000)

  • acceso: 175K/seg
  • Inicialización: 2.0s

• array.array ('L', (0 para i en el rango de (20000000)))

  • acceso: 175K/seg, presumiblemente, basado en el perfil para Por otra array.array
  • inicialización: 6.7s

Answer 2

Prueba esto:

x = [0] * 100000000 

Se tarda sólo unos segundos para ejecutar en mi máquina, y el acceso está cerca de instantánea.

Answer 3

Es poco probable que encuentre algo más rápido que numpy 's array. La implementación de la matriz en sí es tan eficiente como lo sería en, por ejemplo, C (y básicamente lo mismo que array.array, solo con más utilidad).

Si desea acelerar su código, tendrá que hazlo haciendo exactamente eso. Aunque la matriz se implementa de manera eficiente, acceder a ella desde el código de Python tiene cierta sobrecarga; por ejemplo, la indexación de la matriz produce objetos enteros, que deben crearse sobre la marcha. numpy ofrece una cantidad de operaciones implementadas de manera eficiente en C, pero sin ver el código real que no funciona tan bien como desea, es difícil hacer sugerencias específicas.

Answer 4

Además de las otras excelentes soluciones, otra forma es usar un dict en lugar de una matriz (los elementos que existen son distintos de cero, de lo contrario son cero). El tiempo de búsqueda es O (1).

También puede verificar si su aplicación reside en la memoria RAM, en lugar de cambiarla. Solo tiene 381 MB, pero es posible que el sistema no te lo esté proporcionando por ningún motivo.

Sin embargo también hay algunas matrices dispersas muy rápido (SciPy y ndsparse). Se realizan en C de bajo nivel y también pueden ser buenos.

Answer 5

NumPy es la herramienta adecuada para una matriz grande, de tamaño fijo y homogénea. El acceso a elementos individuales de cualquier cosa en Python no va a ser tan rápido, aunque las operaciones de conjunto completo a menudo se pueden llevar a cabo a velocidades similares a C o Fortran. Si necesita realizar operaciones en millones y millones de elementos individualmente rápidamente, solo puede salir de Python.

¿Qué tipo de algoritmo está implementando? ¿Cómo sabes que usar arrays dispersos es demasiado lento si no lo has probado?¿Qué quieres decir con "eficiente"? ¿Quieres una inicialización rápida? Ese es el cuello de botella de tu código?

Answer 6

para la creación rápida, utilice el módulo de matriz.

Con el módulo de matriz es ~ 5 veces más rápido para la creación, pero casi dos veces más lenta para el acceso a los elementos en comparación con una lista de lo normal:

# Create array 
python -m timeit -s "from array import array" "a = array('I', '\x00' 
* 100000000)" 
10 loops, best of 3: 204 msec per loop 

# Access array 
python -m timeit -s "from array import array; a = array('I', '\x00' 
* 100000000)" "a[4975563]" 
10000000 loops, best of 3: 0.0902 usec per loop 

# Create list 
python -m timeit "a = [0] * 100000000" 
10 loops, best of 3: 949 msec per loop 

# Access list 
python -m timeit -s "a = [0] * 100000000" "a[4975563]" 
10000000 loops, best of 3: 0.0417 usec per loop 

Answer 7

Sólo un recordatorio de cómo los números enteros de Python funcionan: si asigna una lista diciendo

a = [0] * K 

que necesita la memoria de la lista (sizeof(PyListObject) + K * sizeof(PyObject*)) y la memoria para el objeto entero simple 0. Siempre que los números en la lista permanezcan por debajo del número mágico V que Python usa para el almacenamiento en caché, está bien porque se comparten, es decir, cualquier nombre que apunte a un número n < V apunta exactamente al mismo objeto.Puede encontrar este valor mediante el siguiente fragmento:

>>> i = 0 
>>> j = 0 
>>> while i is j: 
... i += 1 
... j += 1 
>>> i # on my system! 
257 

Esto significa que tan pronto como los recuentos de ir por encima de este número, la memoria que necesita es sizeof(PyListObject) + K * sizeof(PyObject*) + d * sizeof(PyIntObject), donde d < K es el número de enteros por encima V (== 256). En un sistema de 64 bits, sizeof(PyIntObject) == 24 y sizeof(PyObject*) == 8, es decir, el peor consumo de memoria de los casos es 3,200,000,000 de bytes.

Con numpy.ndarray o array.array, el consumo de memoria es constante después de la inicialización, pero hay que pagar los objetos que los que se crean de forma transparente, como dijo Thomas Wouters. Probablemente, debe pensar en convertir el código de actualización (que accede y aumenta las posiciones en la matriz) al código C, ya sea usando Cython o scipy.weave.

Answer 8

Simplemente crearía su propio tipo de datos que no inicializa CUALQUIER valor.

Si desea leer una posición de índice que NO se ha inicializado, devuelve ceros. Aún así, no inicialice ningún almacenamiento.

Si desea leer una posición de índice que ha sido inicializada, simplemente devuelva el valor.

Si desea escribir en una posición de índice que NO se haya inicializado, inicialícela y almacénela.

Answer 9

Si no puede vectorizar sus cálculos, Python/Numpy será lento. Numpy es rápido porque los cálculos vectorizados ocurren en un nivel más bajo que Python. Las funciones básicas numpy están escritas en C o Fortran. Por lo tanto, sum(a) no es un ciclo de Python con muchos accesos, es una sola llamada de bajo nivel C.

Numpy's Performance Python demo page tiene un buen ejemplo con diferentes opciones. Puede aumentar 100 veces fácilmente utilizando un lenguaje compilado de nivel inferior, Cython, o utilizando funciones vectorizadas si es factible. This blog post que muestra un aumento de 43 veces usando Cython para un uso numpy.

Answer 10

Si la velocidad

• acceso de array.array es aceptable para su aplicación
• almacenamiento compacto es más importante
• desea utilizar módulos estándar (sin dependencia NumPy)
• usted está en plataformas que tienen/dev/zero

las siguientes pueden ser de su interés. Se inicializa array.array alrededor de 27 veces más rápido que array.array ('L', [0] * Tamaño):

myarray = array.array('L') 
f = open('/dev/zero', 'rb') 
myarray.fromfile(f, size) 
f.close() 

En How to initialise an integer array.array object with zeros in Python estoy en busca de una mejor manera.