为什么“for”循环在计算真值时如此快？

Question

我最近回答了一个question on a sister site，它要求一个对一个数字的所有偶数位数进行计数的函数。其中一个other answers包含两个函数（到目前为止，这是最快的）：

def count_even_digits_spyr03_for(n):
    count = 0
    for c in str(n):
        if c in "02468":
            count += 1
    return count

def count_even_digits_spyr03_sum(n):
    return sum(c in "02468" for c in str(n))

此外，我还研究了使用列表理解和list.count：

^{pr2}$

前两个函数本质上是相同的，只是第一个函数使用显式计数循环，而第二个函数使用内置的sum。我本以为第二个会更快（基于例如this answer），如果要求复查的话，我会建议把前者变成这样。但是，事实恰恰相反。用一些位数不断增加的随机数进行测试（因此任何一个数字为偶数的概率约为50%），我得到以下计时：

{为什么手动循环要快得多？它几乎比使用sum快一倍。由于内置的sum应该比手动求和列表快5倍（根据the linked answer），这意味着它实际上要快十倍！只需为一半的值添加一个值，而另一半被丢弃，这是否足以解释这种差异？在

---

使用if作为过滤器，如下所示：

def count_even_digits_spyr03_sum2(n):
    return sum(1 for c in str(n) if c in "02468")

只将计时改进到与列表理解相同的级别。在

---

当将计时扩展到更大的数字，并规范化为for循环计时时，它们会渐进地收敛到非常大的数字（>10k位），这可能是由于str(n)所花费的时间：

Answer 1

如果我们使用dis.dis()，我们可以看到函数的实际行为。在

count_even_digits_spyr03_for()：

  7           0 LOAD_CONST               1 (0)
              3 STORE_FAST               0 (count)

  8           6 SETUP_LOOP              42 (to 51)
              9 LOAD_GLOBAL              0 (str)
             12 LOAD_GLOBAL              1 (n)
             15 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             18 GET_ITER
        >>   19 FOR_ITER                28 (to 50)
             22 STORE_FAST               1 (c)

  9          25 LOAD_FAST                1 (c)
             28 LOAD_CONST               2 ('02468')
             31 COMPARE_OP               6 (in)
             34 POP_JUMP_IF_FALSE       19

 10          37 LOAD_FAST                0 (count)
             40 LOAD_CONST               3 (1)
             43 INPLACE_ADD
             44 STORE_FAST               0 (count)
             47 JUMP_ABSOLUTE           19
        >>   50 POP_BLOCK

 11     >>   51 LOAD_FAST                0 (count)
             54 RETURN_VALUE

我们可以看到只有一个函数调用，在开头是对str()：

^{pr2}$

其余部分是高度优化的代码，使用跳转、存储和就地添加。在

什么是count_even_digits_spyr03_sum()：

 14           0 LOAD_GLOBAL              0 (sum)
              3 LOAD_CONST               1 (<code object <genexpr> at 0x10dcc8c90, file "test.py", line 14>)
              6 LOAD_CONST               2 ('count2.<locals>.<genexpr>')
              9 MAKE_FUNCTION            0
             12 LOAD_GLOBAL              1 (str)
             15 LOAD_GLOBAL              2 (n)
             18 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             21 GET_ITER
             22 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             25 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             28 RETURN_VALUE

虽然我不能完美地解释这些差异，但是我们可以清楚地看到有更多的函数调用（可能是sum()和{}（？），这使得代码的运行速度比直接执行机器指令慢得多。在

Answer 2

@MarkusMeskanen的答案是正确的-函数调用很慢，genexpr和listcomp基本上都是函数调用。在

总之，要务实：

使用str.count(c)更快，this related answer of mine about ^{} in Python可以使事情更快。在

def count_even_digits_spyr03_count(n):
    s = str(n)
    return sum(s.count(c) for c in "02468")


def count_even_digits_spyr03_count_unrolled(n):
    s = str(n)
    return s.count("0") + s.count("2") + s.count("4") + s.count("6") + s.count("8")

结果：

^{pr2}$

Answer 3

sum相当快，但{}并不是减速的原因。导致经济放缓的主要因素有三：

• 使用生成器表达式会导致持续暂停和恢复生成器的开销。在
• 生成器版本无条件地添加，而不是仅当数字为偶数时。当数字是奇数时，这个更贵。在
• 添加布尔值而不是整数可以防止sum使用其整数快速路径。在

---

与列表理解相比，生成器有两个主要优点：它们占用更少的内存；如果不需要所有元素，它们可以提前终止。它们的设计目的是在需要所有元素的情况下提供时间优势。每个元素暂停和恢复一个生成器非常昂贵。在

如果我们用列表理解代替genexp：

In [66]: def f1(x):
   ....:     return sum(c in '02468' for c in str(x))
   ....: 
In [67]: def f2(x):
   ....:     return sum([c in '02468' for c in str(x)])
   ....: 
In [68]: x = int('1234567890'*50)
In [69]: %timeit f1(x)
10000 loops, best of 5: 52.2 µs per loop
In [70]: %timeit f2(x)
10000 loops, best of 5: 40.5 µs per loop

我们看到了一个立即加速，代价是在一个列表上浪费大量内存。在

---

如果你看看你的genexp版本：

^{pr2}$

你会发现它没有if。它只会将布尔值放入sum。相反，你的循环：

def count_even_digits_spyr03_for(n):
    count = 0
    for c in str(n):
        if c in "02468":
            count += 1
    return count

只有在数字为偶数时才添加任何内容。在

如果我们将前面定义的f2更改为同时包含一个if，我们会看到另一个加速：

In [71]: def f3(x):
   ....:     return sum([True for c in str(x) if c in '02468'])
   ....: 
In [72]: %timeit f3(x)
10000 loops, best of 5: 34.9 µs per loop

f1，与您的原始代码相同，耗时52.2µs，f2，只需修改列表理解，就需要40.5µs

---

使用True而不是f3中的1可能看起来相当尴尬。这是因为将其更改为1会激活最后一个加速。sum对整数有一个fast path，但是快速路径只对类型正好是int的对象激活。bool不计算。这是检查项目是否属于int类型的行：

if (PyLong_CheckExact(item)) {

完成最后的更改后，将True更改为1：

In [73]: def f4(x):
   ....:     return sum([1 for c in str(x) if c in '02468'])
   ....: 
In [74]: %timeit f4(x)
10000 loops, best of 5: 33.3 µs per loop

我们看到最后一个小的加速。在

---

那么在所有这些之后，我们是否打破了显式循环？在

In [75]: def explicit_loop(x):
   ....:     count = 0
   ....:     for c in str(x):
   ....:         if c in '02468':
   ....:             count += 1
   ....:     return count
   ....: 
In [76]: %timeit explicit_loop(x)
10000 loops, best of 5: 32.7 µs per loop

没有。我们基本上已经收支平衡，但我们还没赢。剩下的最大问题是名单。构建它非常昂贵，sum必须通过列表迭代器来检索元素，这有其自身的成本（尽管我认为这部分相当便宜）。不幸的是，只要我们使用测试数字和call-sum方法，就没有任何好的方法来删除列表。显式循环获胜。在

我们能再进一步吗？到目前为止，我们一直在努力使sum更接近显式循环，但是如果我们坚持这个愚蠢的列表，我们可以脱离显式循环，只调用len而不是{}：

def f5(x):
    return len([1 for c in str(x) if c in '02468'])

单独测试数字并不是我们可以尝试打破循环的唯一方法。进一步偏离显式循环，我们还可以尝试str.count。str.count直接在C语言中遍历字符串的缓冲区，避免了很多包装对象和间接寻址。我们需要调用它5次，在字符串上传递5次，但它仍然有回报：

def f6(x):
    s = str(x)
    return sum(s.count(c) for c in '02468')

不幸的是，这是我用来计时的网站因为使用了太多的资源而被困在“tarpit”中，所以我不得不切换站点。以下时间不能与上述时间直接比较：

>>> import timeit
>>> def f(x):
...     return sum([1 for c in str(x) if c in '02468'])
... 
>>> def g(x):
...     return len([1 for c in str(x) if c in '02468'])
... 
>>> def h(x):
...     s = str(x)
...     return sum(s.count(c) for c in '02468')
... 
>>> x = int('1234567890'*50)
>>> timeit.timeit(lambda: f(x), number=10000)
0.331528635986615
>>> timeit.timeit(lambda: g(x), number=10000)
0.30292080697836354
>>> timeit.timeit(lambda: h(x), number=10000)
0.15950968803372234
>>> def explicit_loop(x):
...     count = 0
...     for c in str(x):
...         if c in '02468':
...             count += 1
...     return count
... 
>>> timeit.timeit(lambda: explicit_loop(x), number=10000)
0.3305045129964128