Python中的LFU缓存实现

Question

我在Python中实现了一个LFU缓存，参考了优先队列的实现，具体可以查看这个链接：https://docs.python.org/2/library/heapq.html#priority-queue-implementation-notes

我在帖子最后提供了代码。

不过我觉得这个代码有一些严重的问题：
1. 假设只有一个页面被不断访问（比如说访问了50次）。但是这个代码会一直把已经添加的节点标记为“移除”，然后再把它添加到堆中。所以实际上会有50个不同的节点代表同一个页面。这会导致堆的大小大幅增加。
2. 这个问题几乎和http://www.geeksforgeeks.org/flipkart-interview-set-2-sde-2/中的电话面试第一题相似。那位提到双向链表相比于堆能提供更好的效率。有没有人能解释一下这是为什么？

from llist import dllist
import sys
from heapq import heappush, heappop

class LFUCache:
    heap = []
    cache_map = {}
    REMOVED = "<removed-task>"

    def __init__(self, cache_size):
        self.cache_size = cache_size

    def get_page_content(self, page_no):
        if self.cache_map.has_key(page_no):
            self.update_frequency_of_page_in_cache(page_no)  
        else:
            self.add_page_in_cache(page_no)

        return self.cache_map[page_no][2]       

    def add_page_in_cache(self, page_no):
        if (len(self.cache_map) == self.cache_size):
            self.delete_page_from_cache() 

        heap_node = [1, page_no, "content of page " + str(page_no)]
        heappush(self.heap, heap_node)
        self.cache_map[page_no] = heap_node

    def delete_page_from_cache(self):
        while self.heap:
            count, page_no, page_content = heappop(self.heap)
            if page_content is not self.REMOVED:
                del self.cache_map[page_no]
                return

    def update_frequency_of_page_in_cache(self, page_no): 
        heap_node = self.cache_map[page_no]
        heap_node[2] = self.REMOVED
        count = heap_node[0]

        heap_node = [count+1, page_no, "content of page " + str(page_no)]
        heappush(self.heap, heap_node)
        self.cache_map[page_no] = heap_node

def main():
    cache_size = int(raw_input("Enter cache size "))
    cache = LFUCache(cache_size)

    while 1:
        page_no = int(raw_input("Enter page no needed "))
        print cache.get_page_content(page_no)
        print cache.heap, cache.cache_map, "\n"


if __name__ == "__main__":
    main() 

Answer 1

效率这个问题挺复杂的。在实际应用中，通常建议先用最简单、最容易的算法，等到发现它运行得很慢时再考虑优化。优化的方式是通过分析代码，找出哪些地方运行得慢。

如果你在使用 CPython，这个问题就更复杂了，因为即使是用 C 实现的低效算法，有时也能比用 Python 实现的高效算法快。这是因为 C 的常数开销比较小；比如，用 Python 实现的双向链表通常比直接使用普通的 Python 列表慢，尽管理论上它应该更快。

简单算法：

对于 LFU（最不常用算法），最简单的做法是用一个字典，把键映射到（项目，频率）对象上，并在每次访问时更新频率。这样访问速度非常快（O(1)），但清理缓存的速度就慢了，因为你需要按频率排序来剔除使用最少的元素。不过在某些使用场景下，这种方法比其他“更聪明”的解决方案还要快。

你可以通过不把 LFU 缓存修剪到最大长度，而是当它变得太大时修剪到，比如说最大长度的 50%，来优化这个模式。这样一来，你的修剪操作就不需要频繁调用，相比读取操作，它可以更低效。

使用堆：

在（1）中，你使用了堆，因为它是存储优先队列的高效方式。但你并不是在实现优先队列。这样得到的算法在清理方面是优化过的，但在访问方面就不太好：你可以很容易找到最小的 n 个元素，但更新现有元素的优先级就不那么简单了。理论上，你需要在每次访问后重新平衡堆，这样效率就很低。

为了避免这个问题，你采用了一个小技巧，即即使元素被删除也保留它们。但这样做是以空间换时间。

如果你不想以时间换空间，可以在原地更新频率，然后在清理缓存之前重新平衡堆。这样你可以恢复快速的访问时间，但清理的时间会变慢，就像上面的简单算法一样。（我怀疑这两者之间没有速度差异，但我没有测量过。）

使用双向链表：

在（2）中提到的双向链表利用了可能发生的变化：一个元素要么作为最低优先级（0 次访问）被添加，要么是现有元素的优先级增加 1。你可以利用这些特点来设计数据结构：

你有一个按元素频率排序的双向链表。此外，你还有一个字典，把项目映射到那个链表中的元素。

访问一个元素的过程是：

• 要么它不在字典中，也就是说是一个新项目，这种情况下你可以直接把它添加到双向链表的末尾（O(1)）
• 要么它在字典中，这种情况下你增加元素的频率，并将它向左移动，直到链表重新排序（最坏情况下是 O(n)，但通常接近 O(1)）。

要清理缓存，你只需从链表末尾切掉 n 个元素（O(n)）。