转自:《程序员》 文/ 洪伟铭
cache的所有位置都用双向链表链接起来,当一个位置被命中后,就将通过调整链表的指向将该位置调整到链表的头位置,新加入的内容直接放在链表的头上。这样,在进行过多次查找操作后,最近被命中过的内容就向链表的头移动,而没有被命中的内容就向链表的后面移动。当需要替换时,链表最后的位置就是最近最少被命中的位置,我们只需要将新的内容放在链表前面,淘汰链表最后的位置就是想了LRU算法。
LRU算法的实现
对象设计
对于Cache的每个位置,我们设计一个对象来储存对象的内容,并实现一个双向链表。
其中属性next和prev时双向链表的两个指针,key用于存储对象的键值,value用户存储要cache的对象本身。
我们使用hash算法来从cache中查找对象。
我们使用一个hashmap作为cache,用hashmap的检索机制来实现cache查找;并用head和last两个属性来记录链表的头和尾。并提供put(),getEntry()方法来操作该cache。
算法实现
cache的put()方法可将要缓存的内容放到cache中,在该方法中,对象调用私有方法insert(),将内容放到双向链表的头位置,如果cache满了,则将链表最后的位置淘汰掉:
pubilc boolean put(Object key,Object value){
boolean res = false;
HashLinkEntry en = new HashLinkEntry(key , value);
if(map.isEmpty()) {
this.head = en;
this.last = en;
map.put(en.key,en);
res = true;
} else {
HashLinkEntry point = this.getEntry(key);
if(point = null) {
point.value = value;
} else {
this.insert(en);
res = true;
}
}
return res;
}
private void insert(HashLinkEntry en) {
if(map.size() >= this.maxsize) {
HashLinkEntry lastprev = last.prev;
if(lastprev != null) {
map.remove(last.key);
lastprev.next = null;
last = null;
last = lastprev;
} else {
log.error("hashlist get a null point\n" + this.toString());
}
}
map.put(en.key,en );
ent.next = head;
head.prev = en;
head = en;
}
cache的getEntry()方法可根据输入的内容键值key来查找内容是否存在于cache中,如果命中,这个内容就是最新被使用过的,就需要放到双向链表的头位置。
结束语
LRU算法是cache最常用的算法之一,基于双向链表的实现方式比较容易,并可满足大容量cache的需求,在对系统性能要求越来越高的今天,良好的cache算法有着非常广泛的用途和实现意义。
分享到:
相关推荐
spider网络爬虫 c++ 实现 采用广度搜索算法获取url
宽度优先搜索策略通常是实现爬虫的最佳策略,因为它容易实现,而且具备大多数期望的功能。但是如果要遍历一个指定的站点或者深层嵌套的HTML文件集,用宽度优先搜索策略则需要花费比较长的时间才能到达深层的HTML文件...
网络爬虫是通过网页的链接地址来寻找网页,从网站某一个页面(设置为主页)开始,读取网页的内容,找到网页中的其它链接地址,然后通过这些链接地址寻找下一个网页,这样一直循环下去,直到这个网站所有的网页都...
从零开始学Python网络爬虫_源代码,介绍爬虫Spider框架及爬虫内容
用c#实现 的爬虫算法的实现,并用C# while (flag == 0) { uritemp = uritext + "&start=" + intstart.ToString() + "&sa = N"; MyInfo = ""; HttpWebRequest MyPageRequest = (HttpWebRequest)WebRequest....
本项目是基于Java的强力爬虫Spiderman设计源码,包含223个文件,其中114个Java文件,93个XML文件,6个gitignore文件,3个Properties文件,1个LICENSE文件,1个Markdown文件,1个bak2文件,1个YAML文件,1个EXE文件和...
网络爬虫 C++ Crawler Spider 有一定的参考价值
网络爬虫,spider,学习网络爬出的号例子,满足一般的抓取
网络爬虫,爬取指定的url,以及设定爬取深度。爬取的结果是网页的源码文件和图片。
小小网络爬虫测试软件,对搜索引擎设计者有所帮助!java语言开发。需要导入第三方包,可以到网站上下载,也可以找本人索取。
商剑分布式网络蜘蛛,性能高速运转,能耗尽全部带宽,可批量采集海量数据的网页,若几百台服务器安装商剑...更是搜索引擎-网络蜘蛛-网络爬虫-spider-网页抓取等技术的必备工具之一。http://www.100spider.cn/wspider.rar
基于Jsp的网络spider技术的网络新闻分析系统设计与实现(项目报告+源代码+数据库+演示录像).zip 基于Jsp的网络spider技术的网络新闻分析系统设计与实现(项目报告+源代码+数据库+演示录像).zip 基于Jsp的网络spider...
网络爬虫 java代码简单实现。可以供你参考哦。能直接导入工程运行的哦 网络爬虫 java代码简单实现。可以供你参考哦。能直接导入工程运行的哦
可扩展Spider的设计与实现可扩展Spider的设计与实现可扩展Spider的设计与实现可扩展Spider的设计与实现可扩展Spider的设计与实现可扩展Spider的设计与实现可扩展Spider的设计与实现可扩展Spider的设计与实现
这是一个spider网络爬虫源代码,用c++完成的,主要是为搜索引擎研究者提供很好的材料,为初学者提供代码。大家可以互相学习学习。
利用相关网络爬虫技术与算法,实现网络媒体新闻数据自动化采集与结构化存储,并利用中文分词算法和中文相似度分析算法进行一些归纳整理,得出相关的新闻发展趋势,体现网络新闻数据的挖掘价值。 如果商业公司能选取...