リスト型と辞書型の計算量の違い~ハムスターのごはん探し~

あれご飯どこに隠したっけ？

ある日，ケージから脱走し部屋へと探索に出るハムスター
ハム「おなかがすいた」
ハム「そういえば，別の隠し場所に，ご飯を貯めていたはず！」
ハム「，，，，，，，，，あれ？どの隠し場所にご飯貯めてたっけ？」
どこにご飯を隠したか，思い出せないハムスター，さてどこにあったかどのように探していくのだろう？

隠し場所の候補

ハム「そういえば，ごはんはN個の隠し場所に隠したはず」
ハム「えーと，冷蔵庫の裏と，テレビ台の裏と，押し入れの隅と・・・エコバックの中と」
ハム「どこにご飯を隠したっけ？」

あんまり賢くないハムスター(リスト型)

ハム「どこかに隠したことは覚えているけど，どこに隠したかは覚えてないな」
ハム「どこにあるか，わかんないから，全部回って確認しよう！」
そうして，ハムスターは覚えている隠し場所の候補を全て回ることにしたのであった．
ハム「1つ目の場所は違う，2つ目の場所も違う・・・N個目の場所にあった！」
ハムスターが，ご飯を発見するまでに最悪のケースでは，隠し場所の数(N)箇所を探しに行かなければなりません．

List_sample.py

place_lis = [False, False,False，...,False, True] #N個
#True(ご飯がある場所)を検索
for place in place_to_hide_lis:
    if place == True:
        #最悪の場合の操作回数: N回
        print("ご飯見つけた！")

ハム「いっぱい回って疲れた，，，」

ちょっと賢くなったハムスター(辞書型)

前回，家中を回って懲りたハムスター
ハム「今度は隠した場所の名前を，憶えておいた！」
ハム「そこだけ，確認しに行けばいいや！」
ハム「”サーバラックの下”に隠したはず」

Dict_sample.py

place_dict = {'冷蔵庫の裏': 'False', 'テレビ台の裏': 'False',..., 'サーバラックの下': 'True'}
# キー''を検索
if place_dict['サーバラックの下'] == 'True':
    print("ご飯見つけた！")  # 平均的な操作回数: 1回

なんと，一か所探すだけでご飯が見つかりました．

まとめ

どちらも便利ではあるけれど，基本一発で一意に定まるので，検索速度は速い辞書型方が速い．このあたりを理解しておくと，辞書型とリスト型の使い分けにそこそこ便利だと思う．