Python LFU算法实现

本文是译文，原文参见: https://www.laurentluce.com/posts/least-frequently-used-cache-eviction-scheme-with-complexity-o1-in-python/

这篇文章描述了在Python中实现O(1)"最少使用"(LFU)缓存驱逐策略算法。这个算法在由Prof. Ketan Shah, Anirban Mitra 和 Dhruv Matani写的论文中有描述。本文中的实现提及的命名和该论文的命名保持一致。

LFU缓存驱逐策略算法是很有用的，例如在HTTP缓存代理中，我们想从缓存中删除最少使用的元素。

这里的目标是LFU缓存策略算法有运行时复杂度为O(1)，所有操作都是O(1)。包括插入、访问和删除(驱逐)。

这个算法使用了双向列表，用于代表访问频率。它的每一个节点包含一组元素，这一组元素的访问频率相同（One for the access frequency and each node in that list contains a list with the elements of same access frequency）。假设我们有 5个元素在我们的缓存中，2个元素访问了1次，3个元素访问了2次。在这种情况下，访问频率列表下就有两个节点元素(一个是访问频率1， 一个是2)。那么，在双向链表下的所有节点上，第一个访问频率节点下有两个两个节点元素，第二个有三个节点元素。

lfu1.png

那么如何实现呢？第一个需要实现的是node对象

class 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属性分别代表前一个节点和后一个节点。头部节点为第一个节点，尾部节点为最后一个节点

lfu2.png

在我们的双向列表，可以使用方法来定义在链表最后添加节点，插入节点，删除节点和获取链表所有节点的数据。

class 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节点在下图）。它是一个节点，同时也是一个双向列表，节点包含一组item节点(Item节点)，它们是相同频率的。每一个Item节点有一个指针指向父频率节点。

lfu3.png

class 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

Freq节点下的item节点的数据和我们缓存的数据的键是一样的。例如，一个http请求可以是一个键，内容本身（http响应内容）存储在字典（过会会看到）上。每一个value在字典上都是一个LfuItem类型的数据，LfuItem的data字段就是存储的缓存数据。parent字段指向Freq节点，node节点指向的是freq节点下的item节点。

lfu4.png

class LfuItem(object):
    def __init__(self, data, parent, node):
        self.data = data
        self.parent = parent
        self.node = node

我们定义了我们的数据对象类，现在我们可以定义缓存对象类。它有一个双向链表（访问频率链表）和一个字典来包含LFU item。我们定义了两个方法：一个用来插入一个频率节点，一个用来删除一个频率节点。

class 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的频率节点不存在，会插入在访问频率链表的开始位置。一个item节点会添加到频率节点下的item链表。键和值会添加到字典。复杂度为O（1）。

def 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)

    item_node = freq_node.add_item_node(key)
    self.items[key] = LfuItem(value, freq_node, item_node)

我们插入两个元素到我们的缓存，最后我们得到：

lru05.png

我们来看访问数据方法的逻辑，如果键不存在，我们抛出一个异常。如果键存在，我们移动item节点到频率节点到频率+1的节点列表上（添加一个频率节点如果不存在）。复杂度为O（1）。

def 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

如果我们访问键1，item节点数据为1的节点会移动到频率节点频率为2的地方。我们最终得到：

lfu6.png

如果我们访问键2，item节点为2的会移动到频率为2的节点上，频率节点为1的将会移除。我们最终得到：

lfu7.png

让我们来看一下delele_lfu方法。它从缓存上移除了最少使用频率的item。为了实现这一点，它移除了第一个频率节点下的第一个item，同时从字典中删除。如果这个操作后，频率节点为空，这个频率节点将会被删除。

def 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_flu从我们的缓存中，item节点对应的数据也就是键等于1的时候将会移除，LFUItem也会。我们最终得到：

lfu8.png

Github repo for the complete implementation.