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

Question

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

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

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

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

28

c++ algorithm lru

задан sud03r 13 January 2010 в 14:46

3 ответа

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

2

ответ дан 28 November 2019 в 02:55

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

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

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

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

6

ответ дан 28 November 2019 в 02:55

Другие вопросы по тегам:

c++ algorithm lru

Похожие вопросы:

score 39 · Accepted Answer

Недавно я реализовал кэш 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--;
}