python中LFU缓存的实现

Question

我已经在python中实现了LFU缓存，并借助于上给出的优先级队列实现 https://docs.python.org/2/library/heapq.html#priority-queue-implementation-notes

我在帖子的最后给出了密码。在

但我觉得代码有一些严重的问题：
1为了给出一个场景，假设只有一个页面被连续访问（比如50次）。但此代码将始终将已添加的节点标记为“已删除”，然后再次将其添加到堆中。所以基本上，对于同一个页面，它将有50个不同的节点。因此大大增加了堆大小。
2这个问题与电话采访的Q1几乎相似 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中实现的高效算法；例如，在Python中实现的双链接列表往往比简单地使用普通Python列表慢得多，即使在理论上应该更快的情况下。在

简单算法：

对于LFU，最简单的算法是使用字典将键映射到（item，frequency）对象，并在每次访问时更新频率。这使得访问速度非常快（O（1）），但是修剪缓存的速度较慢，因为您需要按频率进行排序，以删除最少使用的元素。不过，对于某些使用特性，这实际上比其他“更聪明”的解决方案要快。在

您可以针对这种模式进行优化，方法不是简单地将LFU缓存修剪到最大长度，而是在其增长过大时将其修剪为最大长度的50%。这意味着prune操作很少被调用，因此与read操作相比，它可能效率低下。在

使用堆：

在（1）中，使用堆是因为这是存储优先级队列的有效方法。但您没有实现优先级队列。生成的算法针对修剪进行了优化，但不是访问：您可以轻松找到n个最小的元素，但如何更新现有元素的优先级就不那么明显了。理论上，每次访问后都必须重新平衡堆，这是非常低效的。在

即使是被删除的元素，也要避免被删除。但这是以空间换取时间的。在

如果您不想以时间为代价，您可以就地更新频率，并在修剪缓存之前简单地重新平衡堆。您可以以较慢的修剪时间为代价重新获得快速访问时间，如上面的简单算法。（我怀疑两者之间是否存在速度差，但我没有测量过这一点。）

使用双链接列表：

（2）中提到的双重链接列表利用了这里可能发生的变化的性质：一个元素被添加为最低优先级（0次访问），或者一个现有元素的优先级正好增加1。如果按以下方式设计数据结构，则可以使用这些属性：

您有一个按元素频率排序的元素的双链接列表。此外，您还有一个字典，可以将项映射到该列表中的元素。在

访问元素意味着：

• 或者它不在字典中，也就是说，它是一个新条目，在这种情况下，您可以简单地将它附加到双链接列表（O（1））的末尾
• 或者是在字典中，在这种情况下，增加元素的频率，并在双链接列表中向左移动，直到列表再次排序（O（n）最坏情况，但通常更接近O（1））。在

要修剪缓存，只需从列表末尾（O（n））中删除n个元素。在