LRU 缓存淘汰策略
LRU（Least Recent Used）缓存淘汰策略
LRU 算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
实现细节
核心思想使用 map 结构做到 save 和 get key的时间都是 O(1)，配合双向链表完成 O(1) 时间将节点放置在缓存头部。
编码细节：
- save(key, value)
- 首先在 Map 找到 Key 对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。
- 如果不存在，需要构造新的节点，并且尝试把节点塞到队头，如果LRU空间不足，则通过 tail 淘汰掉队尾的节点，同时在 Map 中移除 Key。
- get(key)
- 通过 Map 找到 LRU 链表节点，因为根据LRU 原理，这个节点是最新访问的，所以要把节点插入到队头，然后返回缓存的值。
Python 实现
#!/usr/bin/env python
# -*- coding: utf-8 -*-
class Node(object):
"""节点包含前后指针和键值"""
def __init__(self, key, value, pre=None, post=None):
self.key = key
self.value = value
self.pre = pre
self.post = post
def __repr__(self):
return 'Node({},{})'.format(self.key, self.value)
__str__ = __repr__
class LRUCache(object):
def __init__(self, capacity=10):
"""容量大小，初始化头尾节点"""
self.size = 0
self.capacity = capacity
self.head = Node(-1, -1)
self.tail = Node(-1, -1)
self.head.post = self.tail
self.tail.pre = self.head
self.key_map = dict()
def set(self, k, v):
node = self.key_map.get(k)
if node is not None:
self.key_map[k] = v
self._move_node(node)
else:
node = Node(k, v)
self._add_node(node)
self.key_map[k] = node
self.size += 1
if self.size >= self.capacity:
node = self._pop_node()
self.key_map.pop(node.key)
self.size -= 1
def get(self, k):
"""获取操作"""
node = self.key_map.get(k)
if node is not None:
self._move_node(node)
return node.value
else:
print('miss key')
return -1
# raise KeyError('key not exist')
def _add_node(self, node):
"""增加node至head后"""
node.pre = self.head
node.post = self.head.post
self.head.post.pre = node
self.head.post = node
def _remove_node(self, node):
"""删除node"""
node.pre.post = node.post
node.post.pre = node.pre
def _move_node(self, node):
"""移动至头部"""
self._remove_node(node)
self._add_node(node)
def _pop_node(self):
"""弹出尾节点"""
node = self.tail.pre
self._remove_node(node)
return node
def print_node(self):
node = self.head
while node.post != self.tail:
yield node.post
node = node.post
if __name__ == '__main__':
import random
cache = LRUCache()
for i in range(20):
k = random.randint(0, 5)
if k % 2 == 0:
cache.set(i, i)
print('set {}'.format(i))
else:
v = cache.get(k)
print('get {}, value {}'.format(k, v))
print('->'.join(str(i) for i in cache.print_node()))