当前位置:  编程语言>c/c++

boost unordered_map和std::list相结合的实现LRU算法

 
    发布时间:2013-10-20  


    本文导语:  LRU(Least Recently Used)近期最少使用算法是内存管理的一种页面置换算法。LRU是为虚拟页式存储管理服务的。关于操作系统的内存管理,如何节省利用容量不大的内存为最多的进程提供资源,一直是研究的重要方向。而内存的...

  LRU(Least Recently Used)近期最少使用算法内存管理的一种页面置换算法。LRU是为虚拟页式存储管理服务的。关于操作系统的内存管理,如何节省利用容量不大的内存为最多的进程提供资源,一直是研究的重要方向。而内存的虚拟存储管理,是现在最通用,最成功的方式—— 在内存有限的情况下,扩展一部分外存作为虚拟内存,真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能,极大地提高了计算机并发度。虚拟页式存储管理,则是将进程所需空间划分为多个页面,内存中只存放当前所需页面,其余页面放入外存的管理方式。然而,有利就有弊,虚拟页式存储管理减少了进程所需的内存空间,却也带来了运行时间变长这一缺点:进程运行过程中,不可避免地要把在外存中存放的一些信息和内存中已有的进行交换,由于外存的低速,这一步骤所花费的时间不可忽略。因而,采取尽量好的算法以减少读取外存的次数,也是相当有意义的事情。

   在设计数据缓存项目中,经常需要实现基于LRU的数据缓存。目前常用方法有两种:

  1)每一条缓存数据附加一个时间戳,通过对时间的对比来清除当前最久未使用的的数据项。

  2)通过栈来缓存数据项的标识,不断将最近使用过的数据项标识移动到栈顶,通过不断移除栈底标识对应的数据项来实现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;


  插入算法实现代码片段:  

// 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--;
}

以上实现方法的一些频繁操作时间复杂度均为O(1).


  • 本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载,整理或搜集自网络.欢迎任何形式的转载,转载请注明出处.
    转载请注明:文章转载自:[169IT-IT技术资讯]
    本文标题:boost unordered_map和std::list相结合的实现LRU算法
相关文章推荐:


站内导航:


特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

©2012-2021,,E-mail:www_#163.com(请将#改为@)

浙ICP备11055608号-3