frozensetの性能との比較

Question

私は、Pythonのsetとfrozensetのコレクションタイプを手直ししていました。

当初は、frozensetは、setよりも優れた検索パフォーマンスを提供すると仮定していましたが、これは変更不可能であり、したがって保存されたアイテムの構造を悪用する可能性があります。

> pypy set.py 100000000 
set  : 6.156 
frozenset: 6.166 

> python set.py 100000000 
set  : 16.824 
frozenset: 17.248 

：私は以下の結果を与えはCPythonとPyPyの両方を使用してこのコードを、実行

import random 
import time 
import sys 

def main(n): 
    numbers = [] 
    for _ in xrange(n): 
     numbers.append(random.randint(0, sys.maxint)) 
    set_ = set(numbers) 
    frozenset_ = frozenset(set_) 

    start = time.time() 
    for number in numbers: 
     number in set_ 
    set_duration = time.time() - start 

    start = time.time() 
    for number in numbers: 
     number in frozenset_ 
    frozenset_duration = time.time() - start 

    print "set  : %.3f" % set_duration 
    print "frozenset: %.3f" % frozenset_duration 


if __name__ == "__main__": 
    n = int(sys.argv[1]) 
    main(n) 

：

しかし、これは以下の実験に関しては、ケースであるようには見えません実際にはfrozensetはCPythonとPyPyの両方でルックアップのパフォーマンスが遅くなっているようです。なぜこれが当てはまるのか誰もが知っていますか？私は実装を調べなかった。

Answer 1

frozensetとsetの実装は大部分が共有されています。 setは、ちょうどfrozensetであり、まったく同じハッシュテーブルの実装で、変更メソッドが追加されています。 Objects/setobject.c source fileを参照してください。最上位のPyFrozenSet_Type definitionはPySet_Type definitionと機能します。

メンバーシップのテスト時にののにハッシュを計算する必要がないため、ここではフロゼンセットの最適化はありません。 をに対してテストするために使用するアイテムは、ハッシュ計算を依然として計算する必要があります。これにより、ハッシュテーブルに正しいスロットが見つかるようになり、同等のテストができるようになります。

このように、システムで実行中の他のプロセスが原因でタイミング結果がオフになっている可能性があります。ウォールクロックの時間を測定し、Pythonのガベージコレクションを無効にしたり、同じことを繰り返しテストしたりしませんでした。これは、各テスト1万回を繰り返し、生成

import random 
import sys 
import timeit 

numbers = [random.randrange(sys.maxsize) for _ in range(10000)] 
set_ = set(numbers) 
fset = frozenset(numbers) 
present = random.choice(numbers) 
notpresent = -1 
test = 'present in s; notpresent in s' 

settime = timeit.timeit(
    test, 
    'from __main__ import set_ as s, present, notpresent') 
fsettime = timeit.timeit(
    test, 
    'from __main__ import fset as s, present, notpresent') 

print('set  : {:.3f} seconds'.format(settime)) 
print('frozenset: {:.3f} seconds'.format(fsettime)) 

：

set  : 0.050 seconds 
frozenset: 0.050 seconds