python:求和的速度

Question

我知道对数字列表求和的最快方法是使用内置函数sum。与使用reduce相比，使用for循环进行求和可能是一种较慢的方法。然而，当我尝试它时，它并不是真的。有人能解释一下这个结果吗？

import time, random, operator

sample = [random.randrange(10000) for _ in range(1000000)]

def use_for(l):
    acc = 0
    for n in l:
        acc += n
    print acc

def use_lambda(l):
    print reduce(operator.add, l)

print time.time()
use_for(l)
print time.time()
use_lambda(l)
print time.time()

我得到的时间：

1479671513.04
4998734199
1479671513.07
4998734199
1479671513.13

Answer 1

让我向您展示如何更系统地完成此操作。首先，您应该使用timeit模块进行基准测试。正确使用它有点笨拙，但它的准确性要高得多。其次，绝对确保除了您关心的测试中的基准测试之外，您没有做任何其他工作。特别是，您不应该打印测试函数中的任何内容，因为打印内容的开销很大。第三，您应该在一定的长度范围内测试每个候选函数，然后将结果绘制成图形。第四，你不需要增加到一百万个数字才能得到有用的结果。

import csv
import operator
import random
import sys
from functools import partial, reduce
from timeit import timeit

lengths = [10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000]

samples = [ [random.randrange(10000) for i in range(n)]
            for n in lengths ]

def use_for(l):
    acc = 0
    for n in l: acc += n
    return acc

def use_reduce(l):
    return reduce(operator.add, l)

def use_sum(l):
    return sum(l)

def main():
    with sys.stdout as ofp:
        wr = csv.writer(ofp, lineterminator='\n', quoting=csv.QUOTE_MINIMAL)
        wr.writerow(('len','for loop','reduce','sum'))

        for length, sample in zip(lengths, samples):
            t_for = timeit(partial(use_for, sample), number=1000)
            t_red = timeit(partial(use_reduce, sample), number=1000)
            t_sum = timeit(partial(use_sum, sample), number=1000)
            wr.writerow((length, t_for, t_red, t_sum))

main()

我们运行这个测试程序，然后绘制输出。您没有说您使用的是Python2还是Python3，所以我编写了上面的代码来使用这两种语言，我对这两种方法都进行了测试。[编辑：，既然另一个答案提到了它，我现在也测试了PyPy。]不用担心我正在做的绘图的细节- ggplot非常值得学习，但它以及它嵌入的R语言可能非常神秘。

$ python2 sumbench.py > sumbench-2.csv
$ python3 sumbench.py > sumbench-3.csv
$ pypy    sumbench.py > sumbench-P.csv
$ R --quiet
> suppressPackageStartupMessages({ library(reshape2); library(ggplot2); })
> data2 <- melt(read.csv('sumbench-2.csv'), id.var='len')
> data3 <- melt(read.csv('sumbench-3.csv'), id.var='len')
> dataP <- melt(read.csv('sumbench-P.csv'), id.var='len')
> data2$interp <- ordered('CPython 2', levels=c('CPython 2','CPython 3','PyPy'))
> data3$interp <- ordered('CPython 3', levels=c('CPython 2','CPython 3','PyPy'))
> dataP$interp <- ordered('PyPy',      levels=c('CPython 2','CPython 3','PyPy'))
> data <- rbind(data2, data3, dataP)
> colnames(data) <- c("Input length", "Algorithm", "Time (ms)", "Interpreter")
> ggplot(data, aes(x=`Input length`, y=`Time (ms)`,
                   colour=`Algorithm`, linetype=`Algorithm`)) +
      facet_grid(.~`Interpreter`) + geom_line() +
      theme_grey(base_size=9) +
      theme(legend.position=c(0.01,0.98), legend.justification=c(0,1))

​

​

这清楚地表明，使用reduce确实比使用for循环慢，但sum比这两种循环都要快得多。它还清楚地表明，CPython 3.5的速度比2.7慢，这是可悲的，但在意料之中。PyPy不仅比它们中的任何一个都快5倍，而且这三种算法的性能都一样好！这就是当你使用一个真正的优化编译器来处理这类代码时会发生的事情。(PyPy比CPython的sum()内部函数更快，因为它可以计算出数组的所有元素都是数字的，并减少一大堆每个元素的开销。NumPy数组的sum方法可能与PyPy一样快。)

在对数-对数尺度上绘制这样的数据通常很好-这也是我选择长度的原因：

> last_plot() + scale_x_log10() + scale_y_log10()

​

​

看到它们现在的斜率都大致相同了吗？这意味着所有三种技术的是相同的，O(n)，只是不同的常数因子。渐近复杂性很重要，因为它可以让你预测更大的输入需要多长时间。在这种情况下，如果我们想知道您的原始测试用例需要多长时间，我们可以将这三行扩展到x轴上的一百万行。对于不同的大O，我们会看到曲线，我们需要用不同的方式来推断它们。

我们还可以看到sum()在它的曲线上有一个弯曲，这在线性图上是完全看不见的；这意味着在实现中可能有一些特殊的短列表。更清楚的是，reduce与3中的手写for循环的性能几乎相同；reduce不再是3中的内置函数，但它仍然是在编译的代码中实现的，所以我没有对此进行解释。我们可以看到，PyPy在一开始就以一种不可预测的方式变得非常慢:这是因为正在进行基准测试的函数的实时编译成本被归因于早期调用。我可以在基准测试中添加一个“热身”步骤，让它消失，但这是一件很好的事情。

另一方面，在对数-对数图上很难看到CPython 3比CPython 2慢得多的事实。

Answer 2

对于sum，我得到了截然不同的时间安排。

您可能希望使用timeit作为计时小段代码的更好方法。下面是一个示例：

from __future__ import print_function
import operator
from functools import reduce

def f1(l):
    return sum(l)

def f2(l):
    return reduce(operator.add, l)

def f3(l):
    s=0
    for e in l:
        s+=e
    return s    

if __name__=='__main__':
    import timeit 
    import random  
    l=[random.randrange(10000) for _ in range(1000000)] 
    for f in (f1, f2, f3):
        print("   ",f.__name__, timeit.timeit("f(l)", setup="from __main__ import f, l", number=100) )     

Python3打印：

f1 0.7481771620000472
f2 6.92161642699989
f3 5.201012654999886

Python2打印：

f1 0.554444074631
f2 4.81940102577
f3 3.65543603897

PyPy：

f1 0.108825922012
f2 0.112055063248
f3 0.105736970901

Answer 3

读完你的问题后，我想到的第一件事是：

与使用reduce相比，使用

循环进行求和可能是一种较慢的方法

这是基于一些文档或数据，还是仅仅是一个假设？我读了一些，看起来这只是一个假设。

基于functional programming上的python文档

功能设计可能看起来像是一个奇怪的工作约束。为什么要避免对象和副作用？函数式风格有理论上和实践上的优势：

• 调试和测试的正式provability.
• Modularity.
• Composability.
• Ease。

速度似乎不是一个优势。如果有什么不同的话，我认为由于调用函数的开销，它将是缓慢的(你的经验数据支持这一点)。

此外，由于sum是在c中实现的，因此它的速度更快