Jakie struktury danych są powszechnie używane w pamięci podręcznej LRU i szybko lokalizują obiekty?

Question

Chciałem zaimplementować HashTable do szybkiego zlokalizowania obiektów, co jest ważne dla mojej aplikacji.

Jednak nie podoba mi się pomysł skanowania i potencjalnie konieczność zablokowania całej tabeli w celu zlokalizowania, który obiekt był ostatnio dostępny. Tabele mogą być dość duże.

Jakie struktury danych są powszechnie używane do pokonania?

np. Pomyślałem, że mogę rzucić obiekty do FIFO, a także do pamięci podręcznej, aby wiedzieć, ile lat ma coś takiego. Ale to nie będzie wspierać algorytmu LRU.

Wszelkie pomysły? jak robi to kalmary?

Answer 1

Powiązane listy są dobre dla pamięci podręcznych LRU. W przypadku indeksowanych wyszukiwań na połączonej liście (aby przenieść wpis do ostatnio używanego końca połączonej listy), użyj HashTable. Ostatnio używany wpis zawsze będzie ostatni na liście połączonej.

Answer 2

Może się okazać, że ta article dla implementacji pamięci podręcznej LRU będzie korzystała z kontenerów STL (lub alternatywy opartej na boost::bimap). W przypadku STL, w zasadzie używasz kombinacji mapy (do szybkiego wyszukiwania wartości klucz-wartość) i oddzielnej listy kluczy lub iteratorów do tej mapy (dla łatwej konserwacji historii dostępu).