优化：循环 vs 求和生成器推导式

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

有人能解释一下为什么这个操作明显变慢了吗？对于非专业人士来说，这个操作的不同之处并不容易看出来。

- Joost

---

在前者中，您在迭代过程中跟踪“min”值。而在后者中，则需要另一次遍历。请问“lengths”中有多少个元素（数量级是多少）？ - Brian Cain

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}

在我的电脑上（Windows，Python2.7），它们几乎以相同的速度运行，但请注意函数调用次数多了多少。在Python中，函数调用是昂贵的，有时最好坚持使用循环和简单的解决方案。

通过查看配置文件转储，sum被调用101次，在迭代解决方案中，您可以使用+=运算符来完成此操作，因此不会调用任何函数。

功能代码将循环移动到C中，但以调用101个函数为代价，或者可能只是长度的长度，因此需要调用len（lengths）更多函数。

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

我不确定评论中提到的min是否需要再次迭代整个数组来提取最小值。函数式解决方案基于生成器。外部生成器min是推动生成器所有机制的引擎。

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

隐式地，min实际上正在跟踪最小值，因为您正在使用生成器而不是列表推导。

希望这有所帮助！

- Paulo Bu