LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@u1and0

末尾移動で最新のキャッシュを保持する辞書の派生クラスをPythonで作ってみた

Last updated at Posted at 2023-05-13

はじめに

このコードでは、maxsizeに指定された数までのキャッシュの値を保持するクラス「LRUDict」を定義しています。
指定したキーごとに保持する値がある場合、データを末尾に移動し 一番古い値を先頭から削除する仕組み(LRU)が備わっています。また、UserDictを継承しており、辞書型と同様のメソッドを利用できます。

使用用途としては、クエリ結果などをサイズ制限付きのディクショナリとしてキャッシュし、古いデータや参照されないデータは捨てていくような使い方です。使用回数に制限があったり使用にコストのかかるAPIを使うときにコストを節約することができます。メモリを食うような値を扱うときにメモリを節約しながらディクショナリへ結果をキャッシュすることができます。

旧名「LRUCache」でしたが、標準ライブラリのfunctools.lru_cacheと名前がかぶるので、「LRUDict」に名称変更しました。
functools.lru_cache は下記のような使われ方をするもので、LRUDictとは用途が違うものです。

以下、functools.lru_cacheより抜粋

高価な関数や I/O に束縛されている関数を定期的に同じ引数で呼び出すときに、時間を節約できます。

一般的には、 LRU キャッシュは前回計算した値を再利用したいときにのみ使うべきです。 そのため、副作用のある関数、呼び出すごとに個別の可変なオブジェクトを作成する必要がある関数、 time() や random() のような純粋でない関数をキャッシュする意味はありません。

LRU1とは

容量を使い切った後で新たに記録しなければならないデータが生じると、一定の計算手順（アルゴリズム）に従って既存のデータを消去したり、より低速・大容量な装置へ追い出す処理（仮想記憶のページアウトなど）を行い、空いた領域を新しいデータに割り当てる。
LRU方式は記録されたデータについて実行中のプログラムから最後にいつ参照されたかを記録しておき、入れ替えが必要になった時点で最後に参照されてから最も時間が経っているものを削除対象とする。

class LRUDict 

from typing import Optional
from collections import OrderedDict, UserDict


class LRUDict(UserDict):
    """
    getや__getitem__で参照されるたびに要素を末尾に移動します。
    __setitem__されたばかりの要素も末尾に追加されます。
    つまり、最初の方に__setitem__され、かつ__getitem__で参照されていないものが、
    __setitem__されたときにmaxsizeを超えると先頭から削除されます。

    Usage:

    >>> cache = LRUDict(maxsize=3)

    # キャッシュに値を保存する
    >>> cache["key1"] = "value1"

    # キャッシュから値を取得する
    >>> cache['key1']
    'value1'

    # 存在しないキーを指定して値を取得する
    >>> cache.get('not_exist_key', 'default_value')
    'default_value'

    # インスタンス化
    >>> cache = LRUDict(maxsize=3, a=1, b=2, c=3)

    >>> cache
    OrderedDict([('a', 1), ('b', 2), ('c', 3)])

    # maxsizeを超えると
    >>> cache["d"] = 4

    # 古いものから削除("a"の要素がなくなる)
    >>> cache
    OrderedDict([('b', 2), ('c', 3), ('d', 4)])

    # 参照すると
    >>> cache["c"]
    3

    # 新しく追加したものとして最後尾に追加
    >>> cache
    OrderedDict([('b', 2), ('d', 4), ('c', 3)])

    # `values`, `items`は
    # RuntimeError: OrderedDict mutated during iteration
    # が発生するので再実装
    # 表示を合わせるために`keys`も再実装

    >>> cache.keys()
    odict_keys(['b', 'd', 'c'])

    >>> cache.values()
    odict_values([2, 4, 3])

    >>> cache.items()
    odict_items([('b', 2), ('d', 4), ('c', 3)])

    # ここからはUserDictによる継承が機能しているかのテスト

    # __repr__
    >>> cache
    OrderedDict([('b', 2), ('d', 4), ('c', 3)])

    # __len__
    >>> len(cache)
    3

    # __contains__
    >>> "b" in cache
    True

    """
    def __init__(self, maxsize: Optional[int] = None, **kwargs):
        self.maxsize = maxsize
        self.data = OrderedDict(**kwargs)

    def __getitem__(self, key):
        value = self.data.pop(key)
        self.data[key] = value
        return value

    def __setitem__(self, key, value):
        if key in self.data:
            self.data.pop(key)
        elif self.maxsize is not None and len(self.data) >= self.maxsize:
            self.data.popitem(last=False)
        self.data[key] = value

    def get(self, key, default=None):
        if key in self.data:
            return self.__getitem__(key)
        return default

    def keys(self):
        return self.data.keys()

    def values(self):
        return self.data.values()

    def items(self):
        return self.data.items()


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=True)

使い方

docstringsに書いたままですが、一応書きます。doctest.testmod() でテストすることができます。

インスタンス化

>>> cache = LRUDict(maxsize=3)

キャッシュに値を保存する

>>> cache["key1"] = "value1"

キャッシュから値を取得する

>>> cache['key1']
'value1'

存在しないキーを指定して値を取得する

>>> cache.get('not_exist_key', 'default_value')
'default_value'

インスタンス化

>>> cache = LRUDict(maxsize=3, a=1, b=2, c=3)

>>> cache
OrderedDict([('a', 1), ('b', 2), ('c', 3)])

