データを探索するときのリストと辞書型の速度比較

Python

データを探索するときのリストと辞書を速度比較してみた．

プログラム

以下のプログラムで調べた

#-*- coding:utf-8 -*-
import time

a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']
b = {'a':1, 'b':1, 'c':1, 'd':1, 'e':1, 'f':1, 'g':1, 'h':1, 'i':1, 'j':1, 'k':1}

def test_a():
    if 'c' in a:
	print 'a'

def test_b():
    if b.has_key('c'):
	print 'a'

if __name__=='__main__':
    f = time.clock()
    test_a()
    t = time.clock()
    print t-f
    f = time.clock()
    test_b()
    t = time.clock()
    print t-f

結果

  • １回目
リスト 0.000531219697289
辞書型 0.000296955110286
  • ２回目
リスト 0.000330316733787
辞書型 0.000177806454924
  • ３回目
リスト 0.00050555690998
辞書型 0.00178136405047
  • ４回目
リスト 0.000355979521096
辞書型 0.000163875227528
  • ５回目
リスト 0.0023804068285
辞書型 0.00198446668145
  • ６回目
リスト 0.000446165887923
辞書型 0.00161125643174
  • ７回目
リスト 0.000526453751075
辞書型 0.00165488317016
  • ８回目
リスト 0.000484293457639
辞書型 0.00183232301384

感想

リストが線形探索で，辞書型はハッシュだから，計算量的にはO(n)とO(1)ってことなのかな？
だから，当然辞書型のほうが速いと思ってたら，リストは途中から高速化しだした．
なんでだろ？？