python：求和的速度

Question

我知道对数字列表求和的最快方法是使用内置函数sum。使用for循环求和可能比使用 更慢reduce。然而，当我尝试时，事实并非如此。有人可以解释这个结果吗？

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

我们运行这个测试程序，然后绘制输出。你没有说你使用的是Python 2还是Python 3，所以我编写了上面的代码来使用其中任何一个，并且我对这两种方式进行了测试。 [编辑：既然另一个答案提到了它，我现在也测试了 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))

这非常清楚地表明 usingreduce确实比for循环慢，但sum比两者都快得多。它还清楚地表明 CPython 3.5 在这方面比 2.7 慢，这令人遗憾，但却是意料之中的。PyPy 不仅比它们中的任何一个快 5 倍，而且所有三种算法的性能都同样好！当您对此类代码使用真正的优化编译器时，就会发生这种情况。（PyPy 比 CPython 的内在函数更快sum()，因为它可以计算出数组的所有元素都是数字，并去除大量每个元素的开销sum。NumPy 数组的方法可能与 PyPy 一样快或更快。）

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

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

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

我们还可以看到 sum() 的曲线有一个弯曲，这在线性图上完全不可见；这意味着在实现中可能存在一些特殊的短列表大小写。而且更清楚的是，它的性能与2 中的reduce手写循环非常接近，但不是 3；不再是3中的内置函数，但它仍然在编译代码中实现，所以我对此没有解释。我们可以看到 PyPy 在开始时以一种不可预测的方式显着变慢：这是因为被基准测试的函数的即时编译成本已归因于早期调用。我可以在基准测试中添加一个“热身”步骤并使其消失，但了解这一点是一件好事。forreduce

另一方面，CPython 3 明显慢于 CPython 2 的事实在双对数图中很难看出。