Python timeit 的惊人结果：Counter() vs defaultdict() vs dict()

Question

我用 timeit 得到了非常令人惊讶的结果，如果我做错了什么，有人能告诉我吗？我正在使用 Python 2.7.

这是文件 speedtest_init.py 的内容：

import random

to_count = [random.randint(0, 100) for r in range(60)]

这些是speedtest.py的内容：

__author__ = 'BlueTrin'

import timeit

def test_init1():
    print(timeit.timeit('import speedtest_init'))

def test_counter1():
    s = """\
    d = defaultdict(int);
    for i in speedtest_init.to_count:
        d[i] += 1
    """
    print(timeit.timeit(s, 'from collections import defaultdict; import speedtest_init;'))

def test_counter2():
    print(timeit.timeit('d = Counter(speedtest_init.to_count);', 'from collections import Counter; import speedtest_init;'))


if __name__ == "__main__":
    test_init1()
    test_counter1()
    test_counter2()

控制台输出为：

C:\Python27\python.exe C:/Dev/codility/chlorum2014/speedtest.py
2.71501962931
65.7090444503
91.2953839048

Process finished with exit code 0

我认为默认情况下 timeit() 运行 1000000 次代码，所以我需要将次数除以 1000000，但令人惊讶的是 Counter 比 defaultdict() 慢。

这是预期的吗？

编辑：

同样使用字典比默认字典（int）更快：

def test_counter3():
    s = """\
    d = {};
    for i in speedtest_init.to_count:
        if i not in d:
            d[i] = 1
        else:
            d[i] += 1
    """
    print(timeit.timeit(stmt=s, setup='from collections import defaultdict; import speedtest_init;')

最后一个版本比 defaultdict(int) 更快，这意味着除非您更关心可读性，否则您应该使用 dict() 而不是 defaultdict()。

Answer 1

是的，这是预料之中的； Counter() 构造函数 使用 Counter.update() ，它使用 self.get() 加载初始值而不是依赖 __missing__.

此外，defaultdict __missing__ 工厂完全用 C 代码处理，尤其是在使用另一种类型时，例如 int()，它本身是用 C 实现的。Counter源是纯 Python，因此 Counter.__missing__ 方法需要 Python 框架才能执行。

因为 dict.get() 仍然在 C 中处理，构造函数方法是 Counter() 的更快方法，前提是您使用相同的技巧 Counter.update() 使用和别名 self.get 首先作为本地查找：

>>> import timeit
>>> import random
>>> import sys
>>> sys.version_info
sys.version_info(major=2, minor=7, micro=9, releaselevel='final', serial=0)
>>> to_count = [random.randint(0, 100) for r in range(60)]
>>> timeit.timeit('for i in to_count: c[i] += 1',
...               'from collections import Counter; from __main__ import to_count; c = Counter()',
...               number=10000)
0.2510359287261963
>>> timeit.timeit('for i in to_count: c[i] = c_get(i, 0) + 1',
...               'from collections import Counter; from __main__ import to_count; c = Counter(); c_get = c.get',
...               number=10000)
0.20978617668151855

defaultdict 和 Counter 都很有帮助类为它们的功能而构建，而不是它们的性能；不依赖 __missing__ 钩子会更快：

>>> timeit.timeit('for i in to_count: d[i] = d_get(i, 0) + 1',
...               'from __main__ import to_count; d = {}; d_get = d.get',
...               number=10000)
0.11437392234802246

这是一个使用别名 dict.get() 方法以获得最大速度的常规词典。但随后您还必须重新实现 Counter 或 Counter.most_common() 方法的包行为。 defaultdict 用例数不胜数。

在 Python 3.2 中，更新 Counter() 通过添加处理这种情况的 C 库来提高速度；参见 issue 10667。在 Python 3.4 上测试，Counter() 构造函数现在击败别名 dict.get 案例：

>>> timeit.timeit('Counter(to_count)',
...               'from collections import Counter; from __main__ import to_count',
...               number=100000)
0.8332311600097455
>>> timeit.timeit('for i in to_count: d[i] = d_get(i, 0) + 1',
...               'from __main__ import to_count; d = {}; d_get = d.get',
...               number=100000)
0.961191965994658
>>> import sys
>>> sys.version_info
sys.version_info(major=3, minor=4, micro=2, releaselevel='final', serial=0)

（注意：为了获得有意义的计时结果，迭代次数从 10k 增加到 100k；因此，如果您将这些与上面的 dict.get() 情况进行比较，您需要将计时时间乘以十，在1.144 秒）。

Python timeit 的惊人结果：Counter() vs defaultdict() vs dict()

Surprising results with Python timeit: Counter() vs defaultdict() vs dict()

python

python-2.7

counter

timeit

defaultdict