用for循环求和比用reduce函数更快吗？

Question

用for循环求和比用reduce函数更快吗？

13

我想看看使用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)]

- Bryan Head

1

使用 sum 函数可以使任务完成的速度快 4 倍，这基本上表明“应该有一种明显的方法来做到这一点”。 - jsbueno

@jsbbueno：没错，但我这样做是为了找出在序列上进行一般数值计算的最快方法。在现实世界中，我肯定会使用sum来求和:D 没有尝试过mul，但我相信结果会类似。 - Bryan Head

4个回答

0

自从我好奇起来，这里有一些关于64位Ubuntu 20.04的最新测试结果。

在Python 3.8.10中，对于这个简单的循环，reduce实际上更快一些。

$ python3 -m pyperf timeit -s 'c=0' 'for i in range(10000):c+=i'
Mean +- std dev: 410 us +- 20 us

$ python3 -m pyperf timeit -s 'from functools import reduce; from operator import add' 'reduce(add, range(10000))'
Mean +- std dev: 317 us +- 11 us

为了减少乘法运算的次数，使用for循环仍然更快速：

$ python3 -m pyperf timeit -s 'c=0' 'for i in range(1,100):c*=i'
Mean +- std dev: 3.00 us +- 0.39 us

$ python3 -m pyperf timeit -s 'from functools import reduce; from operator import mul' 'reduce(mul, range(1,100))'
Mean +- std dev: 4.39 us +- 0.22 us

当然，对于任何数字计算，我会使用PyPy或numpy。以下是PyPy 7.3.12的结果（假设pyperf准确地计算了JIT启动时间）：

$ pypy3 -m pyperf timeit -s 'c=0' 'for i in range(10000):c+=i'
Mean +- std dev: 10.1 us +- 0.9 us

$ pypy3 -m pyperf timeit -s 'from functools import reduce; from operator import add' 'reduce(add, range(10000))'
Mean +- std dev: 14.7 us +- 1.0 us

$ pypy3 -m pyperf timeit -s 'c=0' 'for i in range(1,100):c*=i'
Mean +- std dev: 141 ns +- 26 ns

$ pypy3 -m pyperf timeit -s 'from functools import reduce; from operator import mul' 'reduce(mul, range(1,100))'
Mean +- std dev: 1.95 us +- 0.06 us

对于加法而言，for循环大约快30%，但对于乘法来说，它几乎快14倍。所以PyPy明显优化了常用的for循环。

到目前为止，所有的函数式map和reduce都使用了Python内置的单核函数。对于一个库来说，将map和reduce并行化（至少对于纯函数来说）是微不足道的，这就是map的真正威力所在。

- qwr

0

编辑：用零替换数组乘法可以大幅缩小差距。

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 took 0.03230619430541992 For loop took took 0.058577775955200195

old: 如果使用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

- wegry

在这个例子中，for循环为什么如此慢有几个原因。1）使用zeros而不是用array([0] * width)创建零数组。2）l数组中的元素非常少，这有利于reduce函数，因为for循环的开销太高了。一旦有6个或更多元素，for循环就会更快。 - nickpapior

@zeroth，确实大大缩小了差距。在Python 3.6和最新版本的NumPy中，它们的性能几乎相同。 - wegry

0

这可能是复制参数和返回值（即“add(1, 2)”）的开销，而不是简单地操作数字字面值

- user297250

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- samplebias · Accepted Answer

使用 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