michimani.net

[Python] 特定の値が存在するかチェックするときは list より set のほうが速い

2020-08-16

プログラムを書いているときに、特定の値がリストなどのオブジェクトに含まれているかどうかをチェックする場面はよくあると思います。久々に入門 Python 3 を読んでいたらタイトルのような内容がコラム的に書いてあったので、実際にどれくらい速いのか試してみました。

前提

やってみる

下記のようなスクリプトを用意して、連続して実行してみます。

あらかじめ NUM で指定した数の要素を持つ listset を生成しておいて、それぞれに対して特定の要素 TARGET_ITEM を含むかどうかをチェックし、かかった時間を計測します。

とりあえず要素数が 10 の場合で実行してみます。

$ sh check.sh 10
False
[item in list]: 0.000027179718017578125
False
[is subset]:    0.00002574920654296875

この時点でも少しだけ set のほうが速いです。ただ、何度か実行していると 10 回に 1 回くらいは list のほうが速くなる時がありました。

要素数 = 100

$  sh check.sh 100
False
[item in list]: 0.000029087066650390625
False
[is subset]:    0.000027179718017578125

要素数 = 10000

$ sh check.sh 10000
True
[item in list]: 0.0000660419464111328125
True
[is subset]:    0.0000431537628173828125

要素数 = 1000000

$ sh check.sh 1000000
True
[item in list]: 0.000080108642578125
True
[is subset]:    0.0000650882720947265625

要素数 = 100000000

$ sh check.sh 100000000
True
[item in list]: 0.0016210079193115234375
True
[is subset]:    0.00047206878662109375

まとめ

set のほうが速そう。

以上、よっしー (michimani) でした。