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

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

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

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

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

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

另一方面，CPython 3 明显比 CPython 2 慢的事实在对数-对数图中更难看出。