为什么`for`循环这么快才能计算True值？

Question

我最近在一个姐妹网站上回答了一个问题，该问题要求一种功能来计算数字的所有偶数位。其中的其他的答案中包含两个功能（这被证明是最快的，至今）：

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：

def count_even_digits_spyr03_list(n):
    return [c in "02468" for c in str(n)].count(True)

前两个函数基本相同，除了第一个函数使用显式的计数循环，而第二个函数使用内建的sum。我本来希望第二个更快（基于此答案），这是我建议将第二个变成要求审查的东西。但是，事实证明是相反的。用一些数字递增的随机数对其进行测试（因此，任何一位数字的偶数概率约为50％），我得到以下计时：

为什么手动for循环这么快？比使用快将近两倍sum。而且由于内置功能sum应该比手动汇总列表大约快五倍（根据链接的答案），这意味着它实际上要快十倍！是否因为只需要将一半的​​值添加到计数器而节省了费用，因为另一半被丢弃了，足以说明这种差异？

---

使用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

sum速度非常快，但这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版本：

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

您会看到它没有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代替1in 可能看起来很尴尬f3。那是因为将其更改为1激活一个最终加速。sum有一个快速路径为整数，但在快速路径只有激活的对象，它的类型是完全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必须通过列表迭代器来检索元素，而元素有其自身的成本（尽管我认为那部分很便宜）。不幸的是，只要我们经历了测试数字和通话sum方法，我们就没有摆脱列表的任何好方法。显式循环获胜。

反正我们可以走得更远吗？好吧，sum到目前为止，我们一直在尝试使显式循环更接近，但是如果我们坚持使用这个愚蠢的列表，我们可以脱离显式循环，而只需调用len而不是sum：

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

Answer 2

如果使用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()在开始时：

9 LOAD_GLOBAL              0 (str)
...
15 CALL_FUNCTION            1 (1 positional, 0 keyword pair)

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

结果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()和in（？）），它使代码不是直接执行的机器指令慢得多运行。

Answer 3

@MarkusMeskanen的答案正确无误–函数调用很慢，genexprs和listcomps基本上都是函数调用。

无论如何，要务实：

使用str.count(c)速度更快，而我strpbrk()在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")

结果：

string length: 502
count_even_digits_spyr03_list 0.04157966522
count_even_digits_spyr03_sum 0.05678154459
count_even_digits_spyr03_for 0.036128606150000006
count_even_digits_spyr03_count 0.010441866129999991
count_even_digits_spyr03_count_unrolled 0.009662931009999999

Answer 4

实际上，有一些差异会导致观察到的性能差异。我的目标是对这些差异进行高层次的概述，但尽量不要过多介绍低层次的细节或可能的改进。对于基准测试，我使用自己的软件包simple_benchmark。

生成器与for循环

生成器和生成器表达式是语法糖，可用来代替编写迭代器类。

当您编写类似的生成器时：

def count_even(num):
    s = str(num)
    for c in s:
        yield c in '02468'

或生成器表达式：

(c in '02468' for c in str(num))

它将（在幕后）转换为可通过迭代器类访问的状态机。最后，它大致相当于（尽管生成器周围生成的实际代码会更快）：

class Count:
    def __init__(self, num):
        self.str_num = iter(str(num))

    def __iter__(self):
        return self

    def __next__(self):
        c = next(self.str_num)
        return c in '02468'

因此，生成器将始终具有一个附加的间接层。这意味着前进生成器（或生成器表达式或迭代器）意味着您调用__next__由生成器生成的迭代器，生成器本身会调用__next__您实际要迭代的对象。但这也有一些开销，因为您实际上需要创建一个额外的“迭代器实例”。通常，如果您在每次迭代中都进行大量操作，则这些开销可以忽略不计。

仅举一个例子，与手动循环相比，生成器会产生多少开销：

import matplotlib.pyplot as plt
from simple_benchmark import BenchmarkBuilder
%matplotlib notebook

bench = BenchmarkBuilder()

@bench.add_function()
def iteration(it):
    for i in it:
        pass

@bench.add_function()
def generator(it):
    it = (item for item in it)
    for i in it:
        pass

@bench.add_arguments()
def argument_provider():
    for i in range(2, 15):
        size = 2**i
        yield size, [1 for _ in range(size)]

plt.figure()
result = bench.run()
result.plot()

生成器与列表推导

生成器的优点是它们不创建列表，而是“生成”值。因此，尽管生成器具有“迭代器类”的开销，但它可以节省用于创建中间列表的内存。这是速度（列表理解）和内存（生成器）之间的权衡。关于StackOverflow的各种帖子对此进行了讨论，因此在这里我不想进一步详细介绍。

import matplotlib.pyplot as plt
from simple_benchmark import BenchmarkBuilder
%matplotlib notebook

bench = BenchmarkBuilder()

@bench.add_function()
def generator_expression(it):
    it = (item for item in it)
    for i in it:
        pass

