python - count() 的奇怪执行时间

Question

代码:

from timeit import Timer
print(min(Timer('y=x.count(1)',setup='x=[1] * 1000').repeat(number=1000000))) 
print(min(Timer('y=x.count(0)',setup='x=[1] * 1000').repeat(number=1000000)))

我机器上的结果:

0.7033228789223358
10.16116041096393

谁能解释为什么第一个案例比第二个案例快得多？我预计两次都会相似。

Answer 1

这是由于您构建列表对象的方式造成的:

x = [1] * 1000    

这将创建一个仅包含一个对象的列表，并被引用 1000 次；列表乘法不会创建值的副本。为了理解为什么这很重要，我们需要看看 Python 列表如何进行计数。

list.count() 循环可以如下所示，这是实现的快速 Python 翻译 written in C :

def count(self, value):
    count = 0
    for elem in self:
        if elem == value:
            count += 1
    return count

这很简单，对吧？然而，事实并非如此。实际代码使用 PyObject_RichCompareBool()，其中 first tests for object identity 。确实如此:

if elem is value or elem == value:

当所有列表元素都是同一个对象时，身份测试(简单的指针相等性测试)会快得多:

>>> import random
>>> v = random.randint(1000, 100000000)
>>> x = [v] * 1000
>>> all(value is v for value in x)
True

您可以使用任何随机值重现此内容:

>>> from timeit import Timer
min(Timer('y=x.count(v)',setup='import random; v = random.randint(1000, 10000000); x=[v] * 1000').repeat(number=100000))
0.2716284029884264
>>> min(Timer('y=x.count(w)',setup='import random; v = random.randint(1000, 10000000); x=[v] * 1000; w = v + 1').repeat(number=100000))
1.0827720829984173

正如这些数字所示，在测试值相等性之前进行简单的指针比较是很有意义的。这正是 Python 实现实习生某些经常重用的值的原因，例如小整数 ( those between -5 and 256, inclusive ) 或也是有效 Python 标识符的字符串值。

如果你没有在这里使用一个小整数作为x.count()的参数，它就不会起作用； 因为 1 实习了 x.count(1) 使用的对象也是列表的成员； x[0] 为 1 为 true。