gpt4 book ai didi

c++ - 生产代码中的 LRU 实现

转载 作者:IT老高 更新时间:2023-10-28 12:46:41 25 4
gpt4 key购买 nike

我有一些 C++ 代码需要使用 LRU 技术实现缓存替换。
到目前为止,我知道实现 LRU 缓存替换的两种方法:

  1. 每次访问缓存数据时使用timeStamp,最后比较替换时的timeStamp。
  2. 使用一堆缓存项,如果最近访问过,则将它们移动到顶部,因此最后底部将包含 LRU Candidate。

那么,哪些更适合用于生产代码?
他们还有其他更好的方法吗?

最佳答案

最近我使用散布在 HashMap 上的链表实现了 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--;
}

关于c++ - 生产代码中的 LRU 实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2057424/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com