10

私は6,00,000 entries in MongoDB次の形式で周りにいます： 

feature:category:count

どこ

  • 機能は任意の単語である可能性があり、
  • カテゴリがポジティブまたはネガティブであり、
  • countは、そのカテゴリのドキュメントでフィーチャが発生した回数を示します。

毎回データベースにクエリを実行しないように、上位 1000 個のタプルをキャッシュしたいとします。

Python で LRU キャッシュを構築するにはどうすればよいですか? または、これに対する既知の解決策はありますか?

4

4 に答える 4

21

Python3.3のLRU キャッシュには、O(1) の挿入、削除、および検索があります。

この設計では、エントリの循環的な二重リンク リスト (古いものから新しいものへと配置) とハッシュ テーブルを使用して、個々のリンクを見つけます。キャッシュ ヒットは、ハッシュ テーブルを使用して関連するリンクを見つけ、それをリストの先頭に移動します。キャッシュ ミスにより、最も古いリンクが削除され、リンク リストの先頭に新しいリンクが作成されます。

これは、33 行の非常に基本的な Python の単純化された (ただし高速な) バージョンです (単純な辞書操作とリスト操作のみを使用)。Python2.0 以降 (または PyPy、Jython、Python3.x) で動作します。

class LRU_Cache:

    def __init__(self, original_function, maxsize=1024):
        # Link structure: [PREV, NEXT, KEY, VALUE]
        self.root = [None, None, None, None]
        self.root[0] = self.root[1] = self.root
        self.original_function = original_function
        self.maxsize = maxsize
        self.mapping = {}

    def __call__(self, *key):
        mapping = self.mapping
        root = self.root
        link = mapping.get(key)
        if link is not None:
            link_prev, link_next, link_key, value = link
            link_prev[1] = link_next
            link_next[0] = link_prev
            last = root[0]
            last[1] = root[0] = link
            link[0] = last
            link[1] = root
            return value
        value = self.original_function(*key)
        if len(mapping) >= self.maxsize:
            oldest = root[1]
            next_oldest = oldest[1]
            root[1] = next_oldest
            next_oldest[0] = root
            del mapping[oldest[2]]
        last = root[0]
        last[1] = root[0] = mapping[key] = [last, root, key, value]
        return value


if __name__ == '__main__':
    p = LRU_Cache(ord, maxsize=3)
    for c in 'abcdecaeaa':
        print(c, p(c))

Python 3.1 から、OrderedDictにより LRU キャッシュの実装がさらに簡単になります。

from collections import OrderedDict

class LRU_Cache:

    def __init__(self, original_function, maxsize=1024):
        self.original_function = original_function
        self.maxsize = maxsize
        self.mapping = OrderedDict()

    def __call__(self, *key):
        mapping = self.mapping
        try:
            value = mapping[key]
            mapping.move_to_end(key)
        except KeyError:
            value = self.original_function(*key)
            if len(mapping) >= self.maxsize:
                mapping.popitem(False)
            mapping[key] = value
        return value
于 2011-11-30T19:20:06.560 に答える
6

Python 3.2 に含まれているバージョンに加えて、LRU キャッシュ レシピがPython クックブックにあり、 Python コア開発者 Raymond Hettinger によるものも含まれています。

于 2010-12-14T21:13:11.437 に答える
3

Python 3.2functoolsにはLRU キャッシュが含まれています。repoから簡単にチェリーピックし、Python 2 で動作するように調整する必要があるかどうかを確認し (あまり難しくないはずです - おそらくitertools特定のビルトインの代わりに使用します - 助けが必要かどうか尋ねてください)、完了します。ただし、クエリを呼び出し可能なものにラップし、(ハッシュ可能な) 関数の引数に依存していることを確認する必要があります。

于 2010-12-14T20:40:32.157 に答える
1

Python 2.7 で実行されるこのような lru_cache の Python 3.3 バージョンのバックポートもあります。2 層のキャッシュに関心がある場合 (インスタンスにキャッシュされていない場合は、共有キャッシュがチェックされます) 、lru_cache のバックポートに基づいてlru2cacheを作成しました。

于 2016-02-02T22:34:44.137 に答える