Pythonタプルがキーとして遅いですか？

Question

辞書のソートされたタプルの高速検索を実装しようとしています。 "タプル（3,8）には関連する値がありますか？そうであれば、それは何ですか？"という質問に答えるものです。タプル内の整数を下から0で、上からmax_intで束縛させます。

私は先に進み、Pythonのdictを使用しましたが、かなり遅いことがわかりました。この問題に対するもう1つのアプローチは、max_int（主に空の）dictsを持つリストTを作成し、各タプル（3,8）に対してT [3] [8] = valueを入れることです。 これはまさにPythonがdictsで取るバケットハッシュのアプローチですが、後者はここでは約30倍（！）高速です。

また、醜いです（特に3タプルを実装しようとしているので特にそうです）。私はここでいくつかのヒントを感謝したいと思います。

参考のために、ここで私はタイミングを取得するために使用されるコードは次のとおりです。

import numpy as np 
import time 

# create a bunch of sorted tuples 
num_tuples = 10 
max_int = 100 
a = np.random.rand(num_tuples,2) * max_int 
a = a.astype(int) 
for k in xrange(len(a)): 
    a[k] = np.sort(a[k]) 

# create dictionary with tuples as keys 
d = {} 
for t in a: 
    d[tuple(t)] = 42 

print d 

# do some lookups 
m = 100000 
start_time = time.time() 
for k in xrange(m): 
    (3,8) in d.keys() 
elapsed = time.time() - start_time 
print elapsed 

# now create the bucket-list structure mentioned above 
t = [{} for k in xrange(max_int)] 
for k in xrange(len(a)): 
    t[a[k][0]][a[k][1]] = 42 

print t 

# do some lookups 
m = 10000 
start_time = time.time() 
for k in xrange(m): 
    8 in t[3].keys() 
elapsed = time.time() - start_time 
print elapsed 

Answer 1

は、Python 2.7での正確なタイミングの結果である：

>>> %timeit (3, 8) in d.keys() # Slow, indeed 
100000 loops, best of 3: 9.58 us per loop 

>>> %timeit 8 in t[3].keys() # Faster 
1000000 loops, best of 3: 246 ns per loop 

>>> %timeit (3, 8) in d # Even faster! 
10000000 loops, best of 3: 117 ns per loop 

>>> %timeit 8 in t[3] # Slightly slower 
10000000 loops, best of 3: 127 ns per loop 

彼らは標準(3, 8) in d（無.keys()リスト建物は）少し速く（以下一般）よりも、実際に8 in t[3]アプローチであり、そして二倍ことを示しています質問の比較的速いとして速いとして。この.keys/no .keysの違いは、(3, 8) in d.keys()がキーのリスト（Python 2で）を作成してから、このリストの(3, 8)を検索します。これは辞書dのハッシュテーブルで(3, 8)を探すよりもはるかに遅いです。

コメント欄で述べたように、タイミング結果は、Python 3と異なっている：inオペレータが対応のハッシュテーブルを使用できるようにPythonの3のkeys()は、キーの代わりに、図keys()返すため高速inテストを有しています辞書。

元の質問の速度の相違は、t[3].keys()と比較して、d.keys()が比較的長いリストを作成するという事実から来ています。

PS：%timeit機能は、優れたIPythonシェルによって提供されます。元のプログラムは%run prog.pyのIPythonで実行できます。

Answer 2

あなたが異なる値に対してテストしています。辞書版では、100,000個のキーが検索されますが、バケットリスト構造では、検索は10,000個のキーだけになります。

(3,8) in d.keys()ちょうど(3,8) in dを書き込んだ場合、このコードスニペットでは処理が遅くなりますが、両方のバージョンの参照時間はかなり似ていますが、その差はごくわずかです。この修正されたテストを試してみて、自分の目で確かめてください：観察された挙動のため

import numpy as np 
import time 

# create a bunch of sorted tuples 
num_tuples = 10 
max_int = 100 
a = np.random.rand(num_tuples,2) * max_int 
a = a.astype(int) 
for k in xrange(len(a)): 
    a[k] = np.sort(a[k]) 

# create dictionary with tuples as keys 
d = {} 
for t in a: 
    d[tuple(t)] = 42 

# do some lookups 
m = 100000 
start_time = time.time() 
for k in xrange(m): 
    if (3,8) in d: 
     pass 

elapsed = time.time() - start_time 
print elapsed 

# now create the bucket-list structure mentioned above 
t = [{} for k in xrange(max_int)] 
for k in xrange(len(a)): 
    t[a[k][0]][a[k][1]] = 42 

# do some lookups 
m = 100000 
start_time = time.time() 
for k in xrange(m): 
    if 8 in t[3]: 
     pass 

elapsed = time.time() - start_time 
print elapsed 

理由は(3,8) in d.keys()と8 in t[3].keys()両方が毎回新しいキーの一時リストを作成しているが、2番目のバージョンは短いリストを作成することです。単にイディオムkey in dictionaryを使用していた場合、一時的なリストは作成されなくなり、両方のアプローチでパフォーマンスが同様に見えるようになります。

私は最初のバージョンに行きました、はるかに簡単で、読みやすく、理解しやすく、慣用であり、正しく使用すると、2番目のバージョンと同様に動作します。ここで

Answer 3

(a, b) in dの速度をb in t[a]と比較するのはちょっと奇妙です。後者はaが存在しなければならないと仮定しているためです。

いずれにしても、最初の方法は常に高速にする必要があります。どちらのバージョンもととbの両方を持っています。最初のものは、タプルを割り当ててハッシュする追加のオーバーヘッドがあります。しかし、2番目の方法は2つの別々の辞書検索を行います。