未加星标

LRU 缓存 Python 简单实现

字体大小 | |
[开发(python) 所属分类 开发(python) | 发布者 店小二03 | 时间 2016 | 作者 红领巾 ] 0人收藏点击收藏
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

已上实现参考:

https://pypi.python.org/pypi/py_lru_cache

本文开发(python)相关术语:python基础教程 python多线程 web开发工程师 软件开发工程师 软件开发流程

主题: GitPythonUC
分页:12
转载请注明
本文标题:LRU 缓存 Python 简单实现
本站链接:http://www.codesec.net/view/484835.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 开发(python) | 评论(0) | 阅读(22)