python - 为什么这两种计算总和的方法会产生不同的运行时间

Question

为什么这两种计算总和的方法会产生不同的运行时间？ (5次检查)两个代码都运行于:https://colab.research.google.com

from timeit import repeat

setup = 'a = [1] * 10_000_000'

expressions = [
    'sum(x % 2 for x in a)',
    'sum(True for x in a if x % 2)',
]

for expression in expressions:
    times = sorted(repeat(expression, setup, number=1))
    print(*('%.2f ' % t for t in times), expression)

结果:

0.65  0.65  0.65  0.65  0.66  sum(x % 2 for x in a)
1.03  1.04  1.04  1.05  1.06  sum(True for x in a if x % 2)

另一个检查但不同的结果:

...

setup = 'a = [0] * 10_000_000'

...

结果:

0.66  0.66  0.66  0.67  1.45  sum(x % 2 for x in a)
0.43  0.43  0.44  0.45  0.46  sum(True for x in a if x % 2)

第三次检查

...

setup = 'a = range(10**7)'

...

结果:

0.75  0.75  0.76  0.77  0.78  sum(x % 2 for x in a)
0.81  0.82  0.82  0.82  0.84  sum(True for x in a if x % 2)

Answer 1

为清楚起见，我们表示:

表达式 1:sum(x % 2 for x in a)

表达式 2:sum(True for x in a if x % 2)

检查 1:a = [1] * 10_000_000

检查 2:a = [0] * 10_000_000

检查 3:a = range(10**7)

现在，在这两项检查中，表达式 1 涉及计算 1000 万个模值并对所有 1000 万个值求和。无论模数始终为 1(检查 1)还是始终为 0(检查 0)，这花费的时间几乎相同。

表达式 2 的工作方式略有不同。它计算 1000 万个模值，将它们与零进行比较，并对仅包含非零值的条目的系列求和。

对于检查 1，这意味着表达式 2 需要进行 1000 万次比较，并对 1000 万个值求和。这与检查 1 中表达式 1 的总和相同，但增加了比较工作。因此，对于检查 1，表达式 2 比表达式 1 慢也就不足为奇了。

对于检查 2，表达式 2 有 1000 万次比较要再次进行，但这些比较都发现模数为零。因此求和步骤无事可做!事实证明，与 Check 2 相比，表达式 2 用于比较的时间少于它因不必对所有内容求和而节省的时间。所以对于检查 2，表达式 2 比表达式 1 更快。

(在使用检查 3 更新问题后编辑)

对于检查 3，表达式 1 再次仅对 1000 万个项目求和。表达式 2 进行 1000 万次比较并对 500 万个项目求和。由于表达式 2 稍微变慢了，我们可以看到从总和中删除 500 万项所节省的时间比进行 1000 万次比较所花费的时间要少一些。