Удивительные результаты с Python timeit: Counter() vs defaultdict() vs dict()

Я получил очень удивительные результаты с 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, но что удивительно, так это то, что счетчик работает медленнее, чем defaultdict().

Это ожидается?

РЕДАКТИРОВАТЬ:

Также использование dict быстрее, чем 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().


python python-2.7 counter defaultdict timeit
person BlueTrin    schedule 06.01.2015    source источник

Ответы (1)


arrow_upward
19
arrow_downward

Да, это ожидаемо; конструктор 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, которая обрабатывает этот случай; см. проблема 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)

(Примечание: чтобы получить значимый результат измерения времени, количество итераций было увеличено с 10 000 до 100 000; поэтому, если вы сравните их со случаем dict.get() выше, вам нужно взять время, умноженное на десять, на 1,144 секунды).

person Martijn Pieters    schedule 06.01.2015
comment
С 2020 года при использовании python 3.7 ›= это уже не так — счетчик работает быстрее. - person bones.felipe; 26.10.2020
comment
@bones.felipe, пожалуйста, прочитайте весь ответ. Вопрос был о Python 2.7, но я упоминаю, что с Python 3.2 Counter работает быстрее, так что с 2012 года (8 лет назад). - person Martijn Pieters; 26.10.2020