Vi un video sobre la velocidad de los bucles en python, donde se explicaba que hacer sum(range(N)) es mucho más rápido que recorrer manualmente el range y sumar las variables, ya que el primero se ejecuta en C debido a las funciones integradas. siendo utilizado, mientras que en este último la suma se realiza en python (lento). Tenía curiosidad por lo que sucede al agregar numpy a la mezcla. Como esperaba, np.sum(np.arange(N)) es el más rápido, pero sum(np.arange(N)) y np.sum(range(N)) son incluso más lentos que hacer el ingenuo bucle for.
¿Por qué es esto?
Aquí está el script que usé para probar, algunos comentarios sobre la supuesta causa de la ralentización que yo sé (tomados principalmente del video) y los resultados que obtuve en mi máquina (python 3.10.0, numpy 1.21.2):
guión actualizado:
import numpy as np from timeit import timeit N = 10_000_000 repetition = 10 def sum0(N = N): s = 0 i = 0 while i < N: # condition is checked in python s += i i += 1 # both additions are done in python return s def sum1(N = N): s = 0 for i in range(N): # increment in C s += i # addition in python return s def sum2(N = N): return sum(range(N)) # everything in C def sum3(N = N): return sum(list(range(N))) def sum4(N = N): return np.sum(range(N)) # very slow np.array conversion def sum5(N = N): # much faster np.array conversion return np.sum(np.fromiter(range(N),dtype = int)) def sum5v2_(N = N): # much faster np.array conversion return np.sum(np.fromiter(range(N),dtype = np.int_)) def sum6(N = N): # possibly slow conversion to Py_long from np.int return sum(np.arange(N)) def sum7(N = N): # list returns a list of np.int-s return sum(list(np.arange(N))) def sum7v2(N = N): # tolist conversion to python int seems faster than the implicit conversion # in sum(list()) (tolist returns a list of python int-s) return sum(np.arange(N).tolist()) def sum8(N = N): return np.sum(np.arange(N)) # everything in numpy (fortran libblas?) def sum9(N = N): return np.arange(N).sum() # remove dispatch overhead def array_basic(N = N): return np.array(range(N)) def array_dtype(N = N): return np.array(range(N),dtype = np.int_) def array_iter(N = N): # np.sum's source code mentions to use fromiter to convert from generators return np.fromiter(range(N),dtype = np.int_) print(f"while loop: {timeit(sum0, number = repetition)}") print(f"for loop: {timeit(sum1, number = repetition)}") print(f"sum_range: {timeit(sum2, number = repetition)}") print(f"sum_rangelist: {timeit(sum3, number = repetition)}") print(f"npsum_range: {timeit(sum4, number = repetition)}") print(f"npsum_iterrange: {timeit(sum5, number = repetition)}") print(f"npsum_iterrangev2: {timeit(sum5, number = repetition)}") print(f"sum_arange: {timeit(sum6, number = repetition)}") print(f"sum_list_arange: {timeit(sum7, number = repetition)}") print(f"sum_arange_tolist: {timeit(sum7v2, number = repetition)}") print(f"npsum_arange: {timeit(sum8, number = repetition)}") print(f"nparangenpsum: {timeit(sum9, number = repetition)}") print(f"array_basic: {timeit(array_basic, number = repetition)}") print(f"array_dtype: {timeit(array_dtype, number = repetition)}") print(f"array_iter: {timeit(array_iter, number = repetition)}") print(f"npsumarangeREP: {timeit(lambda : sum8(N/1000), number = 100000*repetition)}") print(f"npsumarangeREP: {timeit(lambda : sum9(N/1000), number = 100000*repetition)}") # Example output: # # while loop: 11.493371912998555 # for loop: 7.385945574002108 # sum_range: 2.4605720699983067 # sum_rangelist: 4.509678105998319 # npsum_range: 11.85120212900074 # npsum_iterrange: 4.464334709002287 # npsum_iterrangev2: 4.498494338993623 # sum_arange: 9.537815956995473 # sum_list_arange: 13.290120724996086 # sum_arange_tolist: 5.231948580003518 # npsum_arange: 0.241889145996538 # nparangenpsum: 0.21876695199898677 # array_basic: 11.736577274998126 # array_dtype: 8.71628468400013 # array_iter: 4.303306431000237 # npsumarangeREP: 21.240833958996518 # npsumarangeREP: 16.690092379001726Desde el código fuente de cpython para sum sum inicialmente parece intentar una ruta rápida que asume que todas las entradas son del mismo tipo. Si eso falla, simplemente iterará:
/* Fast addition by keeping temporary sums in C instead of new Python objects. Assumes all inputs are the same type. If the assumption fails, default to the more general routine. */ No estoy del todo seguro de lo que sucede debajo del capó, pero es probable que la creación/conversión repetida de tipos C a objetos Python esté causando estas ralentizaciones. Vale la pena señalar que tanto la sum como el range se implementan en C.
El siguiente bit no es realmente una respuesta a la pregunta, pero me preguntaba si podríamos acelerar sum para python range s ya que range es un objeto bastante inteligente .
Para hacer esto, he usado functools.singledispatch para anular la función de sum incorporada específicamente para el tipo de range ; Luego implementó una pequeña función para calcular la suma de una progresión aritmética .
from functools import singledispatch def sum_range(range_, /, start=0): """Overloaded `sum` for range, compute arithmetic sum""" n = len(range_) if not n: return start return int(start + (n * (range_[0] + range_[-1]) / 2)) sum = singledispatch(sum) sum.register(range, sum_range) def test(): """ >>> sum(range(0, 100)) 4950 >>> sum(range(0, 10, 2)) 20 >>> sum(range(0, 9, 2)) 20 >>> sum(range(0, -10, -1)) -45 >>> sum(range(-10, 10)) -10 >>> sum(range(-1, -100, -2)) -2500 >>> sum(range(0, 10, 100)) 0 >>> sum(range(0, 0)) 0 >>> sum(range(0, 100), 50) 5000 >>> sum(range(0, 0), 10) 10 """ if __name__ == "__main__": import doctest doctest.testmod()No estoy seguro de si esto está completo, pero definitivamente es más rápido que hacer un bucle.
A ver si puedo resumir los resultados.
sum puede funcionar con cualquier iterable, solicitando repetidamente el siguiente valor y agregándolo. range es un generador, que está feliz de proporcionar el siguiente valor
# sum_range: 1.4830789409988938Hacer una lista de un rango lleva tiempo:
# sum_rangelist: 3.6745876889999636Sumar una lista pregenerada es en realidad más rápido que sumar el rango:
%%timeit x = list(range(N)) ...: sum(x) np.sum está diseñado para sumar matrices. Es un contenedor para np.add.reduce .
np.sum tiene una advertencia de desaprobación para np.sum(generator) , recomendando el uso de fromiter o Python sum :
# npsum_range: 16.216972655000063 fromiter es la mejor manera de hacer una matriz a partir de un generador. El uso de np.array en range es un código heredado y puede desaparecer en el futuro. Creo que es el único generator que np.array .
np.array es una función de propósito general que puede manejar muchos casos, incluidas matrices anidadas y conversión a varios tipos de d. Como tal, tiene que procesar todo el argumento de entrada, deduciendo tanto la forma como el tipo.
# npsum_fromiterrange:3.47655400199983La iteración en una matriz numpy es más lenta que una lista, ya que tiene que "desempaquetar" cada elemento.
# sum_arange: 16.656015603000924Del mismo modo, hacer una lista a partir de una matriz es lento; mismo tipo de iteración de nivel de Python.
# sum_list_arange: 19.500842117000502 arr.tolist() es relativamente rápido, creando una lista de python pura en código compilado. Entonces, la velocidad es similar a hacer una lista a partir del rango.
# sum_arange_tolist: 4.004777374000696 np.sum de una matriz es puramente numpy y bastante rápido. np.sum(x) donde x=np.arange(N) es aún más rápido (alrededor de 4x)
# npsum_arange: 0.2332638230000157 np.sum del rango o lista está dominado por el costo de crear primero la matriz:
# array_basic: 16.1631146109994 # array_dtype: 16.550737804000164 # array_iter: 3.9803170430004684np.sum(range(N)) es lento principalmente porque la implementación actual de Numpy no usa suficiente información sobre el tipo/contenido exacto de los valores proporcionados por el generador range(N) . El corazón del problema general se debe inherentemente a la tipificación dinámica de Python y los números enteros grandes, aunque Numpy podría optimizar este caso específico.
En primer lugar, range(N) devuelve un objeto de Python tipificado dinámicamente que es un (tipo especial de) generador de Python. El objeto proporcionado por este generador también se tipifica dinámicamente. En la práctica, es un entero de Python puro .
La cuestión es que Numpy está escrito en el lenguaje C de tipo estático y, por lo tanto, no puede funcionar de manera eficiente en objetos de Python puro de tipo dinámico. La estrategia de Numpy es convertir tales objetos en tipos C cuando puede. Un gran problema en este caso es que los enteros proporcionados por el generador teóricamente pueden ser enormes: Numpy no sabe si los valores pueden desbordar un np.int32 o incluso np.int64 . Por lo tanto, Numpy primero detecta el buen tipo a usar y luego calcula el resultado usando este tipo.
Este proceso de traducción puede ser bastante costoso y parece no ser necesario aquí, ya que todos los valores proporcionados por range(10_000_000) . Sin embargo, range(5_000_000_000) devuelve el mismo tipo de objeto con enteros de Python puro que desbordan np.int32 y Numpy necesita detectar automáticamente este caso para no devolver resultados incorrectos. La cuestión es que el tipo de entrada también se puede identificar correctamente ( np.int32 en mi máquina), no significa que el resultado de salida sea correcto porque pueden aparecer desbordamientos durante el cálculo de la suma. Lamentablemente, este es el caso en mi máquina.
Los desarrolladores de Numpy decidieron desaprobar dicho uso y colocar en la documentación que se debe usar np.fromiter en su lugar. np.fromiter tiene un parámetro requerido dtype para permitir que el usuario defina cuál es el tipo adecuado para usar.
Una forma de verificar este comportamiento en la práctica es simplemente crear una lista temporal:
tmp = list(range(10_000_000)) # Numpy implicitly convert the list in a Numpy array but # still automatically detect the input type to use np.sum(tmp)Una implementación más rápida es la siguiente:
tmp = list(range(10_000_000)) # The array is explicitly converted using a well-defined type and # thus there is no need to perform an automatic detection # (note that the result is still wrong since it does not fit in a np.int32) tmp2 = np.array(tmp, dtype=np.int32) result = np.sum(tmp2) El primer caso toma 476 ms en mi máquina mientras que el segundo toma 289 ms. Tenga en cuenta que np.sum tarda solo 4 ms. Por lo tanto, una gran parte del tiempo se dedica a la conversión de objetos enteros de Python puro a tipos int32 internos (más específicamente, la gestión de enteros de Python puro). list(range(10_000_000)) también es caro, ya que tarda 205 ms. Esto nuevamente se debe a la sobrecarga de los enteros de Python puro (es decir, asignaciones, desasignaciones, conteo de referencias, incremento de enteros de tamaño variable, indireccionamientos de memoria y condiciones debido a la tipificación dinámica), así como la sobrecarga del generador .
sum(np.arange(N)) es lento porque sum es una función de Python puro que trabaja en un objeto definido por Numpy. El intérprete de CPython necesita llamar a funciones Numpy para realizar adiciones básicas . Además, los objetos enteros definidos por Numpy siguen siendo objetos de Python y, por lo tanto, están sujetos a recuento de referencias, asignación, desasignación, etc. Sin mencionar que Numpy y CPython agregan muchas comprobaciones en las funciones con el objetivo de finalmente agregar dos números nativos juntos. Un compilador justo a tiempo compatible con Numpy, como Numba, puede resolver este problema . De hecho, Numba tarda 23 ms en mi máquina en calcular la suma de np.arange(10_000_000) (con el código todavía escrito en Python), mientras que el intérprete de CPython tarda 556 ms.