¿Eficiente matriz de Python con 100 millones de ceros?

arrays performance

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 de 4 bytes sin signo, inicializados a cero. Quiero un acceso rápido a la matriz, preferiblemente con memoria contigua.

Curiosamente, las matrices NumPy parecen estar funcionando muy lentamente. ¿Hay alternativas que pueda probar?

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

Respuestas a los comentarios:

• No puedo usar una matriz dispersa. Será demasiado lento para este algoritmo porque la matriz se vuelve muy densa muy rápidamente.
• Sé que se interpreta Python, pero seguramente hay una manera de hacer operaciones de matriz rápidas.
• Realicé algunos perfiles y obtuve alrededor de 160K accesos de matriz (buscando o actualizando un elemento por índice) por segundo con NumPy. Esto parece muy lento.

Answer 1

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

También puede verificar si su aplicación es residente en RAM, en lugar de cambiar. Solo tiene 381 MB, pero es posible que el sistema no lo esté dando todo por el motivo que sea.

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

Answer 2

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

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

Answer 3

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

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

a[i] += 1

Perfiles:

• [0] * 20000000

  • Acceso: 2.3M / seg.
  • Inicialización: 0.8s

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

  • Acceso: 160K / seg.
  • Inicialización: 0.2s

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

  • Acceso: 175K / seg.
  • Inicialización: 2.0s

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

  • Acceso: 175K / seg, probablemente, basado en el perfil para el otro array.array
  • Inicialización: 6.7s

Answer 4

Para una creación rápida, utilice el módulo de matriz.

El uso del módulo de matriz es ~ 5 veces más rápido para la creación, pero casi el doble de lento para acceder a los elementos en comparación con una lista 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 5

Prueba esto:

x = [0] * 100000000

Tarda solo unos segundos en ejecutarse en mi máquina y el acceso es casi instantáneo.

Answer 6

Si

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

Lo siguiente puede ser de su interés. Inicializa array.array aproximadamente 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 Cómo inicializar un objeto array.array entero con ceros en Python , estoy buscando una forma aún mejor.

Answer 7

Si no puedes vectorizar tus cálculos, Python / Numpy será lento. Numpy es rápido porque los cálculos vectorizados se producen en un nivel inferior al de Python. Las funciones básicas del número están escritas en C o Fortran. Por lo tanto, la sum(a) no es un bucle python con muchos accesos, es una llamada C de bajo nivel.

La página de demostración de Numpy''s Performance Python tiene un buen ejemplo con diferentes opciones. Puede obtener fácilmente un aumento de 100x utilizando un lenguaje compilado de nivel inferior, Cython, o usando funciones vectorizadas si es posible. Esta publicación de blog que muestra un aumento de 43 veces utilizando Cython para un número de casos de uso.

Answer 8

Simplemente crearía su propio tipo de datos que no inicializa ningún 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 SE HA inicializado, simplemente devuelva el valor.

Si desea escribir en una posición de índice que NO se haya inicializado, inicialícela y almacene la entrada.

Answer 9

Solo un recordatorio de cómo funcionan los enteros de Python: si asigna una lista diciendo

a = [0] * K

necesita la memoria para la lista ( sizeof(PyListObject) + K * sizeof(PyObject*) ) y la memoria para el único objeto entero 0 . Mientras los números en la lista permanezcan 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 utilizando el siguiente fragmento de código:

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

Esto significa que tan pronto como los conteos superan 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 de V (== 256) . En un sistema de 64 bits, sizeof(PyIntObject) == 24 y sizeof(PyObject*) == 8 , es decir, el consumo de memoria en el peor de los casos es de 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 paga por los objetos de envoltura que se crean de manera transparente, como dijo Thomas Wouters. Probablemente, debería pensar en convertir el código de actualización (que accede y aumenta las posiciones en la matriz) a código C, ya sea utilizando Cython o scipy.weave .

Answer 10

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 será tan rápido, aunque las operaciones de todo el conjunto a menudo se pueden realizar a velocidades similares a las de C o Fortran. Si necesita realizar operaciones en millones y millones de elementos individualmente de manera rápida, solo hay tantas cosas que puede obtener de Python.

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