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（）よりも遅いということです。

これは期待ですか？

EDIT：

また、辞書を使用して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）あなたは読みやすさについてもっと気にしない限り、という意味よりも高速ですdefaultdict（）ではなくdict（）を使うべきです。

Answer 1

はい、これが予想されます。 Counter()コンストラクタは、__missing__に頼るのではなく、self.get()を使用して初期値をロードするCounter.update()を使用します。

また、defaultdict__missing__工場自体はCで実装されてint()ような別のタイプを使用するときに特にCounter源は、純粋のPythonであり、そのようなCounter.__missing__方法として実行するPythonのフレームを必要とする、Cコードで完全に処理されます。

>>> import timeit 
>>> import random 
>>> 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：dict.get()はまだCで処理され

ので、コンストラクタのアプローチは、あなたが同じトリックを最初にローカルとしてCounter.update()用途やエイリアスself.getルックアップを使用提供、Counter()ための速いアプローチですおよびCounterは、その機能のためではなく、パフォーマンスのために構築された有用なクラスです。速くない、まだすることができ__missing__フックに頼っ：

最大速度のためのエイリアス dict.get()方法を使用して、通常の辞書だ

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

。しかし、バッグの振る舞いを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