@bench.add_function()
def list_comprehension(it):
    it = [item for item in it]
    for i in it:
        pass

@bench.add_arguments('size')
def argument_provider():
    for i in range(2, 15):
        size = 2**i
        yield size, list(range(size))

plt.figure()
result = bench.run()
result.plot()

sum 应该比手动迭代更快

是的，sum确实比显式的for循环快。特别是如果您遍历整数。

import matplotlib.pyplot as plt
from simple_benchmark import BenchmarkBuilder
%matplotlib notebook

bench = BenchmarkBuilder()

@bench.add_function()
def my_sum(it):
    sum_ = 0
    for i in it:
        sum_ += i
    return sum_

bench.add_function()(sum)

@bench.add_arguments()
def argument_provider():
    for i in range(2, 15):
        size = 2**i
        yield size, [1 for _ in range(size)]

plt.figure()
result = bench.run()
result.plot()

字符串方法与任何类型的Python循环

要了解使用类似于str.count循环（显式或隐式）之类的字符串方法时的性能差异，在于Python中的字符串实际上是作为值存储在（内部）数组中的。这意味着循环实际上不会调用任何__next__方法，它可以直接在数组上使用循环，这将大大加快速度。但是，它还在字符串上强加了一个方法查找和一个方法调用，这就是为什么对于很短的数字它会更慢的原因。

只是为了提供一个小的比较，迭代字符串需要多长时间与Python迭代内部数组需要多长时间：

import matplotlib.pyplot as plt
from simple_benchmark import BenchmarkBuilder
%matplotlib notebook

bench = BenchmarkBuilder()

@bench.add_function()
def string_iteration(s):
    # there is no "a" in the string, so this iterates over the whole string
    return 'a' in s  

@bench.add_function()
def python_iteration(s):
    for c in s:
        pass

@bench.add_arguments('string length')
def argument_provider():
    for i in range(2, 20):
        size = 2**i
        yield size, '1'*size

plt.figure()
result = bench.run()
result.plot()

在此基准测试中，让Python对字符串进行迭代比使用for循环对字符串进行迭代要快200倍左右。

为什么它们都收敛为大数？

这实际上是因为数字到字符串的转换将在那里占主导地位。因此，对于非常大的数字，您实际上只是在测量将该数字转换为字符串所花费的时间。

如果将带数字的版本与带转换后的数字的版本进行比较，就会看到差异（我在这里使用另一个答案中的函数来说明这一点）。左边是数字基准，右边是采用字符串的基准-两个图的y轴也相同：

如您所见，对于带数字的字符串，使用函数的基准测试要比将数字转换为字符串并将其转换为字符串的函数的基准要快得多。这表明字符串转换是大数字的“瓶颈”。为了方便起见，我还包括一个基准，仅将字符串转换为左图（对于大数而言，这将变得显着/显着）。

%matplotlib notebook

from simple_benchmark import BenchmarkBuilder
import matplotlib.pyplot as plt
import random

bench1 = BenchmarkBuilder()

@bench1.add_function()
def f1(x):
    return sum(c in '02468' for c in str(x))

@bench1.add_function()
def f2(x):
    return sum([c in '02468' for c in str(x)])

@bench1.add_function()
def f3(x):
    return sum([True for c in str(x) if c in '02468'])    

@bench1.add_function()
def f4(x):
    return sum([1 for c in str(x) if c in '02468'])

@bench1.add_function()
def explicit_loop(x):
    count = 0
    for c in str(x):
        if c in '02468':
            count += 1
    return count

@bench1.add_function()
def f5(x):
    s = str(x)
    return sum(s.count(c) for c in '02468')

bench1.add_function()(str)

@bench1.add_arguments(name='number length')
def arg_provider():
    for i in range(2, 15):
        size = 2 ** i
        yield (2**i, int(''.join(str(random.randint(0, 9)) for _ in range(size))))


bench2 = BenchmarkBuilder()

@bench2.add_function()
def f1(x):
    return sum(c in '02468' for c in x)

@bench2.add_function()
def f2(x):
    return sum([c in '02468' for c in x])

@bench2.add_function()
def f3(x):
    return sum([True for c in x if c in '02468'])    

@bench2.add_function()
def f4(x):
    return sum([1 for c in x if c in '02468'])

@bench2.add_function()
def explicit_loop(x):
    count = 0
    for c in x:
        if c in '02468':
            count += 1
    return count

@bench2.add_function()
def f5(x):
    return sum(x.count(c) for c in '02468')

@bench2.add_arguments(name='number length')
def arg_provider():
    for i in range(2, 15):
        size = 2 ** i
        yield (2**i, ''.join(str(random.randint(0, 9)) for _ in range(size)))

f, (ax1, ax2) = plt.subplots(1, 2, sharey=True)
b1 = bench1.run()
b2 = bench2.run()
b1.plot(ax=ax1)
b2.plot(ax=ax2)
ax1.set_title('Number')
ax2.set_title('String')