【Python】collectionsライブラリを活用しよう_2. OrderedDict

はじめに

こんにちは。孔子の80代目子孫兼AS部DS2課の孔です。collectionsライブラリを活用しよう第２弾！今回はOrderedDictの紹介です。

前回の記事で、collectionsライブラリは「汎用の Python 組み込みコンテナ dict, list, set, および tuple に代わる、特殊なコンテナデータ型の実装」とのお話がありました。第１弾はtupleを拡張したnamedtupleの紹介でしたが、今回はdictを拡張したOrderedDictです。それでは早速みてみましょう！

OrderedDict: 順序付き辞書型

OrderedDictは名前通り、「順序付き辞書」になります。まずはどのように使うのかをみてみましょう。

from collections import OrderedDict
　
# listを渡して作成
od = OrderedDict([
    ('key_1', 'itme_1'),
    ('key_2', 'itme_2'),
    ('key_3', 'itme_3'),
])
od  # OrderedDict([('key_1', 'itme_1'), ('key_2', 'itme_2'), ('key_3', 'itme_3')])
　
# tupleを渡して作成
od = OrderedDict(
    key_1='item_1',
    key_2='item_2',
    key_3='item_3',
)
od  # OrderedDict([('key_1', 'item_1'), ('key_2', 'item_2'), ('key_3', 'item_3')])
　
# 要素を操作する方法はdict同様
od['new_key'] = 'new_item'  # 要素追加
od['new_key'] = 'new_item_updated'  # 更新
del od['new_key']  # 削除
　
# 要素を追加しても要素の順序が変わらない
od.update([
    ('key_4', 'item_4'),
    ('key_5', 'item_5')
])
od  # OrderedDict([('key_1', 'itme_1'), ('key_2', 'itme_2'), ('key_3', 'itme_3'), ('key_4', 'item_4'), ('key_5', 'item_5')])

OrderedDictの名前通り、要素を追加したり削除したりしても順序が変わらない！というのが特徴です。

dict型は要素が追加された時に、どの順番で要素が追加されたのかは特に保存してなく、キーと値だけを覚えているので、「要素が追加された順序も覚えてる辞書が欲しい！」と言った時に活躍できるのがこのOrderedDictです！

…であったはずですが、これはもう過去の話です。

the insertion-order preservation nature of dict objects has been declared to be an official part of the Python language spec. （引用元：https://docs.python.org/3/whatsnew/3.7.html）

つまり、Python3.7+ であれば、デフォルトのdictでも順序が保証されています。じゃOrderedDictなんかいらないじゃんか！となるかもしれませんが、まだそう思うには早いのです！

dictとOrderedDictの使い分け

dictも順序が保証されるようになった今、あまり違いがなさそうに見えるOrderedDictですが、何か違いがないと生き残れないはずです。その違いをみてみましょう。

違いその１：オブジェクト間の比較をする際に順序まで比較してくれる

まず１つ目の違いは、オブジェクトを比較する際に「順序も一致してるかどうか」までをOrderedDictは見てくれます。

# dictは順序が違ってもKey-Valueが一致したら同じオブジェクト
dict_1 = {
    'key_1': 'item_1',
    'key_2': 'item_2'
}
dict_2 = {
    'key_2': 'item_2',
    'key_1': 'item_1'
}
dict_1 == dict_2  # True
　
# OrderedDictはKey-Valueが一致しても順序が異なったら異なるオブジェクト
from collections import OrderedDict
　
od_1 = OrderedDict([
    ('key_1', 'itme_1'),
    ('key_2', 'itme_2'),
])
od_2 = OrderedDict([
    ('key_2', 'itme_2'),
    ('key_1', 'itme_1'),
])
od_1 == od_2  # False

違いその２：順序に関する実装がより豊富

OrderedDict型にはpopitemというメソッドがあります。このメソッドにlast引数を渡すことで、キーと値をFIFO・LIFO式で取り出すことができます。 dict型でも実装されているpopitemメソッドですが、last引数はなく、LIFOでキーと値を取得します。

from collections import OrderedDict
　
od = OrderedDict([
    ('key_1', 'itme_1'),
    ('key_2', 'itme_2'),
    ('key_3', 'itme_3'),
])
# popitemメソッドはFIFOでもLIFOでも使用可能
od.popitem(last=False)  # ('key_1', 'item_1')
od.popitem(last=True)  # ('key_3', 'item_3')
od  # OrderedDict([('key_2', 'item_2')])

deque（次回の記事で説明しますが、簡単に言うと先頭からも末尾からもpopができるキューです）のような使い方ができるdictが欲し！となったらOrderedDictを考慮するのもいいでしょう。

また、OrderedDictにはmove_to_endメソッドが実装されていて、要素を先頭・末尾に移動させることもできます。

# 要素を先頭・末尾に移動する
od = OrderedDict([
    ('key_1', 'itme_1'),
    ('key_2', 'itme_2'),
    ('key_3', 'itme_3'),
])
　
od.move_to_end('key_1')
od  # OrderedDict([('key_2', 'itme_2'), ('key_3', 'itme_3'), ('key_1', 'itme_1')])
od.move_to_end('key_1', last=False)
od  # OrderedDict([('key_1', 'itme_1'), ('key_2', 'itme_2'), ('key_3', 'itme_3')])
　
# オブジェクト同士を比較する際に、順序まで比較する

順序を意識したdictらしく、FIFO・LIFOで要素をpopできたり、要素を先頭・末尾に置けたりするのが特徴です。

違いその３：並び替えに特化した実装

OrderedDictはdictより並び替えに特化したアルゴリズムで実装されています。そのため、順序を変えたり、要素を追加・削除したり数量な操作において、パフォーマンスがdictより優れています。

その利点を活かしたのがLRUキャッシュ（Least Recently Used Cache）の実装です。LRUキャッシュとは、名前通り「最も最近使われたものをキャッシュする」ような方式です。つまり、キャッシュ用メモリがいっぱいになったら、最も古くキャッシュされたデータが削除されていくような実装になります。

# https://docs.python.org/ja/3/library/collections.html#ordereddict-examples-and-recipesより
from time import time
　
class TimeBoundedLRU:
    "LRU Cache that invalidates and refreshes old entries."
　
    def __init__(self, func, maxsize=128, maxage=30):
        self.cache = OrderedDict()  # { args : (timestamp, result)}
        self.func = func
        self.maxsize = maxsize
        self.maxage = maxage
　
    def __call__(self, *args):
        if args in self.cache:
            self.cache.move_to_end(args)  # キャッシュされた値が参照されたら末尾に置く
            timestamp, result = self.cache[args]
            if time() - timestamp <= self.maxage:
                return result
        result = self.func(*args)
        self.cache[args] = time(), result
        if len(self.cache) > self.maxsize:  # キャッシュ限度を超えたら、先頭の値を削除する
            self.cache.popitem(0)
        return result