dictでキーの存在有無を確認する方法について

Question

疑問

pythonではマッピング型の組み込みはdictです。
キーが含まれているかどうかの判定は以下のどちらでやるのが適切なのでしょうか？

#1
b = key in dict.keys()
#2
b = key in dict

そう思った理由はたまに方法として#1の方法を紹介しているサイトがあるからです。

速度検証

動きが同じなら速度で見るのが良いかと思い、速度を測ってみました。

検証コード

import time
from math import sqrt

mean=lambda list: sum(list)/len(list)
def stdev(list):
    avg = mean(list)
    return sqrt(sum([(x-avg)*(x-avg) for x in list])/(len(list)-1))

N=1000000
REP=100
dic = {float(x):float(x) for x in range(N)}

def func(f):
    sum = 0
    start = time.time()
    for i in range(N):
        sum += f(i)
    end = time.time()
    if sum != N:
        raise Exception
    return end - start 

def func2(f):
    times = [func(f) for i in range(REP)]
    print(str(mean(times)) + "\t" + str(stdev(times)))
    
func2(lambda x: x in dic)
keys = dic.keys()
func2(lambda x: x in keys)
func2(lambda x: x in dic.keys())

※hayataka2049さんの回答より、dic.keys()を事前に計算する方式を追加。ついでに測定回数を100回にし、平均と標準偏差を出した。

検証結果

####測定環境

項目	値
Host OS	Windows 10 Home 10.0.18362.535
VM	VirtualBox 6.0.14 r133895 (Qt5.6.2)
Guest OS	Ubuntu 19.04
Kernel	5.0.0-37-generic #40-Ubuntu SMP Thu Nov 14 00:14:01 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
CPU	AMD Ryzen 5 1400 3.2GHz

####測定結果

Python実装	バージョン	#1(毎回keys())	#1(固定keys)	#2	補足
CPython	2.7.16	(計測断念)	(計測断念)	0.166±0.005	-
CPython	3.7.3	0.1888±0.005	0.150±0.005	0.147±0.004	-
PyPy	2.7.13	(計測断念)	(計測断念)	0.069±0.003	docker使用
PyPy	3.6.9	0.084±0.004	0.074±0.005	0.070±0.004	docker使用
Cython	3.7.3	0.157±0.010	0.109±0.003	0.107±0.004	Jupyter Notebook使用

単位: 秒
測定回数: 100

####考察
バージョンに依らず、#2の方法が速いように見える

質問

dictにキーが含まれているかどうかの判定はどのようにやるのが、適切なのでしょうか？
なるべく正確な理由を添えて教えて下さい

※あまりに不正確と思ったときは低評価にします
※質問内容は時間内なら訂正要求に応じて随時訂正しますが、追記などの手段は取りません
※日本時間2019年12月27日正午以降ベストアンサー選択を含め、いかなる更新もしません
※いかなる場合も自己解決はしません

Answer 1

その二つの式自体は、基本的に同じ結果になります。

dict.keysでは辞書ビューオブジェクトが得られ、それに対して帰属判定を行うことになります。

key in d

d がキー key を持っていれば True を、そうでなければ、 False を返します。

組み込み型 — Python 3.8.1 ドキュメント

　

x in dictview

x が元の辞書のキー、値、または項目 (項目の場合、 x は (key, value) タプルです) にあるとき True を返します。

組み込み型 — Python 3.8.1 ドキュメント

dict.keysメソッドの呼び出しには多少のオーバーヘッドが伴います。帰属判定のために新たに辞書ビューオブジェクトを生成するのがさしあたり最大の負担でしょう。

これがなければ、帰属判定自体は互角のスピードで行うことができるようです。

>>> # python3.6, linux 
>>> d = {x:None for x in range(10000)}
>>> import timeit
>>> timeit.timeit(lambda : "a" in d)
0.12786398804746568
>>> timeit.timeit(lambda : "a" in d.keys())
0.20240118994843215
>>> ks = d.keys()
>>> timeit.timeit(lambda : "a" in ks)
0.11665043595712632

ということで、基本的には記述が簡潔で速度も申し分ないkey in dictを用いればよいかと思います。

Comments

[dameo]

回答ありがとうございます。確認/質問が2件あります。

(1)CPythonの3.6～あたりでは、x in dicではdictviewが生成されず、x in dic.keys()ではdictviewが生成される分コストが高くなるため、x in dicの方が良いという理解でいいですか？
(2)またpythonの仕様とは、ご提示頂いたリンク先以上に詳しいものはないのでしょうか？

以下感想です。
d.keys()単独の速度を計測した方がいいかもですね。
オーダーレベルの速度比較は簡単にそういう測り方でもいいと思いますが、ハッシュテーブルの実装を考えると、存在しないキーの比較はハッシュが衝突した場合の比較処理が走らないので、やや不公平感があります。

[hayataka2049]

(1)はい。これ以外の仕組みにはしようがないはずなので、たぶん他のバージョンでも同じでは（組み込み型だから、もしかしたらいずれ最適化されてしまうかもしれませんが）。
(2)仕様ということならdocs.python.orgが一番詳しいかと。あとは、たまにこっちでは文書化されていないけどPEPにはあるという情報もありますが、それくらいでしょうか。

[dameo]

(1)少なくとも2.7では待ってられない時間がかかっているのですが、そこを説明できますか？
(2)了解です。ありがとうございます。

[hayataka2049]

keysの仕様が違うのだと思います。2.7のリファレンスでは
＞辞書のキーのリストのコピーを返します。
＞https://docs.python.org/ja/2.7/library/stdtypes.html
という記述です。
（そういえばpython2ってそういう言語だった……「たぶん他のバージョンでも同じでは」は外していたようですみません）

[dameo]

ありがとうございます。

2.7ではdict.viewkeys()を使わないとdictviewは返らないようですね。
現状python2.Xで新たに実装することはないのですが、たまに走らせたいときがあるので念の為です。

まとめると、
CPython3.Xでは、keys()呼び出しでdictview生成時間が差異となり発生するため、x in dictが速い。keys()を使うならdictviewを保存する。
CPython2.Xでは、keys()呼び出しでlistが生成されるため、その生成時間とinによるlist探索で膨大な時間がかかる。keys()ではなく、viewkeys()を使用し、dictviewを保存する。※要検証
他のPython実装は不明。
ですね

[hayataka2049]

それでいいと思います。

[hayataka2049]

辞書ビューのときと辞書のときの速度差についてですが、こちらでも測り直して、積極的に差があるとは言い難い結果でしたので、回答を修正しておきました。

[dameo]

対応ありがとうございます。
こちらの環境で、同様な計測をし、ついでにd.keys()を測ってみました。
Python 3.7.3 (default, Oct 7 2019, 12:56:13)
[GCC 8.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> d = {x:None for x in range(10000)}
>>> import timeit
>>> timeit.timeit(lambda : "a" in d)
0.09891023603267968
>>> timeit.timeit(lambda : "a" in d.keys())
0.1395494539756328
>>> ks = d.keys()
>>> timeit.timeit(lambda : "a" in ks)
0.1115037280251272
>>> timeit.timeit(lambda : d.keys())
0.12243326002499089
>>>
どうやら一回の処理時間が短すぎて、何を計測してるのだか分からない結果になってしまいました。

[hayataka2049]

そのようですね。lambda: Noneでやっても私の環境で約0.09秒かかっていますし、後ろで何かが走ったりしてばらつきに左右されるのでしょう。