`
litaocheng
  • 浏览: 333484 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

erlang lru cache module

阅读更多
1个月前写ecrawler的时候,需要一个lru cache算法。
erlang中好像没有特别合适的选择,就自己实现了一个。
思想:
采用gb_trees保存key-value pair,可以实现快速的key lookup,但是当发生替换时,
需要根据访问时间清理item,我们可能需要gb_trees中的数据导入到list中,随后进行排序,然后调换掉比较旧的内容。为了改善性能,我将数据在list中做一个拷贝,但是注意不包含value,只是key和一些状态信息。
当发生替换时,我们可以直接对list进行排序(也可以在每次操作的时候,将item插入到list中的合适位置,保持list有序),随后删除最旧的元素。

采用此方法比gb_trees:to_list方法效率稍高。当然没有做太多的性能测试,比如gb_trees用dict, ets替换等,我们的原则还是,先让代码正确,随后再让代码高效。

接口:
new/1, get/2, insert/3, insert/4, size/1, max/1, hitrate/1, to_list/1

废话不说了,看代码吧,写的不足之处请见谅。
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics