Python: Aufbau eine LRU-Cache

Question

Ich habe um 6,00,000 entries in MongoDB in folgendem Format:

feature:category:count 

wo

• Merkmal jedes Wort sein könnte,
• Kategorie positiv oder negativ und
• zählen gibt an, wie oft ein Feature in einem Dokument für diese Kategorie aufgetreten ist.

Ich möchte die Top 1000 Tupel zwischenspeichern, sagen wir so, um Datenbank jedes Mal nicht abzufragen.

Wie erstellt man einen LRU-Cache in Python? Oder gibt es dafür bekannte Lösungen?

Answer 1

Python 3.2 functools enthält eine LRU cache. Sie können es leicht von repo aus überprüfen, überprüfen, ob Sie es anpassen müssen, um mit Python 2 zu arbeiten (sollte nicht zu schwer sein - vielleicht mit itertools anstelle von bestimmten eingebauten - fragen Sie, wenn Sie Hilfe brauchen) und fertig sein. Sie müssen die Abfrage in eine aufrufbare Datei umbrechen und sicherstellen, dass sie von den (hashbaren) Funktionsargumenten abhängt.

Answer 2

Neben der in Python 3.2 enthaltenen Version gibt es LRU-Cache-Rezepte in der Python Cookbook einschließlich these von Python Core-Entwickler Raymond Hettinger.

Answer 3

Die LRU cache in Python3.3 hat O (1) einfügen, löschen und suchen.

Der Entwurf verwendet eine kreisförmige doppelt verknüpfte Liste von Einträgen (angeordnet ältesten zu neuesten) und eine Hash-Tabelle, um einzelne Verknüpfungen zu finden. Cache-Treffer verwenden die Hash-Tabelle, um den relevanten Link zu finden und ihn an den Anfang der Liste zu verschieben. Cache-Fehler löschen den ältesten Link und erstellen einen neuen Link am Anfang der verknüpften Liste.

Hier ist eine vereinfachte (aber schnelle) Version in 33 Zeilen von sehr einfachen Python (mit nur einfache Wörterbuch-und Listen-Operationen). Es läuft auf Python2.0 und später (oder PyPy oder Jython oder 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)) 

Answer 4

Es gibt auch portiert von der Python-Version 3.3 von lru_cache wie this, die 2.7 auf Python läuft. Wenn Sie an zwei Caching-Schichten interessiert sind (falls nicht in der Instanz zwischengespeichert, wird es einen geteilten Cache prüfen) Ich habe lru2cache basierend auf dem Backport von lru_cache erstellt.