TSpython 発言

Bruce.です。

機械伯爵 writes:

> > in だと リストかジェネレータが相手になると思うんですが、
> > has_keyはそういうことないんですかね? それとも inでも
> > 違う?
> 
> 　えっと、質問の意味がわかんないのですが、has_keyはマッピング
> 専用の関数ですし、そもそもリストやジェネレータには「長さ」さえ
> あれば、そこまでの数値しかないわけですし・・・

えーとですね、リストを相手にするとなるとリストを生成する手間が
発生し、かつリストを格納するだけのメモリが必要になるので巨大な
辞書相手にはちょっと問題かなー、と思ったわけです。ジェネレータ
だとメモリの問題はないでしょうけど。

また、リスト中から線形に検索するとなると計算量がO(N)になりますが、
辞書がハッシュで実装されていると仮定するならばキーの検索はO(1)で
できますから、その点でも巨大辞書相手にはどうかと。

> 　valuesの中にあるか無いかを拾うだけなら、
> 
> value in dict.values()
> 
> 　や
> 
> value in dict.itervalues()
> 
> 　が使えますが、値は重複が可能なので、値に対応するキーを
> 拾おうと思ったら、なめるしか無いですね（それっぽいメソッド
> は無いみたいですし）

has_keyに対応付けて考えるならば、重複していようがいまいが存在
しているのには間違いないので気にしないでよいのではないかと。
で、

value in dict.values()

と記述したときに、実際にリストをなめて行ってるかどうかが
気になったわけです。

そこで↓こんなスクリプトを書いて実測してみました。
Pythonは初心者なので添削歓迎(^^)

手元の環境では、

has_key:  0.016000032424926758
has_key2: 56.062999963760376

となりました。圧倒的に差がつきましたね。

import random
import time

class random_str:
    def __init__(self, max=20, strlen=10):
        self.length=strlen
        self.max=max
        self.basestr = "ABCDEFGHIJKLNMOPQRSTUVWXYZabcdefghijklmnopqrstrvwxyz"
        random.seed(None)

    def __iter__(self):
        for i in range(self.max):
            s = ""
            baselength = len(self.basestr)
            strlength  = int((self.length-1)*random.random()+1)
            for x in range(strlength):
                s += self.basestr[int(baselength*random.random())]

            yield s
        raise StopIteration

def has_key2(dict, key):
    if key in dict.keys():
        return True
    else:
        return False


dictsize  = 10000
keylenmax = 100
rs = random_str(dictsize, keylenmax)
dict = {}

for str in rs:
    #print str
    dict[str] = True

l = []
rs2 = random_str(dictsize, keylenmax)
for str in rs2:
    l.append(str)

keys = dict.keys()
l += keys

random.shuffle(l)

t1 = time.time()
for x in l:
    dict.has_key(x)

t2 = time.time()
for x in l:
    has_key2(dict, x)

t3 = time.time()

print "has_key:  " + repr(t2-t1)
print "has_key2: " + repr(t3-t2)

いじょ。