找回密码
 用户注册

QQ登录

只需一步,快速开始

查看: 6695|回复: 1

一种O1性能的LRU算法

[复制链接]
发表于 2012-3-2 19:33:55 | 显示全部楼层 |阅读模式
LRU是一种淘汰算法,淘汰那些最久没被访问过的节点,以提高cache命中率。网游后台cache server经常会用到。这里说一种O1算法。

先明确两个操作相关的对象
1. DataKey: cache数据的key
2. IndexNode: 链表节点,内部有数据的index

list(单向链表)
      保存DataKeys。
hashtable(表)
      以DataKey作为key, IndexNode做为值,从DataKey可以定位到IndexNode。

访问一个数据对象
      先用DataKey查hash,如果找到,将IndexNode从list原来的位置拿掉,然后插到尾部。
      如果没找到,说明数据第一次被访问,有可能要淘汰旧点的数据。
      1. 查看hashtable size是否已达到最大值,未达到,将新的IndexNode插到list尾部;并且将DataKey和新的IndexNode保存到hashtable中。
      2. size已经是最大值,要淘汰一个旧节点来给新节点挪位置。从list头部取个节点,这个节点从list头部拿掉,然后通过DataKey把hash表对应的节点删除。



发表于 2013-2-21 16:30:09 | 显示全部楼层
哪儿有具体实现代码啊
您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

Archiver|手机版|小黑屋|ACE Developer ( 京ICP备06055248号 )

GMT+8, 2024-3-28 19:58 , Processed in 0.605010 second(s), 7 queries , Redis On.

Powered by Discuz! X3.5

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表