Python で実装された単純な LRU キャッシュ

原因: 私の同僚は固定サイズのキャッシュを必要としています。レコードがキャッシュ内にある場合はキャッシュから直接読み取られ、それ以外の場合はデータベースから読み取られます。 Python の dict は非常にシンプルなキャッシュですが、データ量が多いためメモリが肥大化しやすいため、LRU アルゴリズムを使用してレコード数を制限し、古いレコードを破棄する必要があります。キーは整数、値は約10KBのPythonオブジェクトです

分析:

1) キャッシュの場合、キー -> 値の関係を維持する必要があると想像できます

2) LRU を実装するには、関係タイムスタンプ -> (キー、値) を維持するための時間ベースの優先キューが必要です。

3) キャッシュ内のレコード数が上限 maxsize に達すると、最小のタイムスタンプを持つ (キー、値) をデキューする必要があります

4) (キー、値) がヒットしたら、実際にはそれをキューから削除し、キューの最後に挿入する必要があります。

分析から、キュー テーブルの迅速な削除と挿入を実現するには、キャッシュが上記の 4 つの機能を満たす必要があることがわかります。 use 二重リンクリストで末尾を挿入するには、末尾へのポインタが必要です。

以下は Python で実装されています:

コードをコピー コードは次のとおりです:

#encoding=utf-8
クラス LRUCache(オブジェクト):

Def __init__(self, maxsize):
#キャッシュ内のレコードの最大数
self.maxsize = maxsize
# 実ストレージデータに使用されます
self.inner_dd = {}
# リンクされたリストヘッドポインタ
self.head = なし
# リンクされたリスト末尾ポインタ
self.tail = なし

def set(self, key, value):

# 指定されたサイズに達する len(self.inner_dd) >= self.maxsize の場合:
self.remove_head_node()

ノード = Node()

Node.data = (キー, 値)

self.insert_to_tail(node)
self.inner_dd[key] = ノード

def insert_to_tail(self, ノード):

self.tail が None の場合:

self.tail = ノード
self.head = ノード
その他:
self.tail.next = ノード
Node.pre = self.tail
self.tail = ノード

def delete_head_node(self):

ノード = self.head

del self.inner_dd[node.data[0]]
ノード = なし
self.head = self.head.next
self.head.pre = なし
Def get(self, key):
self.inner_dd を入力した場合:
# ヒットした場合、対応するノードをキューの最後に移動する必要があります
ノード = self.inner_dd.get(key)
self.move_to_tail(node)
戻りnode.data[1]
なしを返す

def move_to_tail(self, node):
        # ただ必要な処理在队列部和中间的情况
        そうでない場合 (node == self.tail):
            if ノード == self.head:
                self.head = ノード.ネクスト
                self.head.pre = なし
                self.tail.next = ノード
                node.pre = self.tail
                node.next = なし
                self.tail = ノード
            それ以外:
                pre_node = ノード.pre
                next_node = ノード.next
                pre_node.next = next_node
                next_node.pre = pre_node

self.tail.next = ノード
                node.pre = self.tail
                node.next = なし
                self.tail = ノード

クラスノード(オブジェクト):
    def __init__(self):
        self.pre = なし
        self.next = なし
        # (キー, 値)
        self.data = なし

def __eq__(self, other):
        if self.data[0] == other.data[0]:
            True を返します
        False を返します
    def __str__(self):
       return str(self.data)

if __name__ == '__main__':
    キャッシュ = LRUCache(10)
    for i in xrange(1000):
        キャッシュ.set(i, i+1)
        キャッシュ.get(2)
    cache.inner_dd のキーの場合:
        印刷キー、cache.inner_dd[key]