欢迎光临
我们一直在努力

使用PriorityQueue实现LFU和LRU

LFU(Least Frequently Used)算法根据数据的历史访问频率来淘汰数据,其核心思想是“如果数据过去被访问多次,那么将来被访问的频率也更高。

然后我先定义一个缓存对象MyCache,这里有一个泛型用来存对象,然后有一个useCount记录被使用次数,接下去是创建时间和最近使用时间。

使用PriorityQueue实现LFU和LRU

使用构造方法来初始化一些值:

使用PriorityQueue实现LFU和LRU

因为使用了Priorityqueue所以要实现Comparable接口,而且更具useCount来比较

使用PriorityQueue实现LFU和LRU

然后我们就可以进入下一步操作啦,定义一个PriorityQueue作为全局变量,这个限制一些最大缓存的数量,还有用一个object用来做同步块,队列中如果没有就加入队列中,这里就先不写set的情况,

使用PriorityQueue实现LFU和LRU

然后根据优先队列的特性来删除哪些不常用的元素,因为根据排序,优先队列会把我们最想要的数据放在头部,所以调用poll方法,就可以实现删除最少使用的那一个,当然这里我可以选择删除固定数量的不常用数据,或者删除一定比例的数据,这个使用中可以用定时器或者分布式任务来清除缓存。

使用PriorityQueue实现LFU和LRU

因为考虑哪些数据相等,我这里重写了hashCode和equals方法,这里只是调用缓存对象的比较,但是对于那些没有重写的缓存对象T,可能就会有问题啦,所以可能有的设计就会用序列化后的数据。

使用PriorityQueue实现LFU和LRU

因为PriorityQueue只是做了一次的排序,所以我需要在用户修改后的数据也要更新顺序,所以我想把原来的数据删了,然后再添加一词,使用次数加1,最近使用时间也更新啦,只是这里我遍历了一边队列,效率比较低,只是说这里先考虑这个最近不常用淘汰,实际过程肯定是查询为主。

使用PriorityQueue实现LFU和LRU

然后我们测试下:

使用PriorityQueue实现LFU和LRU

输出:

使用PriorityQueue实现LFU和LRU

 

LRU(Least recently used)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

那么我想就是把MyCache里面的排序根据时间来指定就行了,最近最久远的排在队列的前面淘汰掉。

当然这里只是想用PriorityQueue写着玩!

未完待续

https://github.com/woshiyexinjie/algorithm-xin

赞(0)
未经允许不得转载:ITyet » 使用PriorityQueue实现LFU和LRU
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址