Python: la costruzione di una cache LRU

Question

ho intorno 6,00,000 entries in MongoDB nel seguente formato:

feature:category:count 

dove

• funzione potrebbe essere qualsiasi parola,
• categoria è positivo o negativo e
• conteggio indica quante volte si è verificata una funzionalità in un documento per quella categoria.

Voglio memorizzare nella cache le 1000 tuple in alto, diciamo di non interrogare il database ogni volta.

Come si crea una cache LRU in Python? O ci sono soluzioni note a questo?

Answer 1

Python 3.2 functools include un LRU cache. Potresti facilmente cherrypick da repo, controlla se devi regolarlo per lavorare con Python 2 (non dovrebbe essere troppo difficile - forse usando itertools invece di alcuni builtin - chiedi se hai bisogno di aiuto) e sii fatto. È necessario avvolgere la query in un callable e assicurarsi che dipenda dagli argomenti della funzione (hashable), comunque.

Answer 2

Oltre alla versione inclusa in Python 3.2, esistono le ricette della cache LRU nello Python Cookbook incluso lo these dallo sviluppatore principale Python Raymond Hettinger.

Answer 3

Lo LRU cache in Python3.3 ha O (1) inserimento, cancellazione e ricerca.

Il progetto utilizza un elenco circolare di voci con doppio collegamento (disposte da meno recenti) e una tabella di hash per individuare i singoli collegamenti. Gli hit della cache usano la tabella hash per trovare il link pertinente e spostarlo in testa alla lista. La mancanza di cache elimina il collegamento più vecchio e crea un nuovo collegamento all'inizio dell'elenco collegato.

Ecco una versione semplificata (ma veloce) in 33 linee di Python di base (utilizzando solo le operazioni di dizionario e elenco semplici). Funziona su Python2.0 e più tardi (o PyPy o Jython o 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

ci sono anche backport della versione di Python 3.3 di lru_cache come this che gira su Python 2.7. Se sei interessato a due livelli di memorizzazione nella cache (se non memorizzato nella cache nell'istanza controllerà una cache condivisa), ho creato lru2cache in base al backport di lru_cache.