什么是小而简单的缓存的最佳数据结构

我经常需要相对较小的（< 10000条目< 1kb）缓存来加速计算。我通常的代码如下所示：什么是小而简单的缓存的最佳数据结构

cache = {} 
def calculate_caches(parms): 
    if parms not in cache: 
     cache[parms] = calculate(parms) 
    return cache[parms]

工作正常，但对于长时间运行的进程我害怕内存泄漏。所以，我经常实施蛮力记忆夹紧这样的：

if len(cache) > 1000: 
    cache = {}

合理运作良好，在大多数情况下，仍然是干净，简单的代码。但是，如果我想要一个真正的LRU strategy我需要时间戳和缓存条目。使用字典的问题是，现在缓存过期意味着遍历整个缓存，既不优雅也不高效。

cache = {} 
def calculate_caches(parms): 
    if parms not in cache: 
     cache[parms] = (time.time(), calculate(parms)) 
    expire() 
    return cache[parms][1] 

def expire() 
    if len(cache) > 1000: 
     mintime = time.time() 
     time2key = {} 
     for key, (timestamp, val) in cache.items(): 
      mintime = min([mintime, timestamp]) 
      time2key[timestamp] = key 
     if mintime in time2key: 
      del cache[time2key[mintime]]

是否有优选的方法/数据结构来实现临时缓存？

我的问题与this question很相似，但我不需要列表按时间排序，我不希望被骗。

来源

2009-07-08 max

一个非常简单的方法来做到这一点，而不使用时间戳将是有一个ordered dictionary，你最后有MRU（这是，当再次请求同一个对象，你删除它和在dict结尾处再次添加它），因此，当您需要过期时，如果大小超过限制，则只需从有序字典的开头删除一个X大小的片段。

效率现在取决于如何执行该命令字典。

来源

2009-07-08 06:45:05

我怀疑这是一颗金色的子弹;最佳策略在很大程度上取决于缓存未命中的成本以及计算参数的时间分布。

垃圾收集方法可能会给你一些启发。如果您将缓存视为堆，并将缓存命中为引用，那么您有问题需要高效地收集缓存的结果，其中包含低的（非零）命中数。这个问题比GC更宽容，因为你攻击你的任何东西都可以重新计算。

以这种方式对您的方法进行改进将为频繁出现的参数引入额外缓存。为每个缓存命中增加的缓存值添加一个计数器。当传递一些阈值时，缓存的值被提升到附加缓存。两代缓存都可以调整大小，所以对内存使用仍然有很大的限制。这是一个经验问题，如果（可能）降低高速缓存未命中证明的开销（在两个缓存查找，点击计数器，复制等）......

来源

2009-07-08 07:10:53 othercriteria

你可以看看Java的LinkedHashMap和LinkedHashSet寻找灵感。基本上它保持一个双向链接列表和可选的访问顺序。

为了维护LRU，您可以定义策略来删除最老的条目（靠近链表头），同时插入一个新条目。

来源

2017-09-12 07:38:09 shailendra1118

什么是小而简单的缓存的最佳数据结构

回答

相关问题