本文主要是介绍复杂度为O(1)的最不常用[LFU]缓存算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
参考链接：http://python.jobbole.com/82424/
这篇文章描述了怎么用 Python 实现复杂度为 O(1) 的「最不常用」（Least Frequently Used， LFU）缓存回收算法。在 Ketan Shah、Anirban Mitra 和 Dhruv Matani的论文中有算法描述。实现中的命名是按照论文中的命名。
LFU 缓存回收机制对于 HTTP 缓存网络代理是非常有用的，我们可以从缓存中移除那些最不常使用的条目。本文旨在设计一个其所有操作的时间复杂度都只有 O(1)的 LFU 缓存算法，这些操作包括了插入、访问和删除（回收）。
这个算法中用了双向链表。其一是用于访问频率，链表中的每个结点都包含一个链表，其中的元素有相同的访问频率。假设缓存中有5个元素。有两个元素被访问了一次，三个元素被访问了两次。在这个例子中，访问频率列表有两个结点（频率为1和2）。第一个频率结点的链表中有两个结点，第二个频率结点的链表中有三个结点。
相关的python代码如下:
class Node(object):def __init__(self,data):self.data= dataself.prev = Noneself.next = Noneclass DoublyLinkedList(object):def __init__(self):self.head = Noneself.tail = Noneself.count= 0def add_node(self,cls,data):return self.insert_node(cls,data,self.tail,None)def insert_node(self,cls,data,prev,next):node = cls(data)node.prev = prevnode.next = nextif prev:prev.next = nodeif next:next.prev = nodeif not self.head or next is self.head:self.head = nodeif not self.tail or prev is self.tail:self.tail = nodeself.count +=1return nodedef remove_node(self,node):if node is self.head:self.head = node.nextelse:node.prev.next = node.nextif node is self.tail:self.tail = node.prevelse:node.next.prev = node.prevself.count -=1;def get_nodes_data(self):data=[]node = self.headwhile node:data.append(node.data)
#print "asd"node = node.nextreturn data
class FreqNode(DoublyLinkedList,Node):def __init__(self,data):DoublyLinkedList.__init__(self)Node.__init__(self,data)def add_item_node(self,data):node = self.add_node(ItemNode,data)node.parent= selfreturn nodedef insert_item_node(self,data,prev,next):self.insert_node(ItemNode,data,prev,next)node.parent = selfreturn nodedef remove_item_node(self,node):self.remove_node(node)
class ItemNode(Node):def __init__(self,data):Node.__init__(self,data)self.parent = None
class LfuItem(object):def __init__(self,data,parent,node):self.data = dataself.parent = parentself.node = node
class Cache(DoublyLinkedList):def __init__(self):DoublyLinkedList.__init__(self)self.items = {}def insert_freq_node(self,data,prev,next):return self.insert_node(FreqNode,data,prev,next)def remove_freq_node(self,node):self.remove_node(node)def insert(self,key,value):if key in self.items:raise DuplicateException('key exists')freq_node = self.headif not freq_node or freq_node.data != 1:
#print "adassd"freq_node = self.insert_freq_node(1,None,freq_node)item_node = freq_node.add_item_node(key)self.items[key] = LfuItem(value,freq_node,item_node)def access(self,key):try:tmp_node = self.items[key]except KeyError:raise NotFoundException('key not found')freq_node = tmp_node.parentnext_freq_node = freq_node.nextif not next_freq_node or next_freq_node.data != freq_node.data+1:next_freq_node = self.insert_freq_node(freq_node.data+1,freq_node,next_freq_node)item_node = next_freq_node.add_item_node(key)tmp_node.parent = next_freq_nodefreq_node.remove_item_node(tmp_node.node)if(freq_node.count == 0):self.remove_freq_node(freq_node)tmp_node.node = item_nodereturn tmp_node.datadef delete_lfu(self):if not self.head:raise NotFoundException('No frequency nodes found')freq_node = self.headitem_node = freq_node.headdel self.items[item_node.data]freq_node.remove_item_node(item_node)if freq_node.count == 0:self.remove_freq_node(freq_node) def funcs(da):for d in da:print d
if __name__ == '__main__':ca = Cache()ca.insert(1,"123")ca.insert(2,"122")ca.insert(3,"322")da = ca.get_nodes_data()print ca.access(1)print ca.access(2)print ca.access(3)print ca.access(3) funcs(ca.get_nodes_data())这篇关于复杂度为O(1)的最不常用[LFU]缓存算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