maxsizeを超えると

>>> cache["d"] = 4

古いものから削除("a"の要素がなくなる)

>>> cache
OrderedDict([('b', 2), ('c', 3), ('d', 4)])

参照すると

>>> cache["c"]
3

新しく追加したものとして最後尾に追加

>>> cache
OrderedDict([('b', 2), ('d', 4), ('c', 3)])

values, itemsはRuntimeError: OrderedDict mutated during iterationが発生するので再実装した。表示を合わせるためにkeysも再実装。

>>> cache.keys()
odict_keys(['b', 'd', 'c'])

>>> cache.values()
odict_values([2, 4, 3])

>>> cache.items()
odict_items([('b', 2), ('d', 4), ('c', 3)])

ここからはUserDictによる継承が機能しているかのテスト

# __repr__
>>> cache
OrderedDict([('b', 2), ('d', 4), ('c', 3)])

# __len__
>>> len(cache)
3

# __contains__
>>> "b" in cache
True

余談

ちなみに、このコードはGPTに適切なプロンプトを与えて生成しました。
ChatGPTではなく、GPT-4モデルが無料で使えるPerplexity.aiのEnhancedモードで生成しました。
以下にプロンプトのやり取りを貼っておきます。
「私からの質問(プロンプト)」をクリックするとPerplexityからの答えが展開されます。

dict-likeなクラスを作って下さい。ただし次の仕様を守って下さい。getや__getitem__で参照されるたびに要素を末尾に移動して下さい。__setitem__されたばかりの要素も末尾に追加されます。つまり、最初の方に__setitem__され、かつ__getitem__で参照されていないものが、__setitem__されたときにmaxsizeを超えると先頭から削除されるものとします。

PERPLEXITY
以下のコードは、指定された仕様に従ってdict-likeなクラスを実装したものです。このクラスは、getや__getitem__で参照されるたびに要素を末尾に移動し、__setitem__されたばかりの要素も末尾に追加されます。また、__setitem__されたときにmaxsizeを超える場合、先頭から削除されます。

from collections import OrderedDict

class CustomDict:
    def __init__(self, maxsize=10):
        self.maxsize = maxsize
        self.data = OrderedDict()

    def __getitem__(self, key):
        value = self.data.pop(key)
        self.data[key] = value
        return value

    def __setitem__(self, key, value):
        if key in self.data:
            self.data.pop(key)
        elif len(self.data) >= self.maxsize:
            self.data.popitem(last=False)
        self.data[key] = value

    def get(self, key, default=None):
        if key in self.data:
            return self.__getitem__(key)
        return default

    def __repr__(self):
        return repr(self.data)

このクラスは、OrderedDictを内部で使用しています。OrderedDictは、要素の挿入順序を保持するため、要素の末尾への移動や先頭からの削除が容易に行えます2。__getitem__と__setitem__メソッドをオーバーライドして、指定された動作を実現しています。2

`in`や`len`や`keys`, `items`といったメソッドも使いたいのですが、わざわざ実装しなければならないでしょうか。UserDictを継承することで簡略化できないでしょうか

PERPLEXITY
UserDictを継承することで、inやlenやkeys, itemsといったメソッドを簡単に実装できます。以下のコードは、UserDictを継承して指定された仕様に従ったdict-likeなクラスを実装したものです。

from collections import UserDict, OrderedDict

class CustomDict(UserDict):
    def __init__(self, maxsize=10):
        self.maxsize = maxsize
        self.data = OrderedDict()

    def __getitem__(self, key):
        value = self.data.pop(key)
        self.data[key] = value
        return value

    def __setitem__(self, key, value):
        if key in self.data:
            self.data.pop(key)
        elif len(self.data) >= self.maxsize:
            self.data.popitem(last=False)
        self.data[key] = value

    def get(self, key, default=None):
        if key in self.data:
            return self.__getitem__(key)
        return default

UserDictは辞書オブジェクトのラッパーとして動作し、独自の辞書に似たクラスを作成するために役立ちます3。UserDictを継承することで、既存のメソッドをオーバーライドしたり新しいメソッドを追加して、辞書風のサブクラスを作成することができます3。このため、UserDictを継承することで、inやlenやkeys, itemsといったメソッドを簡単に実装できます。3

`items`, `values` で RutimeError: OrderdDict mutated during iteration

PERPLEXITY
OrderedDictでitems()やvalues()を使ってイテレーション中に辞書を変更すると、RuntimeError: OrderedDict mutated during iterationが発生します。これは、イテレーション中に辞書の構造が変更されると、イテレーションが正しく機能しなくなるためです4。
この問題を解決するには、イテレーション中に辞書を変更しないようにするか、イテレーション用に辞書のコピーを作成して使用します。例えば、items()を使ってイテレーションする場合、以下のようにlist()を使って辞書のコピーを作成できます。

ordered_dict = OrderedDict(...)
for key, value in list(ordered_dict.items()):
    # ここで ordered_dict を変更してもエラーが発生しない

この方法で、OrderedDictがイテレーション中に変更されてもRuntimeErrorが発生しなくなります5。

これに少し修正を加えて先述のコードの完成です。

  1. LRU 【Least Recently Used】 LRU方式 / LRU制御方式 ↩

  2. github ↩ ↩2

  3. python-doc-ja ↩ ↩2 ↩3

  4. csdn ↩

  5. stackoverflow ↩

0
0
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?