Python实现的最近最少使用算法
作者:Sephiroth 发布时间:2022-07-10 22:48:27
标签:Python,算法
本文实例讲述了Python实现的最近最少使用算法。分享给大家供大家参考。具体如下:
# lrucache.py -- a simple LRU (Least-Recently-Used) cache class
# Copyright 2004 Evan Prodromou <evan@bad.dynu.ca>
# Licensed under the Academic Free License 2.1
# Licensed for ftputil under the revised BSD license
# with permission by the author, Evan Prodromou. Many
# thanks, Evan! :-)
#
# The original file is available at
# http://pypi.python.org/pypi/lrucache/0.2 .
# arch-tag: LRU cache main module
"""a simple LRU (Least-Recently-Used) cache module
This module provides very simple LRU (Least-Recently-Used) cache
functionality.
An *in-memory cache* is useful for storing the results of an
'expe\nsive' process (one that takes a lot of time or resources) for
later re-use. Typical examples are accessing data from the filesystem,
a database, or a network location. If you know you'll need to re-read
the data again, it can help to keep it in a cache.
You *can* use a Python dictionary as a cache for some purposes.
However, if the results you're caching are large, or you have a lot of
possible results, this can be impractical memory-wise.
An *LRU cache*, on the other hand, only keeps _some_ of the results in
memory, which keeps you from overusing resources. The cache is bounded
by a maximum size; if you try to add more values to the cache, it will
automatically discard the values that you haven't read or written to
in the longest time. In other words, the least-recently-used items are
discarded. [1]_
.. [1]: 'Discarded' here means 'removed from the cache'.
"""
from __future__ import generators
import time
from heapq import heappush, heappop, heapify
# the suffix after the hyphen denotes modifications by the
# ftputil project with respect to the original version
__version__ = "0.2-1"
__all__ = ['CacheKeyError', 'LRUCache', 'DEFAULT_SIZE']
__docformat__ = 'reStructuredText en'
DEFAULT_SIZE = 16
"""Default size of a new LRUCache object, if no 'size' argument is given."""
class CacheKeyError(KeyError):
"""Error raised when cache requests fail
When a cache record is accessed which no longer exists (or never did),
this error is raised. To avoid it, you may want to check for the existence
of a cache record before reading or deleting it."""
pass
class LRUCache(object):
"""Least-Recently-Used (LRU) cache.
Instances of this class provide a least-recently-used (LRU) cache. They
emulate a Python mapping type. You can use an LRU cache more or less like
a Python dictionary, with the exception that objects you put into the
cache may be discarded before you take them out.
Some example usage::
cache = LRUCache(32) # new cache
cache['foo'] = get_file_contents('foo') # or whatever
if 'foo' in cache: # if it's still in cache...
# use cached version
contents = cache['foo']
else:
# recalculate
contents = get_file_contents('foo')
# store in cache for next time
cache['foo'] = contents
print cache.size # Maximum size
print len(cache) # 0 <= len(cache) <= cache.size
cache.size = 10 # Auto-shrink on size assignment
for i in range(50): # note: larger than cache size
cache[i] = i
if 0 not in cache: print 'Zero was discarded.'
if 42 in cache:
del cache[42] # Manual deletion
for j in cache: # iterate (in LRU order)
print j, cache[j] # iterator produces keys, not values
"""
class __Node(object):
"""Record of a cached value. Not for public consumption."""
def __init__(self, key, obj, timestamp, sort_key):
object.__init__(self)
self.key = key
self.obj = obj
self.atime = timestamp
self.mtime = self.atime
self._sort_key = sort_key
def __cmp__(self, other):
return cmp(self._sort_key, other._sort_key)
def __repr__(self):
return "<%s %s => %s (%s)>" % \
(self.__class__, self.key, self.obj, \
time.asctime(time.localtime(self.atime)))
def __init__(self, size=DEFAULT_SIZE):
# Check arguments
if size <= 0:
raise ValueError, size
elif type(size) is not type(0):
raise TypeError, size
object.__init__(self)
self.__heap = []
self.__dict = {}
"""Maximum size of the cache.
If more than 'size' elements are added to the cache,
the least-recently-used ones will be discarded."""
self.size = size
self.__counter = 0
def _sort_key(self):
"""Return a new integer value upon every call.
Cache nodes need a monotonically increasing time indicator.
time.time() and time.clock() don't guarantee this in a
platform-independent way.
"""
self.__counter += 1
return self.__counter
def __len__(self):
return len(self.__heap)
def __contains__(self, key):
return self.__dict.has_key(key)
def __setitem__(self, key, obj):
if self.__dict.has_key(key):
node = self.__dict[key]
# update node object in-place
node.obj = obj
node.atime = time.time()
node.mtime = node.atime
node._sort_key = self._sort_key()
heapify(self.__heap)
else:
# size may have been reset, so we loop
while len(self.__heap) >= self.size:
lru = heappop(self.__heap)
del self.__dict[lru.key]
node = self.__Node(key, obj, time.time(), self._sort_key())
self.__dict[key] = node
heappush(self.__heap, node)
def __getitem__(self, key):
if not self.__dict.has_key(key):
raise CacheKeyError(key)
else:
node = self.__dict[key]
# update node object in-place
node.atime = time.time()
node._sort_key = self._sort_key()
heapify(self.__heap)
return node.obj
def __delitem__(self, key):
if not self.__dict.has_key(key):
raise CacheKeyError(key)
else:
node = self.__dict[key]
del self.__dict[key]
self.__heap.remove(node)
heapify(self.__heap)
return node.obj
def __iter__(self):
copy = self.__heap[:]
while len(copy) > 0:
node = heappop(copy)
yield node.key
raise StopIteration
def __setattr__(self, name, value):
object.__setattr__(self, name, value)
# automagically shrink heap on resize
if name == 'size':
while len(self.__heap) > value:
lru = heappop(self.__heap)
del self.__dict[lru.key]
def __repr__(self):
return "<%s (%d elements)>" % (str(self.__class__), len(self.__heap))
def mtime(self, key):
"""Return the last modification time for the cache record with key.
May be useful for cache instances where the stored values can get
'stale', such as caching file or network resource contents."""
if not self.__dict.has_key(key):
raise CacheKeyError(key)
else:
node = self.__dict[key]
return node.mtime
if __name__ == "__main__":
cache = LRUCache(25)
print cache
for i in range(50):
cache[i] = str(i)
print cache
if 46 in cache:
print "46 in cache"
del cache[46]
print cache
cache.size = 10
print cache
cache[46] = '46'
print cache
print len(cache)
for c in cache:
print c
print cache
print cache.mtime(46)
for c in cache:
print c
希望本文所述对大家的Python程序设计有所帮助。
0
投稿
猜你喜欢
- 初学python,对python的对齐很重视,为了防止出错,使用spyder工具提供的功能下面是方法:1、首先打开Tools菜单栏下的Pre
- 本文借用HTML的css语法,将样式表应用到窗口部件。这里只是个简单的例子,实际上样式表的语法很丰富。以下类似于css: StyleShee
- 先看下面例子的效果:<INPUT TYPE="text" NAME=""&
- ASP+Access数据库的18条安全法则:1.首先,我们需要过滤所有客户端提交的内容,其中包括?id=N一类,另外还有提交的html代码中
- 采集中 或者 在线添加文章中 都可以用到此功能俺自己在baidu上搜索的保存远程图片到本地的代码 感觉比较难用点 而且没有现成的比较全的代码
- 1、简单的按钮js事件 用于判断和显示提示 <script type="text/javascript&
- 处理多个数据和多文件时,使用for循环的速度非常慢,此时需要用多线程来加速运行进度,常用的模块为multiprocess和joblib,下面
- 1、PandasPython Data Analysis Library 或 pandas 是基于NumPy 的一种工具,相当于这是Pyth
- 以Python 3.x版本为主一、条件语句条件语句基本结构0或null为false,其余则为trueif 判定条件:语句块...可多行els
- 这个函数用于储存图片,将数组保存为图像此功能仅在安装了Python Imaging Library(PIL)时可用。版本也比较老了,新的替代
- 本文实例讲述了Python求两个文本文件以行为单位的交集、并集与差集的方法。分享给大家供大家参考。具体实现方法如下:s1 = set(ope
- 本文实例讲述了python config文件的读写操作。分享给大家供大家参考,具体如下:1、设置配置文件[mysql]host = 1234
- html代码:<!DOCTYPE html><html lang="en"><head&g
- 听说安全地断开Connection连接的记录集可以提高ASP的运行速度,请问如何实现?很多人会将一个Connection对象存储在Appli
- 简单介绍正则表达式并不是Python的一部分。正则表达式是用于处理字符串的强大工具,拥有自己独特的语法以及一个独立的处理引擎,效率上可能不如
- 一、匿名块和命名块◆PL/SQL块分为良好总:命名块和匿名块。◆匿名块:以declare或begin开始,每次执行匿名块都要通过客户端工具将
- 一、函数入门1.概念函数是可以重复执行一定任务的代码片段,具有独立的固定的输入输出接口。函数定义的本质,是给一段代码取个名字,方便以后重复使
- 1、目的:在Python中实现只读取扩展名为xlsx的文件解决方法:使用os模块。解决思路:1、确定目录2、循环遍历每一个文件3、筛选符合条
- 一、前言在Python提供了re模块,用于实现正则表达式的操作。在实现时,可以使用re模块提供的方法(如,search()、match()、
- 目录方法一:直接调用函数运行方法二:使用偏函数来执行方法三:使用 eval 动态执行方法四:使用 getattr 动态获取执行方法五:使用类