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 interned x.count(1) 正在使用一个也是列表成员的对象； x[0] is 1 是真的。

count() 的奇怪执行时间

Strange execution times of count()

python

python-3.x

list

performance

python-internals