用for循环求和比用reduce快吗？

Question

我想看看在简单的数字运算中，使用 reduce 函数比用 for 循环快多少。以下是我用标准的 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

再深入看看：

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

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

这里发生了什么呢？显然，reduce 的循环速度比 for 循环快，但函数调用似乎占据了大部分时间。难道 reduce 的版本不应该几乎完全在 C 语言中运行吗？在 for 循环中使用 iadd(c,i) 让它的运行时间变成了大约 24 秒。为什么使用 operator.add 会比直接用 + 慢这么多呢？我原以为 + 和 operator.add 运行的是同样的 C 代码（我检查过，确保 operator.add 不是在 Python 中只是调用 + 之类的）。

顺便提一下，直接使用 sum 的运行时间大约是 2.3 秒。

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

Answer 1

编辑: 用零来替代数组的乘法，能大大缩小差距。

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))

这样几乎没有什么区别。

使用 reduce 的时间是 0.03230619430541992 使用 for 循环的时间是 0.058577775955200195

之前说过: 如果用 reduce 来按索引把 NumPy 数组加在一起，它的速度可能比 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))

结果是

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

Answer 2

这可能是因为在处理参数和返回值时需要额外的开销，比如说调用“add(1, 2)”这个函数时，而不是直接对数字进行操作。

Answer 3

在这里，reduce(add, r) 这个操作需要调用 add() 函数 100 次，所以每次调用函数都会有一些额外的开销，这些开销会累积起来。实际上，reduce 在每次循环时都会用 PyEval_CallObject 来调用 add 函数：

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;
    }

更新: 针对评论中的问题的回复。

当你在 Python 代码中输入 1 + 2 时，字节码编译器会直接在原地进行加法运算，并把这个表达式替换成 3：

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

1           1 LOAD_CONST           3
            2 RETURN_VALUE         

如果你加两个变量 a + b，编译器会生成字节码，它会加载这两个变量并执行一个叫 BINARY_ADD 的操作，这个过程比调用一个函数来进行加法要快得多：

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