python教程—为什么for循环计算真值要快得多?-Python实用宝典

python教程—为什么for循环计算真值要快得多?

最近,我在一个姐妹网站上回答了一个问题,该网站要求提供一种计算所有偶数位数的功能。另一个答案包含两个功能(这是迄今为止最快的):

我最近在一个姐妹站点上回答了一个问题,该站点要求提供一个函数来计算一个数字的所有偶数位。其中一个其他答案包含两个函数(这是迄今为止最快的):

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

此外,我还查看了使用列表理解和列表。

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

前两个函数本质上是相同的,只是第一个函数使用显式计数循环,而第二个函数使用内置的sum。我本以为第二个会更快(基于https://stackoverflow.com/a/24578976/4042267”这个答案),但是,事实证明恰恰相反。我用一些随机数来测试它,这些随机数的位数越来越多(所以任何一位数字偶数的概率大约是50%),我得到了以下时间:

为什么for循环计算真值要快得多?这意味着它实际上快了10倍!只需要为一半的值向计数器添加一个值(因为另一半值被丢弃)所节省的时间是否足以解释这种差异?


使用if作为过滤器,如下所示:

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

只将计时提高到与列表理解相同的级别。


当将计时扩展到较大的数字,并将其规范化为for循环计时时,它们对于非常大的数字(>10k位)渐进收敛,这可能是由于str(n)花费的时间:

为什么for循环计算真值要快得多?

答案

sum速度很快,但是sum并不是导致速度放缓的原因。放缓的主要原因有三个:

  • 使用生成器表达式会产生不断暂停和恢复生成器的开销。
  • 您的生成器版本无条件地添加,而不是仅当数字为偶数时才添加。当数字是奇数时,这将非常消耗资源。
  • 添加布尔值而不是int值可以防止sum使用其整数快速路径。

与列表解析式相比,生成器提供了两个主要优势:它们占用的内存少得多,如果不需要所有元素,它们可以提前终止。它在所有元素都需要使用的情况下并没有优势,因为每次暂停和恢复一次生成器的代价非常昂贵

如果我们用列表解析式代替生成器:

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

你看,这个加速非常地明显

你会发现它没有if。它只是把布尔值代入求和。相比之下,你的循环:

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

只有当数字是偶数时,才count + 1,缺点是每次都要判断.

如果我们改变之前定义的f2,让它在列表解析式后判断数字是否为偶数,是偶数才会成为最终生成的列表中的一员,这样有另一个加速:

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,f3增加了if,只花了34.9µs,而且还能更快哦。


在f3中使用True而不是1可能看起来很尴尬。这是因为将它改为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。count在C语言中直接遍历字符串的缓冲区,避免了很多包装器对象之类的间接操作。我们需要调用它5次,在字符串上传递5次,但它仍然有回报:

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

以下时间与我们上述测试得到的时间其实不可直接比较,但是你可以看到还是有效果的:

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

​Python实用宝典 (pythondict.com)
不只是一个宝典
欢迎关注公众号:Python实用宝典

本文由 Python实用宝典 作者:Python实用宝典 发表,其版权均为 Python实用宝典 所有,文章内容系作者个人观点,不代表 Python实用宝典 对观点赞同或支持。如需转载,请注明文章来源。
0

发表评论