python LRUキャッシュの淘汰を実現

LRU Least Recent usedは最近最も少なくアルゴリズムを使用して、主にキャッシュ淘汰に用いる.主な目的は、最近最も使用されているデータをメモリから削除し、他のデータをロードすることです.
原理: 新しいデータがある場合(データが以前にキャッシュされていないことを意味する)、リストヘッダキャッシュに加入して最大容量に達した場合、データの多いデータを淘汰する必要がある.この場合、淘汰リストの末尾のデータはキャッシュ中にデータがヒットした場合、データをリストヘッダに移動する(新たにキャッシュに加入することに相当する)
 前述の文章から分かるように、キャッシュを簡略化すると2つの機能があり、1つはデータ(キャッシュデータ)を内蔵し、1つはデータ(ヒットキャッシュ)を外部に吐き出すので、私たちのキャッシュは外部にputとgetの2つのインタフェースだけでよい.
 キャッシュ内部ではLRUロジックを1つのリスト(list)だけで実現できますが、リストではロジックが実現できますが、キャッシュにヒットしたかどうかを判断する際には、速度が非常に遅い可能性があります(リストはデータが入っているかどうかを知るために遍歴する必要があります).Pythonでは,辞書(dict)や集合(set)のようなhashベースの構造を用いて,データが存在するか否かを迅速に判断し,リスト実装の性能問題を解決することができる.しかし、辞書(python 3.6以降の順序)と集合には順序がなく、並べ替え可能でhashベースのデータ構造があればよい.
Pythonのcollectionsパッケージには、このような実用的な構造OrderedDictが内蔵されており、OrderedDictはdictのサブクラスであるが、内部に格納されている要素は秩序化されている(リストの特徴).

from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = OrderedDict()

    def get(self, key):
        #             -1
        if key not in self.queue:
            return -1
        #           
        value = self.queue.pop(key)
        #             
        #                
        self.queue[key] = value
        return self.queue[key]

    def put(self, key, value):
        #         ,         
        if key in self.queue:
            self.queue.pop(key)
        #                ,          
        elif len(self.queue.items()) == self.capacity:
            #           
            self.queue.popitem(last=False)
        #          
        self.queue[key] = value