最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
LRU 缓存 Python 简单实现
时间:2016-10-18 编辑:简简单单 来源:一聚教程网
LRU (Least Recently Used) 最近最久未使用
In computing, cache algorithms (also frequently called cache replacement algorithms or cache replacement policies) are optimizing instructions—or algorithms—that a computer program or a hardware-maintained structure can follow in order to manage a cache of information stored on the computer. When the cache is full, the algorithm must choose which items to discard to make room for the new ones. --Wikipedia
更新:
最近刚好看到 Leetcode 上一道关于LRUCache的题
Design and implement a data structure for Least Recently Used (LRU) cache.
It should support the following operations: get and set .
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
以下是实现:(代码可以在 Github 上找到)
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity = capacity
self.__values = {}
self.__access = []
def get(self, key):
"""
:rtype: int
"""
if key in self.__values:
self.__access.remove(key)
self.__access.append(key)
return self.__values[key]
else:
return -1
def set(self, key, value):
"""
:type key: int
:type value: int
:rtype: nothing
"""
if not self.capacity:
return
if key in self.__values:
self.__access.remove(key)
else:
while len(self.__values) >= self.capacity:
self.cleanup()
self.__access.append(key)
self.__values[key] = value
def cleanup(self):
del self.__values[self.__access.pop(0)]
使用Python来实现LRUCacheDict
dict容量固定
记录每个key的最后一次访问时间与过期时间
在每次增加/查询操作时,对dict进行清理,先清除过期的key,然后清除最早访问的key
具体实现:
以下代码可以在 Github 上找到
import time
from collections import OrderedDict
class LRUCacheDict(object):
def __init__(self, expiration=15*60, maxsize=128):
self.expiration = expiration
self.maxsize = maxsize
self.__expire_times = OrderedDict()
self.__access_times = OrderedDict()
self.__values = {}
def __setitem__(self, key, value):
t = int(time.time())
self.__delitem__(key)
self.__values[key] = value
self.__access_times[key] = t
self.__expire_times[key] = t + self.expiration
self.cleanup()
def __getitem__(self, key):
t = int(time.time())
del self.__access_times[key]
self.__access_times[key] = t
self.cleanup()
return self.__values[key]
def __delitem__(self, key):
if key in self.__values:
del self.__values[key]
del self.__access_times[key]
del self.__expire_times[key]
def size(self):
return len(self.__values)
def clear(self):
self.__values.clear()
self.__access_times.clear()
self.__expire_times.clear()
def cleanup(self):
t = int(time.time())
for key, expire in self.__expire_times.iteritems():
if expire < t:
self.__delitem__(key)
while self.size() > self.maxsize:
for key in self.__access_times:
self.__delitem__(key)
break
相关文章
- Smarty 缓存集合简单讲解 08-14
- PHP导出数据超时的优化建议解读 10-31
- PHP之mysql位运算解析 10-31
- Laravel实现登录跳转功能解析 10-31
- php双向队列解读 10-31
- Laravel异常上下文解决教程 10-24