Внедрение LRU в производственный код

Question

У меня есть некоторый код C ++, где мне нужно реализовать замену кеша с использованием техники LRU.
До сих пор я знаю два способа реализации замены кэша LRU:

1. Использование timeStamp для каждого доступа к кэшированным данным и, наконец, сравнение временных меток во время замены.
2. Использование стопки кэшированных элементов и перемещение их наверх, если к ним недавно обращались, поэтому, наконец, на дне будет находиться кандидат LRU.

Итак, какой из них лучше использовать в рабочем коде?
Есть ли у них какие-нибудь другие лучшие методы?

Answer 1

Недавно я реализовал кэш LRU, используя связанный список, распределенный по хэш-карте.

    /// Typedef for URL/Entry pair
    typedef std::pair< std::string, Entry > EntryPair;

    /// Typedef for Cache list
    typedef std::list< EntryPair > CacheList;

    /// Typedef for URL-indexed map into the CacheList
    typedef boost::unordered_map< std::string, CacheList::iterator > CacheMap;

    /// Cache LRU list
    CacheList mCacheList;

    /// Cache map into the list
    CacheMap mCacheMap;

Преимущество состоит в том, что O (1) для всех важных операций.

Алгоритм вставки:

// create new entry
Entry iEntry( ... );

// push it to the front;
mCacheList.push_front( std::make_pair( aURL, iEntry ) );

// add it to the cache map
mCacheMap[ aURL ] = mCacheList.begin();

// increase count of entries
mEntries++;

// check if it's time to remove the last element
if ( mEntries > mMaxEntries )
{
    // erease from the map the last cache list element
    mCacheMap.erase( mCacheList.back().first );

    // erase it from the list
    mCacheList.pop_back();

    // decrease count
    mEntries--;
}

Answer 2

Вот очень простая реализация кэша LRU

https://github.com/lamerman/cpp-lru-cache.

Легко использовать и понять, как это работает. Общий размер кода составляет около 50 строк.

Answer 3

Для простоты, возможно, вам следует рассмотреть возможность использования карты MultiIndex в Boost. Если мы отделяем ключ от данных, мы поддерживаем несколько наборов ключей для одних и тех же данных.

От [http://old.nabble.com/realization-of-Last-Recently-Used-cache-with-boost%3A%3Amulti_index-td22326432.html]:

"... использовать два индекса: 1) хэшировать для поиска значения по ключу 2) последовательно для отслеживания последних недавно использованных элементов (функция get помещает элемент как последний элемент в секвенции. может удалить их с начала последовательности). "

Обратите внимание, что оператор "проекта" позволяет программисту эффективно перемещаться между различными индексами одного и того же multi_index_container ".

Answer 4

Эта статья описывает реализацию с использованием пары контейнеров STL (карта значения ключа плюс список для истории доступа к ключу) или одного boost::bimap.

.

Answer 5

В нашей производственной среде мы используем двойной связанный список C ++, который похож на связанный список ядра Linux . Прелесть этого в том, что вы можете добавить объект в любое количество связанных списков, и работа со списком выполняется быстро и просто.