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.9803170430004684