¿Por qué es un `for ‘sobre una lista de Python más rápido que sobre una matriz Numpy?

Así que sin contar una historia realmente larga, estaba trabajando en un código donde estaba leyendo algunos datos de un archivo binario y luego repasaba cada punto con un bucle for. Así que completé el código y estaba corriendo ridículamente lento. Recorrí alrededor de 60,000 puntos de alrededor de 128 canales de datos y esto tardó un minuto o más en procesarse. Esto era mucho más lento de lo que esperaba que se ejecutara Python. Así que hice que todo fuera más eficiente al usar Numpy, pero al tratar de averiguar por qué el proceso original se ejecutó tan lentamente, hicimos algunas comprobaciones de tipos y descubrí que estaba repasando arrays de Numpy en lugar de listas de Python. No hay problema para hacer que las entradas a nuestra configuración de prueba sean las mismas. Convirtí las matrices de Numpy en listas antes de hacer un bucle. Golpear el mismo código lento que tardó un minuto en ejecutarse ahora tomó 10 segundos. Me quedé en el suelo. Lo único que pensé fue cambiar una matriz de Numpy a una lista de Python, la cambié de nuevo y fue lento como el barro otra vez. No podía creerlo, así que fui a buscar más pruebas definitivas.

$ python -m timeit -s "import numpy" "for k in numpy.arange(5000): k+1" 100 loops, best of 3: 5.46 msec per loop $ python -m timeit "for k in range(5000): k+1" 1000 loops, best of 3: 256 usec per loop 

Que esta pasando? Sé que los arrays de Numpy y la lista de Python son diferentes, pero ¿por qué es mucho más lento recorrer cada punto de un array?

Observé este comportamiento en Python 2.6 y 2.7 ejecutando Numpy 10.1, creo.

Podemos hacer un poco de investigación para resolver esto:

 >>> import numpy as np >>> a = np.arange(32) >>> a array([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]) >>> a.data  >>> id(a.data) 4433424176 >>> id(a[0]) 4424950096 >>> id(a[1]) 4424950096 >>> for item in a: ... print id(item) ... 4424950096 4424950120 4424950096 4424950120 4424950096 4424950120 4424950096 4424950120 4424950096 4424950120 4424950096 4424950120 4424950096 4424950120 4424950096 4424950120 4424950096 4424950120 4424950096 4424950120 4424950096 4424950120 4424950096 4424950120 4424950096 4424950120 4424950096 4424950120 4424950096 4424950120 4424950096 4424950120 

Entonces, ¿qué está pasando aquí? Primero, eché un vistazo a la ubicación de memoria del búfer de memoria del arreglo. Está en 4433424176 . Eso en sí mismo no es muy iluminador. Sin embargo, numpy almacena sus datos como una matriz C contigua, por lo que el primer elemento de la matriz numpy debe corresponder a la dirección de memoria de la matriz en sí, pero no lo hace:

 >>> id(a[0]) 4424950096 

y es bueno que no lo haga porque eso rompería el invariante en Python de que 2 objetos nunca tienen la misma id durante sus vidas.

Entonces, ¿cómo logra esto Npypy? Bueno, la respuesta es que numpy tiene que envolver el objeto devuelto con un tipo python (por ejemplo, numpy.float64 o numpy.int64 en este caso), lo que lleva tiempo si está iterando elemento por elemento 1 . Se demuestra una prueba adicional de esto cuando se realiza la iteración. Vemos que estamos alternando entre 2 ID independientes al iterar sobre la matriz. Esto significa que el asignador de memoria y el recolector de basura de Python están trabajando horas extras para crear nuevos objetos y luego liberarlos.

Una lista no tiene esta sobrecarga de asignador de memoria / recolector de basura. Los objetos de la lista ya existen como objetos de Python (y seguirán existiendo después de la iteración), por lo que ninguno de ellos desempeña ningún papel en la iteración sobre una lista.

Metodología de tiempo:

Además, tenga en cuenta que sus tiempos se ven afectados por sus suposiciones. Estabas asumiendo que k + 1 debería tomar aproximadamente la misma cantidad de tiempo en ambos casos, pero no es así. Observe si repito sus tiempos sin hacer ninguna adición:

 mgilson$ python -m timeit -s "import numpy" "for k in numpy.arange(5000): k" 1000 loops, best of 3: 233 usec per loop mgilson$ python -m timeit "for k in range(5000): k" 10000 loops, best of 3: 114 usec per loop 

solo hay un factor de diferencia de 2 Sin embargo, hacer la adición conduce a un factor de diferencia de 5 o menos:

 mgilson$ python -m timeit "for k in range(5000): k+1" 10000 loops, best of 3: 179 usec per loop mgilson$ python -m timeit -s "import numpy" "for k in numpy.arange(5000): k+1" 1000 loops, best of 3: 786 usec per loop 

Para la diversión, simplemente hagamos la adición:

 $ python -m timeit -s "v = 1" "v + 1" 10000000 loops, best of 3: 0.0261 usec per loop mgilson$ python -m timeit -s "import numpy; v = numpy.int64(1)" "v + 1" 10000000 loops, best of 3: 0.121 usec per loop 

Y, finalmente, su tiempo también incluye el tiempo de construcción de lista / matriz, que no es ideal:

 mgilson$ python -m timeit -s "v = range(5000)" "for k in v: k" 10000 loops, best of 3: 80.2 usec per loop mgilson$ python -m timeit -s "import numpy; v = numpy.arange(5000)" "for k in v: k" 1000 loops, best of 3: 237 usec per loop 

Tenga en cuenta que en este caso Numpy se alejó mucho más de la solución de la lista. Esto muestra que la iteración en realidad es más lenta y es posible que obtenga algunas aceleraciones si convierte los tipos numpy a los tipos de python estándar.

1 Tenga en cuenta que esto no lleva mucho tiempo al segmentar, ya que solo tiene que asignar O (1) nuevos objetos ya que numpy devuelve una vista a la matriz original.

Usando Python 2.7

Aquí están mis velocidades junto con xrange:

 python -m timeit -s "import numpy" "for k in numpy.arange(5000): k+1" 

1000 bucles, lo mejor de 3: 1.22 ms por bucle

 python -m timeit "for k in range(5000): k+1" 

10000 bucles, lo mejor de 3: 186 usec por bucle

 python -m timeit "for k in xrange(5000): k+1" 

10000 bucles, lo mejor de 3: 161 usec por bucle

Numpy es notablemente más lento porque está iterando sobre una matriz específica de números. Esta no es su función principal. En muchos casos, deben tratarse más como una colección monolítica de números en lugar de simples listas / iterables. Por ejemplo, si tenemos una lista de números de python bastante grande que queremos elevar al tercer poder, podríamos hacer algo como esto:

 python -m timeit "lst1 = [x for x in range(100000)];" "lst2 = map(lambda x: x**3, lst1)" 

10 bucles, lo mejor de 3: 125 ms por bucle

Nota: el lst1 representa una lista arbitraria. Soy consciente de que puede acelerar esto dentro de la lambda original haciendo x ** 3 para x en el rango, pero se trata de una lista que ya debería existir y que posiblemente no sea secuencial.

De todos modos, numpy está destinado a ser tratado como una matriz sería:

 python -m timeit -s "import numpy" "lst1 = numpy.arange(100000)" "lst2 = lst1**2" 

10000 bucles, lo mejor de 3: 120 usec por bucle

Digamos que tenía dos listas de valores arbitrarios, cada uno de los cuales quiere multiplicar juntos. En la vainilla python, podrías hacer:

 python -m timeit -s "lst1 = [x for x in xrange(0, 10000, 2)]" "lst2 = [x for x in xrange(2, 10002, 2)]" "lst3 = [x*y for x,y in zip(lst1, lst2)]" 

1000 bucles, lo mejor de 3: 736 usec por bucle

Y en Numpy:

 python -m timeit -s "import numpy" "lst1 = numpy.arange(0, 10000, 2)" "lst2 = numpy.arange(2, 10002, 2)" "lst3 = lst1*lst2" 

100000 bucles, lo mejor de 3: 10.9 usec por bucle

En estos dos últimos ejemplos, NumPy se dispara por delante como el claro ganador. Para una iteración simple sobre una lista, rango o rango es perfectamente suficiente, pero su ejemplo no tiene en cuenta el verdadero propósito de los arreglos de Numpy. Está comparando aviones y coches; Sí, los aviones son generalmente más rápidos para lo que están destinados a hacer, pero tratar de volar a su supermercado local no es prudente.