LeetCodeを解いていたらOrderedDictを用いる解1が出てきました。OrderedDictの振る舞いやどうして種々の操作がO(1)でできるかをまとめていきます。
OrderedDictとは
ハッシュテーブルとか辞書とか言われるデータ構造があります。辞書はキーとバリューというデータの対応付けを記憶するものです。ただし、キー→バリューの参照は可能ですが、バリューからキーへの逆引きはできません。Python3では
d={} #辞書を作成
d["key"]="hello world" #"key"をキーとして"hello world"というバリューを対応させる
print(d["key"]) #"key"に対応した値hello worldが表示されるなどの形で利用することができます。
一般的なハッシュテーブルでは内部的にデータがどのように並んでいるかの保証はありません。例えば、
d={"aaa":"hoge","xyz":"fuga"}
for key in d:
print(d[key]) #先にfugaが表示されその後hogeが表示されるかもしれない（Python3.6以前）というコードを考えます。このとき、forループで回しているkeyに入ってくる値の順序は、辞書の作成時の”aaa”, “xyz”のままとは限りません（なお、Python3.7以降の辞書では値の設定時の順序が保存されることになりました）。このように、（一般的な）ハッシュテーブルはあくまでキーとバリューの対応付けを保存し、順序は情報として保持しないデータ構造です。
OrderedDictはハッシュテーブルにデータの順序という情報をもたせたデータ構造です。OrderedDictは
- データの挿入順序を保存する
- 効率的な順序変更方法(popitem,move_to_end)を提供する
という点が一般的なハッシュテーブルと異なっています。特に後者に関してはPython3.7以降でも辞書に対する利点として未だ残っています。そのためPython3で辞書データの順序変更を取り扱いたい場合はOrderedDictを使用することが望ましいと言えます2。
OrderedDictは順序変更を効率的に実行できる
OrderedDictで面白いのが、popitemやmove_to_endがO(1)で実行できるという点です。すなわち、どんなに要素数が多くても先頭/末尾の値削除や、あるキーバリューペアを末尾に持ってくる操作にかかる時間は一定です。
OrderedDictを知らなかったのでLeetCodeでは自分で実装しようとしたのですが、どうやってもO(n)のアルゴリズムしか思いつきませんでした。解の中でOrderedDictではO(1)と書かれているのを見てマ！？ｗｗとなりました。
このOrderedDictの内部実装に関してTim Petersという方がStackOverflowで簡単に紹介してくださっています。この方はPythonの中心的な開発者の一人であり、Tim sortというソートを開発された方でもあります。この方によると、OrderedDictの内部構造は
- 通常の辞書（1個目の辞書）
- キーのみを保持している順序保持用双方向リスト
- もとのキーをキーとし、双方向リスト内のノードをバリューとする通常の辞書（2個目の辞書）
からなっているとのことです。このポストをもとに以下で再現実装してみました。なお、以下の説明は前提として
class ListNode:
def __init__(self,val,prev_node=None,next_node=None):
self.val=val
self.next_node=next_node
self.prev_node=prev_node
class OrderedDict:
def __init__(self):
self.normal_dict={} #通常の辞書
self.order_list_head=None#キーのみを保持している順序保持用双方向リストの先頭
self.order_list_tail=None
self.key_to_node={} #元のキーをキーとし、双方向リスト内のノードをバリューとする通常の辞書というクラスを用います。また、キーが存在しない場合のエラー処理は省略しています。テストは行っていないため、間違い等あるかもしれません。その場合はコメントで指摘いただけると幸いです。
キーの追加
キーが追加されるときは
- 通常の辞書にキー・バリューの対応を保存
- 順序保持用双方向リストの末尾にノードを追加
- キーとノードの対応を2個目の辞書に保存
の順序で処理します。コードにすると
def register_key_value(self,key,value):
self.normal_dict[key]=value
new_node=ListNode(key,self.order_list_tail)
if not self.order_list_head: #最初のノード
self.order_list_head=new_node
self.order_list_tail=new_node
else:
self.order_list_tail.next_node=new_node
self.order_list_tail=new_node
self.key_to_node[key]=new_nodeとなります。通常の辞書の登録操作はO(1)で実行できるので、この関数全体でもO(1)の計算量が保たれます。
キーの参照
1個目の辞書を参照します。キーの参照はO(1)で実行できるので計算量はO(1)です。
def lookup(self,key):
return self.normal_dict[key] #エラー処理は省略キーの削除
- キーに対応するノードを2個目の辞書で取得
- ノードのprevとnextを取得
- prevの次をnextにする
- 2個目の辞書からキーとバリューを削除
- 1個目の辞書からキーとバリューを削除
です。
def delete_key(self,key):
node_to_delete=self.key_to_node[key]
prev_node=node_to_delete.prev_node
next_node=node_to_delte.next_node
prev_node.next_node=next_node
if node_to_delete==self.order_list_head:
self.order_list_head=next_node
if node_to_delete==self.order_list_tail:
self.order_list_tail=next_node
#順序保持用双方向リストからの削除完了
del self.key_to_node[key]
del self.normal_dict[key]ここで、もし順序を通常のリストを使って.append(key)で管理していたとすると、通常のリストからkeyを削除する操作が必要になります。一方で、通常のリストからの削除はO(n)でしか実現できません。これは、
- keyに一致するインデックスを取得するためにリストの頭から走査が必要
- リストから値を消して、後ろの値を前に詰めるために走査が必要
だからです(特集！知らないと損をする計算量の話 3-3. vector (C++), ArrayList (Java), list (Python) からの削除処理は末尾を除いて遅い)。上記コードは明らかにO(1)で行うことが可能になっています。従って、双方向リストと2番目の辞書は要素削除をO(1)で行うためのトリックと言えます。
先頭・末尾の取得
def popitem(self,key,last=True):
"""lastは末尾をpopしたいときTrue,先頭をpopしたいときFalse"""
if last:
key_to_delete=self.order_list_tail.val
self.order_list_tail=self.order_list_tail.prev_node
else:
key_to_delete=self.order_list_head.val
self.order_list_head=self.order_list_head.next_node
del self.key_to_node[key_to_delete]キーの先頭・末尾への移動
def move_to_end(self,key,last=True):
value=self.lookup(key)
self.delete_key(key)
new_node=ListNode(key)
if not self.order_list_head: #最初のノード
self.order_list_head=new_node
self.order_list_tail=new_node
elif last:
new_node.prev_node=self.order_list_tail
self.order_list_tail.next_node=new_node
self.order_list_tail=new_node
else:
new_node.next_node=self.order_list_head
self.order_list_head.prev_node=new_node
self.order_list_head=new_node
self.key_to_node[key]=new_nodeまとめ
- OrderedDictは辞書のキー挿入順序情報を保持し、先頭・末尾をpopしたり、ある要素を先頭・末尾に移動する操作を効率的に(O(1)で)実行できる
- OrderedDictの内部では以下データが保持されている
- キーバリューペアを保持する1個目の辞書
- キーの順序情報を保存する双方向リスト
- キーに対応するリストノードを保持する2個目の辞書
なお、エラー処理まで実装されたOrderedDictの再現実装がGitHubのGistで公開されています。より使い物になる実装をご覧になりたい方はそちらを参照ください。
コメント