53
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

posted at

updated at

python リスト、辞書、セット型のinを使った時の参照速度を調べてみた。

はじめに

下記サイトには次のことが記載されている。
setsや辞書を使った要素の検証(O(1))は、配列の検索(O(n))よりも高速です。 a in b を調べるとき、bはリストやタプルではなくsetsや辞書であるべきです。
http://www.peignot.net/python-speed

本当なのかしらん?と思ったのと、本当だとしてどれくらい違うんじゃい?と気になったので実際に試してみた。

実行環境

python2.7
windows7
Intel Core i5 CPU 2.4GHz
メモリ 4.0 GB

実行条件

リスト、辞書、セット型で、1の倍数ごと、2の倍数ごと、3の倍数ごとの整数列(要素数100万個)を作り、1から1万までのinでの参照を行った。1の倍数ごと、2の倍数ごと、3の倍数ごとの整数列を作ったのはヒット率の処理速度への影響を調べるためである。
なお、各テスト回数は合計10回ずつである。
詳細は下記コード参照。

結果

死ぬほどリストの参照が遅い反面、辞書、セット型については超高速であった。リストにおいては、ヒット率が高い場合よりも、ヒット率が低い場合には処理速度が明らかに落ちることが見受けられた。なお、単位は秒であり、10回実行した時の合計時間である。
他方、辞書型、セット型に関してはそこまでの処理速度の低下は見受けられなかった。(3/5 8:08 範囲が誤っていたため図を修正)
speed_in.png

結論

要素数が多いリストで
要素 in リスト
的な文を書くのはできる限り避けるべきである。本当に死ぬほど遅い。

実験コードたち

def lists(q,h):
  ls = [i for i in range(0,q*h,h)]
  for i in range(q): i in ls

def dicts(q,h):
  dc = {i:i for i in range(0,q*h,h)}
  for i in range(q): i in dc  

def setts(q,h):
  st = set(i for i in range(0,q*h,h))
  for i in range(q): i in st

def exe(func,num=100):
  from timeit import timeit
  setup = 'from __main__ import ' + func[:5]
  print "%s: %s" % (func, timeit(func, setup, number=num))

if __name__=='__main__':
  q = 10**4
  funcs = ['lists','dicts','setts']
  hits = [1,2,3]
  for h in hits:
    for f in funcs:
      func = '%s(%s, %s)'  % (f,q,h)
      print func
      exe(func,10)

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
53
Help us understand the problem. What are the problem?