Sumando con un bucle for más rápido que con reducir?

Quería ver cuánto más rápido era reducir que usar un bucle for para operaciones numéricas simples. Esto es lo que encontré (usando la biblioteca estándar de timeit):

In [54]: print(setup) from operator import add, iadd r = range(100) In [55]: print(stmt1) c = 0 for i in r: c+=i In [56]: timeit(stmt1, setup) Out[56]: 8.948904991149902 In [58]: print(stmt3) reduce(add, r) In [59]: timeit(stmt3, setup) Out[59]: 13.316915035247803 

Mirando un poco más:

 In [68]: timeit("1+2", setup) Out[68]: 0.04145693778991699 In [69]: timeit("add(1,2)", setup) Out[69]: 0.22807812690734863 

¿Que está pasando aqui? Obviamente, reducir hace un bucle más rápido que para, pero la función de llamada parece dominar. ¿No debería la versión reducida ejecutarse casi por completo en C? El uso de iadd (c, i) en la versión de bucle for hace que se ejecute en ~ 24 segundos. ¿Por qué el uso de operator.add sería mucho más lento que +? Estaba bajo la impresión de + y operator.add ejecutaba el mismo código C (verifiqué para asegurarme de que operator.add no solo estaba llamando a + en Python o algo así).

Por cierto, solo usando la sum se ejecuta en ~ 2.3 segundos.

 In [70]: print(sys.version) 2.7.1 (r271:86882M, Nov 30 2010, 09:39:13) [GCC 4.0.1 (Apple Inc. build 5494)] 

La función reduce(add, r) debe invocar la función add() 100 veces, por lo que la sobrecarga de las llamadas a la función se sum: reduce usa PyEval_CallObject para invocar add en cada iteración:

 for (;;) { ... if (result == NULL) result = op2; else { # here it is creating a tuple to pass the previous result and the next # value from range(100) into func add(): PyTuple_SetItem(args, 0, result); PyTuple_SetItem(args, 1, op2); if ((result = PyEval_CallObject(func, args)) == NULL) goto Fail; } 

Actualizado : Respuesta a pregunta en comentarios.

Cuando escribe 1 + 2 en el código fuente de Python, el comstackdor de bytecode realiza la adición en su lugar y reemplaza esa expresión con 3 :

 f1 = lambda: 1 + 2 c1 = byteplay.Code.from_code(f1.func_code) print c1.code 1 1 LOAD_CONST 3 2 RETURN_VALUE 

Si agrega dos variables a + b el comstackdor generará un bytecode que carga las dos variables y realiza un BINARY_ADD, que es mucho más rápido que llamar a una función para realizar la adición:

 f2 = lambda a, b: a + b c2 = byteplay.Code.from_code(f2.func_code) print c2.code 1 1 LOAD_FAST a 2 LOAD_FAST b 3 BINARY_ADD 4 RETURN_VALUE 

Podría ser la sobrecarga de copiar argumentos y valores de retorno (es decir, “agregar (1, 2)”), en lugar de simplemente operar con literales numéricos

Editar : Al cambiar los ceros en lugar de multiplicar los arreglos, se cierra la brecha a lo grande.

 from functools import reduce from numpy import array, arange, zeros from time import time def add(x, y): return x + y def sum_columns(x): if x.any(): width = len(x[0]) total = zeros(width) for row in x: total += array(row) return total l = arange(3000000) l = array([l, l, l]) start = time() print(reduce(add, l)) print('Reduce took {}'.format(time() - start)) start = time() print(sum_columns(l)) print('For loop took took {}'.format(time() - start)) 

Te derriba casi ninguna diferencia en absoluto.

Reduce took 0.03230619430541992 For loop took took 0.058577775955200195

old : si reduce se usa para sumr matrices NumPy por índice, puede ser más rápido que un bucle for.

 from functools import reduce from numpy import array, arange from time import time def add(x, y): return x + y def sum_columns(x): if x.any(): width = len(x[0]) total = array([0] * width) for row in x: total += array(row) return total l = arange(3000000) l = array([l, l, l]) start = time() print(reduce(add, l)) print('Reduce took {}'.format(time() - start)) start = time() print(sum_columns(l)) print('For loop took took {}'.format(time() - start)) 

Con el resultado de

 [ 0 3 6 ..., 8999991 8999994 8999997] Reduce took 0.024930953979492188 [ 0 3 6 ..., 8999991 8999994 8999997] For loop took took 0.3731539249420166