python - 优化 : loops vs summing generator comprehensions

Question

在今天的 Google Code Jam 中(特别是在“The Repeater”上)，我遇到了以下两个代码片段之间奇怪的性能差异。

对于下面的代码片段，假设 lengths 是一个正整数列表。

当使用以下代码(嵌套在循环中的某处)时，我的解决方案运行时间大约为 3.1 秒。

minmov = -1
for target in range(101):
    mov = 0
    for l in lengths:
        mov += abs(l - target)
    if mov < minmov or minmov == -1:
        minmov = mov
moves += minmov

但是，当我用下面看到的功能等效的代码片段替换它时，它突然需要 4.2 秒。高达 33% 的增长!

moves += min(sum(abs(l - t) for l in lengths) for t in range(101))

任何人都可以向我解释为什么这会慢得多吗？对于不经意的观察者来说，为什么这样做会有所不同并不是很明显。

Answer 1

您可以使用 Python 的标准库 cProfile 模块来查看代码中哪些地方耗费了时间。我用一个最小的工作示例包装了代码并对其进行了分析(不确定它是否完全模仿了算法的行为，但我希望它对表达我的观点有用):

代码:

import random
moves = 0
lengths = [random.randint(-10,10) for _ in range(101)]

def foo():
    global moves
    minmov = -1
    for target in range(101):
        mov = 0
        for l in lengths:
            mov += abs(l - target)
        if mov < minmov or minmov == -1:
            minmov = mov
    moves += minmov

def foo2():
    global moves
    moves += min(sum(abs(l - t) for l in lengths) for t in range(101))

import cProfile
cProfile.run("foo2()")
#cProfile.run("foo2()")

简介迭代:

python t.py
         10205 function calls in 0.023 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.023    0.023 <string>:1(<module>)
        1    0.013    0.013    0.023    0.023 t.py:5(foo)
    10201    0.010    0.000    0.010    0.000 {abs}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {range}

功能简介:

python t1.py
         10409 function calls in 0.023 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.047    0.047 <string>:1(<module>)
        1    0.000    0.000    0.047    0.047 t.py:16(foo2)
      102    0.000    0.000    0.047    0.000 t.py:18(<genexpr>)
    10201    0.010    0.000    0.010    0.000 {abs}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.047    0.047 {min}
        1    0.000    0.000    0.000    0.000 {range}
      101    0.012    0.000    0.046    0.000 {sum}

在我的 PC(Windows、Python2.7)上，它们几乎以相同的速度运行，但请注意函数代码 执行了多少函数调用。 Python 中的函数调用很昂贵，有时最好坚持使用循环和简单的解决方案。

通过查看配置文件转储，sum 被调用了 101 次，在您的迭代解决方案中，您通过使用 += 运算符来执行此操作，因此没有函数被调用.

功能代码将循环移动到 C，但以 101 为代价(或者也许这个 101 只是意味着 lengths 的长度，所以它会在len(lengths)) 更多函数调用的成本。

我敢打赌这就是造成额外开销的原因。你可以阅读 Guido 的优秀 Python Patterns - An Optimization Anecdote文章以获取有关此主题的更多信息。

我不完全确定 min 必须再次迭代整个数组以提取评论中提到的最小值。功能解决方案基于生成器。外部发电机 min 在本例中是驱动所有发电机机械的引擎。

当 min 启动时，它将尝试找到作为参数传递的生成器上的第一个元素，这反过来将唤醒 sum 方法并启动求和的参数生成器，生成 abs(l[0] - 0) 作为 sum 参数生成器的第一个值，这样做直到整个和 abs(l[ 0]-0) + abs(l[1]-0)... 被计算出来，然后这将是 min 参数生成器的第一个值。 min 会在移动时跟踪它以检查其参数生成器中的第二个元素等等。

隐含地，min 实际上是在跟踪最小值，因为您使用的是生成器，而不是列表理解。

希望这对您有所帮助!