Come implementare la cache LFU usando STL?

Question

Sto provando ad implementare la cache LFU (Least Frequently Used) usando puro STL (non voglio usare Boost!).

I requisiti sono:

• l'accesso a qualsiasi elemento associativo utilizzando un Key come con std::map.
• Possibilità di rilasciare l'elemento con priorità più bassa (utilizzando l'attributo UsesCount).
• Possibilità di aggiornare la priorità (UsesCount) di qualsiasi articolo.

I problemi sono:

• Se uso std::vector come contenitore di oggetti (Key, Value, UsesCount), std::map come contenitore di iteratori al vettore di accesso associative e std::make_heap, std::push_heap e std::pop_heap come implementazione della coda di priorità all'interno del vettore, gli itertori nella mappa non sono validi dopo le operazioni di heap.
• Se uso std::list (o std::map) anziché std::vector nella configurazione precedente, std::make_heap ecc può non essere compilato becasue loro iteratori non supporta aritmetici.
• Se desidero utilizzare std::priority_queue, non è possibile aggiornare la priorità dell'elemento.

Le domande sono:

• mi sto perdendo qualcosa di ovvio come questo problema potrebbe essere risolto?
• Potete indicarmi qualche pura implementazione C++/STL di cache LFU che soddisfi i requisiti precedenti come esempio?

Grazie per i vostri approfondimenti.

Answer 1

L'implementazione make con le funzioni *_heap e un vettore sembra essere una buona idea. sebbene causerà aggiornamenti lenti. Il problema relativo all'in invalidazione dell'iteratore che si verifica è normale per ogni contenitore che utilizza un vettore come struttura dati sottostante. Questo è l'approccio adottato anche da boost::heap::priority_queue, ma non fornisce un'interfaccia mutevole per la ragione sopra menzionata. Altro boost::heap data-structures offre la possibilità di aggiornare l'heap.

Qualcosa che sembra un po 'strano: anche se si sarebbe in grado di utilizzare std::priority_queue si dovrà ancora affrontare il problema di invalidazione iteratore.

Per rispondere direttamente alle tue domande: non ti manca qualcosa di ovvio. std::priority_queue non è così utile come dovrebbe essere. L'approccio migliore è scrivere la propria implementazione dell'heap che supporti gli aggiornamenti. Per renderlo completamente compatibile con STL (specialmente con l'allocatore) è piuttosto complicato e non è un compito semplice. Oltre a ciò, implementa la cache LFU.

Per il primo passaggio, esaminare le implementazioni Boost per avere un'idea dello sforzo. Non sono a conoscenza di alcuna implementazione di riferimento per il secondo.

Per aggirare l'invalidazione dell'iteratore è sempre possibile scegliere l'indirezione in un altro contenitore, anche se si dovrebbe cercare di evitarlo poiché crea un costo aggiuntivo e può diventare piuttosto disordinato.

Answer 2

Un approccio un po 'più semplice di mantenere strutture di due dati:

• solo continuare una mappa, che mappa le chiavi per la loro coppia di valori/uso-count.
• quando la cache è piena:
• • creare un vettore di iteratori agli elementi della mappa (O(n))
• • uso std::nth_element per trovare il peggior 10% (O(n))
• • rimuovere tutti dalla mappa (O(n log n))

Quindi, l'aggiunta di un nuovo elemento alla cache è caso comune O(log n), caso peggiore O(n log n) e ammortizzato O(log n).

Rimuovere il peggior 10% potrebbe essere un po 'drastico in una cache LFU, perché le nuove voci devono ottenere il 90% superiore o sono tagliate. Poi di nuovo, se rimuovi un elemento solo allora le nuove voci devono ancora scendere dal fondo prima della prossima nuova voce, o sono tagliate, e hanno meno tempo per farlo. Quindi, a seconda del motivo per cui LFU è la strategia di caching giusta per te, il mio passaggio ad esso potrebbe essere la strategia sbagliata, o potrebbe ancora andare bene.