python 实现的最近最少使用算法
LFU(Least Frequently Used，最少使用 ) 是一种缓存管理算法，其过期策略为替换出缓存中最少使用项。若各项使用次数相等，则参考 LRU(Least Recently Used，最近最少使用 ) 进行替换。
实现过程中，一直希望绕开链表去实现。尝试过用优先队列，但是优先队列对于优先级的调整处理很复杂，而当替换某些缓存项时，优先队列里保存的索引值又会过期，暂时未想到解决方法。一个比较拙劣的实现是使用 sort() 对使用次数进行排序，Python 内置的 sort 相当独特，是一种运用了 merge sort( 合并排序 ) 和 insertion sort( 插入排序 ) 的混合排序，因其作者 Tim Peter 而命名。据说实际运行效果中，因为利用了子表的有序性，实际比较次数往往远小于 O(nlogn)。
目前的实现，采用了双向链表进行管理。链表中的位置表明了该项的使用次数在全体成员中的序号。通过一个 dict 直接找到链表中的项，然后通过比较相邻项的访问次数决定是否调整位置。
代码见：
Tag:
python