Quali strutture dati vengono comunemente utilizzate per le cache LRU e per localizzare rapidamente gli oggetti?

Question

Ho inteso implementare una HashTable per individuare rapidamente gli oggetti che è importante per la mia applicazione.

Tuttavia, non mi piace l'idea di scansionare e potenzialmente dover bloccare l'intera tabella per individuare l'ultimo oggetto a cui è stato effettuato l'accesso. Le tabelle potrebbero essere abbastanza grandi.

Quali strutture dati vengono comunemente utilizzate per superare questo?

ad es. Pensavo di poter gettare oggetti in una FIFO e nella cache per sapere quanti anni ha. Ma questo non supporterà un algoritmo LRU.

Qualche idea? come fa il calamaro?

Answer 1

Gli elenchi collegati sono validi per le cache LRU. Per le ricerche indicizzate all'interno dell'elenco collegato (per spostare la voce sull'estremità utilizzata più di recente dell'elenco collegato), utilizzare una HashTable. La voce meno recente sarà sempre l'ultima nell'elenco collegato.

Answer 2

È possibile trovare questo article sull'implementazione della cache LRU utilizzando i contenitori STL (o un'alternativa basata su boost::bimap) interessante. Con STL, in pratica si utilizza una combinazione di una mappa (per la ricerca rapida di valori-chiave) e un elenco separato di chiavi o iteratori in quella mappa (per una facile manutenzione della cronologia degli accessi).