复杂度为 O(1) 的「最不常用」缓存算法的 Python 实现,,未经许可,禁止转载!英文
复杂度为 O(1) 的「最不常用」缓存算法的 Python 实现,,未经许可,禁止转载!英文
本文由 编橙之家 - demoZ 翻译,黄利民 校稿。未经许可,禁止转载!英文出处:Laurent Luce。欢迎加入翻译组。
这篇文章描述了怎么用 Python 实现复杂度为 O(1) 的「最不常用」(Least Frequently Used, LFU)缓存回收算法。在 Ketan Shah、Anirban Mitra 和 Dhruv Matani的论文中有算法描述。实现中的命名是按照论文中的命名。
LFU 缓存回收机制对于 HTTP 缓存网络代理是非常有用的,我们可以从缓存中移除那些最不常使用的条目。
本文旨在设计一个其所有操作的时间复杂度都只有 O(1)的 LFU 缓存算法,这些操作包括了插入、访问和删除(回收)。
这个算法中用了双向链表。其一是用于访问频率,链表中的每个结点都包含一个链表,其中的元素有相同的访问频率。假设缓存中有5个元素。有两个元素被访问了一次,三个元素被访问了两次。在这个例子中,访问频率列表有两个结点(频率为1和2)。第一个频率结点的链表中有两个结点,第二个频率结点的链表中有三个结点。
我们要怎么构建它呢?我们需要的第一个对象是结点:
Pythonclass Node(object): """Node containing data, pointers to previous and next node.""" def __init__(self, data): self.data = data self.prev = None self.next = None
接下来是双向链表。每个结点有 prev 和 next 属性,分别等于前一个和下一个结点。head 被设为第一个结点,tail 被设为最后一个结点。
我们可以为双向链表定义方法来在链表尾部加入结点,插入结点,删除结点以及获得链表所有结点的数据。
Pythonclass DoublyLinkedList(object): def __init__(self): self.head = None self.tail = None # Number of nodes in list. self.count = 0 def add_node(self, cls, data): """Add node instance of class cls.""" return self.insert_node(cls, data, self.tail, None) def insert_node(self, cls, data, prev, next): """Insert node instance of class cls.""" node = cls(data) node.prev = prev node.next = next if prev: prev.next = node if next: next.prev = node if not self.head or next is self.head: self.head = node if not self.tail or prev is self.tail: self.tail = node self.count += 1 return node def remove_node(self, node): if node is self.tail: self.tail = node.prev else: node.next.prev = node.prev if node is self.head: self.head = node.next else: node.prev.next = node.next self.count -= 1 def get_nodes_data(self): """Return list nodes data as a list.""" data = [] node = self.head while node: data.append(node.data) node = node.next return data
访问频率双向链表中的每个结点都是一个频率结点(下图中的Freq Node)。它是一个结点,同时也是一个包含有相同频率的元素(下图中Item node)的双向性链表。每个条目结点都有一个指向其频率结点父亲的指针。
Pythonclass FreqNode(DoublyLinkedList, Node): """Frequency node containing linked list of item nodes with same frequency.""" 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 = self return node def insert_item_node(self, data, prev, next): node = self.insert_node(ItemNode, data, prev, next) node.parent = self return node def remove_item_node(self, node): self.remove_node(node) class ItemNode(Node): def __init__(self, data): Node.__init__(self, data) self.parent = None
条目结点的数据等于我们要存储的元素的键,这个键可以是一条HTTP请求。内容本身(例如HTTP响应)存储在字典中。字典中的每个值是LfuItem类型,”data”是缓存的内容,”parent”是指向频率结点的指针,”node”是指向频率结点下条目结点的指针。
Pythonclass LfuItem(object): def __init__(self, data, parent, node): self.data = data self.parent = parent self.node = node
我们已经定义了数据对象类,现在可以定义缓存对象类了。它有一个双向链表(访问频率链表)和一个包含LFU条目(上面的LfuItem)的字典。我们定义两个方法:一个用来插入频率结点,一个用来删除频率结点。
Pythonclass Cache(DoublyLinkedList): def __init__(self): DoublyLinkedList.__init__(self) self.items = dict() 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)
下一步是定义方法来插入到缓存,访问缓存以及从缓存中删除。
我们来看看插入方法的逻辑。它以一个键和值为参数,例如HTTP请求和响应。如果没有频率为1的频率结点,它就被插入到访问频率双向链表的开头。一个条目结点被加入到频率结点的条目双向链表。键和值被加入到字典中。复杂度是O(1)。
Pythondef insert(self, key, value): if key in self.items: raise DuplicateException('Key exists') freq_node = self.head if not freq_node or freq_node.data != 1: freq_node = self.insert_freq_node(1, None, freq_node) freq_node.add_item_node(key) self.items[key] = LfuItem(value, freq_node)
我们在缓存中插入两个元素,得到:
我们来看看访问方法的逻辑。如果键不存在,我们抛出异常。如果键存在,我们把条目结点移到频率加一的频率结点的链表中(如果频率结点不存在就增加这个结点)。复杂度是O(1)。
Pythondef access(self, key): try: tmp = self.items[key] except KeyError: raise NotFoundException('Key not found') freq_node = tmp.parent next_freq_node = freq_node.next if 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.parent = next_freq_node freq_node.remove_item_node(tmp.node) if freq_node.count == 0: self.remove_freq_node(freq_node) tmp.node = item_node return tmp.data
如果我们访问Key 1的条目,这个条目结点就被移动到频率为2的频率结点之下。我们得到:
如果我们访问Key 2的条目,这个条目结点就被移动到频率为2的频率结点之下。频率为1的频率结点会被删除(译注:因为它之下没有条目结点了),我们得到:
我们再看看delete_lfu方法。它把最不常使用的条目从缓存中删除。为此,它删除第一个频率结点下的第一个条目结点,同时从字典删除对应的LFUItem对象。如果此操作过后,频率结点的链表为空,就删除这个频率结点。
Pythondef delete_lfu(self): """Remove the first item node from the first frequency node. Remove the item from the dictionary. """ if not self.head: raise NotFoundException('No frequency nodes found') freq_node = self.head item_node = freq_node.head del self.items[item_node.data] freq_node.remove_item_node(item_node) if freq_node.count == 0: self.remove_freq_node(freq_node)
如果在缓存上调用delete_lfu,数据为Key 1的条目结点和它的LFUItem将被删除。我们得到:
打赏支持我翻译更多好文章,谢谢!
打赏译者
打赏支持我翻译更多好文章,谢谢!
任选一种支付方式
相关内容
- 暂无相关文章
评论关闭