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

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

前提

• Python 3.7
• 値が含まれているかどうかのみチェックする
• 値の重複、順序は考慮しない

やってみる

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

• item_in_list.py

  from decimal import Decimal
  import sys
  import time
  
  
  TARGET_ITEM = 'text_00001000'
  num = 1
  text_list = list()
  
  
  def item_in_list(target_item, target_list):
      in_start = time.time()
      print(target_item in target_list)
      in_proccess = time.time() - in_start
      print(f'[item in list]: {Decimal(in_proccess)}')
  
  
  if __name__ == '__main__':
      num = int(sys.argv[1])
      for n in range(0, num):
          text_list.append(f'text_{str(n).zfill(8)}')
      item_in_list(TARGET_ITEM, text_list)
  

• item_is_subset.py

  from decimal import Decimal
  import sys
  import time
  
  
  TARGET_ITEM = 'text_00001000'
  num = 1
  text_set = set()
  
  
  def item_is_subset(target_item, target_set):
      sub_start = time.time()
      print({target_item} < text_set)
      sub_proccess = time.time() - sub_start
      print(f'[is subset]:    {Decimal(sub_proccess)}')
  
  
  if __name__ == '__main__':
      num = int(sys.argv[1])
      for n in range(0, num):
          text_set.add(f'text_{str(n).zfill(8)}')
      item_is_subset(TARGET_ITEM, text_set)
  

• check.sh

  python item_in_list.py $1
  python item_is_subset.py $1
  

あらかじめ NUM で指定した数の要素を持つ list と set を生成しておいて、それぞれに対して特定の要素 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 のほうが速そう。