どうも、駆け出しのエンジニアのMasaです！
今回は、Pythonの配列（list）と辞書（dict）の検索速度の違いについて書きたいと思います。
この記事で書いていること
まずは結論から。
- 特定のデータを保持しているか検索する際、dictのkeyを使う方が、listを使うよりも圧倒的に速い
- その理由は、dictはhash tableを使用しているから
- LeetCodeの問題を例として紹介
では、詳細を見ていきます。
あるLeetCodeの問題を解いていて
配列と辞書の検索速度について調べることになったのは、あるLeetCodeの問題がきっかけでした。
一言でいうと、「inputとして与えられたLinked Listが循環参照になっているかどうか調べて、True/Falseを返すメソッドを書いてください」という問題です。
「Linked List」というのは、複数のノードから成るデータ構造のことで、それぞれのノードがvalueと次のノードを指し示すpointerを保持しています。
詳しくは、下記の記事がわかりやすいです。
英語の記事ですが、図とコードを見るだけで、Linked Listが何者なのか大体わかります。
さて、この問題ですが、一番シンプルで簡単な方法は、
Linked Listを前から順番に見ていって、出現したnodeを配列や辞書などに格納していく
循環していれば、どこかの時点で、nodeのpointerが、記録済みのnodeを指しているはずなので、それを検知する
というやり方かなと思います。
LeetCode公式が出している、一番最初の解答例もこのやり方です。
もうお分かりだと思いますが、「あるnodeが記録済みのnodeを指し示しているか」を調べる際に、配列と辞書で大きな差が出るのです。
listよりも、dictの方が検索するのが圧倒的に速い
私が最初に書いたのは、配列を使う方法でした。
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
l = []
while True:
if not head:
return False
l.append(head)
if head.next in l:
return True
else:
head = head.next
このコードの結果がこちら。
速度が全然出ていません。
調べた結果、配列よりもdictを使った方が断然速く、かつPython3.6以降はメモリ使用にも関しても差が小さくなったということが分かりました。
dictを使うようにしたコードがこちら。
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
l = {}
while head:
l.setdefault(head, True)
if l.has_key(head.next):
return True
head = head.next
return False
結果は、
一気に速くなりました。
こんなに差が出るのは、dictがhash tableというデータ構造を使っているからです。
hash tableとは？
wikipediaの定義だと、
ハッシュテーブルはキーをもとに生成されたハッシュ値を添え字とした配列である。
とのこと。
つまり、dictのkeyを検索するときは、keyを元に生成されたハッシュ値を検索しているということです。（たぶん）
中身を探索しにいってしまう配列と比べれば、速度に大きな差が出るのは明らかですね。
まとめ
dictのkeyを使う方が、listを使うよりも検索が速いというお話でした。
LeetCodeみたいなコンテストなら、迷わずdictを選ぶべきでしょう。
ただ、実務においては、使いもしないdictのvalueを適当に入れたりするのは、他メンバーの混乱を招きそうな気もするので、どうなのかなと思ったりもしました。
参考にしたサイト
http://www.jessicayung.com/how-python-implements-dictionaries/
