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

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

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

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

Ответ 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 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--;
}

Ответ 2

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

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

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

Ответ 3

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

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

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

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

Ответ 4

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

Ответ 5

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