python实现的最近最少使用算法

wss1051

　　LFU(Least Frequently Used，最少使用)是一种缓存管理算法，其过期策略为替换出缓存中最少使用项。若各项使用次数相等，则参考LRU(Least Recently Used，最近最少使用)进行替换。
　　

　　实现过程中，一直希望绕开链表去实现。尝试过用优先队列，但是优先队列对于优先级的调整处理很复杂，而当替换某些缓存项时，优先队列里保存的索引值又会过期，暂时未想到解决方法。一个比较拙劣的实现是使用sort()对使用次数进行排序，Python内置的sort相当独特，是一种运用了merge sort(合并排序)和insertion sort(插入排序)的混合排序，因其作者Tim Peter而命名。据说实际运行效果中，因为利用了子表的有序性，实际比较次数往往远小于O(nlogn)。
　　

　　目前的实现，采用了双向链表进行管理。链表中的位置表明了该项的使用次数在全体成员中的序号。通过一个dict直接找到链表中的项，然后通过比较相邻项的访问次数决定是否调整位置。

　　代码见：
　　http://github.com/spin6lock/my_memory_cache_with_NFU