Shw*_*eta 1 python heap caching priority-queue
我已经在https://docs.python.org/2/library/heapq.html#priority-queue-implementation-notes中给出的Priority Queue Implementation的帮助下在python中实现了LFU缓存
我在帖子末尾给出了代码。
但是我觉得代码有一些严重的问题：
1.给一个场景，假设只有一个页面被连续访问（比如说50次）。但是此代码将始终将已添加的节点标记为“已删除”，并将其再次添加到堆中。因此，基本上，同一页面将有50个不同的节点。因此，极大地增加了堆大小。
2.这个问题几乎与http://www.geeksforgeeks.org/flipkart-interview-set-2-sde-2/的电话采访Q1相似，
并且该人提到双向链接列表与堆。谁能解释我，如何？
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()
效率是一件棘手的事情。在现实世界的应用程序中，使用最简单，最简单的算法通常是个好主意，并且只有在可测量的速度很慢时才开始进行优化。然后，您可以通过进行分析来找出代码运行缓慢的位置，从而进行优化。
如果您使用的是CPython，它会变得特别棘手，因为由于常量因子较大，即使使用C语言实现的低效率算法也可以击败使用Python实现的高效算法。例如，用Python实现的双向链接列表往往比仅使用普通的Python列表要慢得多，即使在理论上应该更快的情况下。
简单算法：
对于LFU，最简单的算法是使用字典，该字典将键映射到（项目，频率）对象，并在每次访问时更新频率。这样可以使访问非常快（O（1）），但是由于需要按频率排序以减少使用最少的元素，因此修剪缓存的速度较慢。但是，对于某些使用特性，这实际上比其他“更智能”的解决方案要快。
您不仅可以将LFU缓存修剪到最大长度，还可以将它修剪成最大长度的50％（例如，当它变得太大时），以优化此模式。这意味着您的修剪操作很少被调用，因此与读取操作相比效率较低。
使用堆：
在（1）中，您使用了堆，因为这是存储优先级队列的有效方法。但是您没有实现优先级队列。生成的算法针对修剪（但不能访问）进行了优化：您可以轻松找到n个最小的元素，但是如何更新现有元素的优先级并不是很明显。从理论上讲，您每次访问后都必须重新平衡堆，这是非常低效的。
为了避免这种情况，您添加了一个技巧，即使元素被删除，也可以保留它们。但这在时间上是有交换的。
如果您不想及时交易，则可以就地更新频率，并在修剪缓存之前重新平衡堆。就像上面的简单算法一样，您可以以较慢的修剪时间来重新获得快速的访问时间。（我怀疑两者之间是否存在速度差异，但我尚未对此进行测量。）
使用双向链接列表：
（2）中提到的双向链接列表利用了此处可能发生的更改的性质：将元素添加为最低优先级（访问0），或者将现有元素的优先级精确地增加1。可以使用这些元素如果您按以下方式设计数据结构，则对您有利：
您有一个双向链接的元素列表，该列表按元素的频率排序。此外，您还有一个字典，可将项目映射到该列表中的元素。
访问元素意味着：
要修剪缓存，您只需从列表末尾（O（n））删除n个元素。