LRU算法的实现(Python版)
source link: https://allenwind.github.io/blog/3887/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
NLP、深度学习、机器学习、Python、Go
LRU算法的实现(Python版)
上文Go现LRU算法,给出了Go语言的实现。本文使用Python给出实现,体会两种语言的差别和美丽。
Python3标准库中functools.lru_cache
已经实现了LRU算法,但Python2中并没有。对于兼容两个版本的开发,需要使用Python实现兼容functools.lru_cache
接口的LRU算法。从源码看,functools.lru_cache
的实现采用C元,封装在内建模块_functools
中,效率非常高。
在Python2下我们需要给出自己的实现。
双链表+Map的实现
双链表结点
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
self.prev = None
LRU算法的实现
class LRUCache:
def __init__(self, size=10):
# 两哨兵结点
self.head = Node(None, None)
self.tail = Node(None, None)
self.head.next = self.tail
self.tail.prev = self.head
self.size = size
self._map = dict()
def move_to_tail(self, node):
node.next = self.tail
node.prev = self.tail.prev
self.tail.prev.next = node
self.tail.prev = node
def _delete(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def get(self, key):
node = self._map.get(key, None)
if node:
self._delete(node)
self.move_to_tail(node)
return node.value
def set(self, key, value):
node = self._map.get(key, None)
if node:
node.value = value
self._delete(node)
self.move_to_tail(node)
return
if self.size == len(self._map):
node = self.head.next
self.head.next = self.head.next.next
self.head.next.prev = self.head
self._map.pop(node.key)
node = Node(key, value)
self.move_to_tail(node)
self._map[key] = node
def __setitem__(self, key, value):
self.set(key, value)
def __getitem__(self, key):
return self.get(key)
def __contains__(self, key):
return key in self._map
我们使用装饰器来使用LRUCache。
import functools
def lru_cache(maxsize=100):
_cache = LRUCache(maxsize)
def cache(func):
@functools.wraps(func)
def wrapper(key):
if key in _cache:
return _cache[key]
value = func(key)
_cache[key] = value
return value
return wrapper
return cache
我们拿它来计算斐波那契数列,哈哈哈(只是用于测试,应该没有人拿LRU算法来计算递归版本的斐波那契数列实现吧??~)
递归版本实现
def fib(n):
if n < 0:
raise ValueError("n must be zero or positive")
if n in (0, 1):
return 1
return fib(n-1) + fib(n-2)
@lru_cache(maxsize=1000)
def fib_with_lru(n):
if n < 0:
raise ValueError("n must be zero or positive")
if n in (0, 1):
return 1
return fib(n-1) + fib(n-2)
import time
def main():
start = time.time()
fib(30)
end = time.time()
print(fib.__name__, 'elapsed time is {}'.format(end-start))
start = time.time()
fib_with_lru(30)
end = time.time()
print(fib_with_lru.__name__, 'elapsed time is {}'.format(end-start))
if __name__ == '__main__':
main()
fib elapsed time is 0.6846170425415039
fib_with_lru elapsed time is 0.0010001659393310547
快近700倍!
使用collections.OrderedDict
实现
OrderedDict
是有序字典。
from collections import OrderedDict
class LRUCache:
def __init__(self, size=100):
self._size = size
self._od = OrderedDict()
def move_to_tail(self, key):
self._od.move_to_end(key, last=True)
def get(self, key):
value = self._od.get(key, None)
if value is not None:
self.move_to_tail(key)
return value
def set(self, key, value):
temp = self._od.get(key, None)
if temp is not None:
self._od[key] = value
self.move_to_tail(key)
return
if self._size == len(self._od):
self._od.popitem(last=False) # delete the oldest item
self._od[key] = value
self.move_to_tail(key)
OrderedDict
中的move_to_end
可以通过移动键的序列到尾部来管理键的新旧。
但这种实现有性能问题,这里只做演示。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK