<p>Python3.3中的<a href="http://docs.python.org/3.3/library/functools.html#functools.lru_cache" rel="nofollow">LRU cache</a>有O(1)插入、删除和搜索。</p>
<p>该设计使用一个循环的双链接条目列表(从最早到最新排列)和一个哈希表来定位各个链接。缓存命中使用哈希表查找相关链接并将其移动到列表的头部。缓存未命中删除最旧的链接并在链接列表的开头创建新链接。</p>
<p>这是一个简化(但很快)的版本,由33行非常基本的Python组成(只使用简单的字典和列表操作)。它运行在Python2.0及更高版本(或PyPy或Jython或Python3.x)上:</p>
<pre><code>class LRU_Cache:
def __init__(self, original_function, maxsize=1024):
# Link structure: [PREV, NEXT, KEY, VALUE]
self.root = [None, None, None, None]
self.root[0] = self.root[1] = self.root
self.original_function = original_function
self.maxsize = maxsize
self.mapping = {}
def __call__(self, *key):
mapping = self.mapping
root = self.root
link = mapping.get(key)
if link is not None:
link_prev, link_next, link_key, value = link
link_prev[1] = link_next
link_next[0] = link_prev
last = root[0]
last[1] = root[0] = link
link[0] = last
link[1] = root
return value
value = self.original_function(*key)
if len(mapping) >= self.maxsize:
oldest = root[1]
next_oldest = oldest[1]
root[1] = next_oldest
next_oldest[0] = root
del mapping[oldest[2]]
last = root[0]
last[1] = root[0] = mapping[key] = [last, root, key, value]
return value
if __name__ == '__main__':
p = LRU_Cache(ord, maxsize=3)
for c in 'abcdecaeaa':
print(c, p(c))
</code></pre>