LRU Cache 的LRU是指Least Recently Used--最少使用的。
一个字典的读取效率是O（1），把字典当做你的缓存，从字典里调取值是比你用IO去重新读要快很多的，但是缓存是一种有限资源，也就是你的字典不能无限大，这样的话假如我们规定你的字典里最多只能存三组数据，当你要插入一个新的数据时，请删掉最不常用的那个数据。
也就是说，我们每次从字典里读数据，都要把读的这组数据放到队伍的顶端，这样当我们需要插入新数据的时候，末端的那组数据就是最不常用的，删掉末端，再在顶端插入新数据即可。
Python collections库有一个OrderedDict类，派生于基础的字典数据类型，但是key是有序的，你可以通过下标读数据而不是必须使用key。
自带一个move_to_end(key, last=True)方法可以把当前数据转移顶端或末端。
用下标获取数据：
d1= OrderedDict()
...
list(d1.items())[4]
#Python3 中 odict.items(), .values(), .keys()返回的odict_items对象不能直接调下标，需要先转换为list
>>>('3', 'some thing')
实现大小为3的LRU Cache
import collections
class SimpleLRUCache:
def __init__(self, size):
self.size = size
self.lru_cache = collections.OrderedDict()
def get(self, key):
value = self.lru_cache[key]
self.lru_cache.move_to_end(key)
return value
def put(self, key, value):
if len(self.lru_cache)>=self.size:
self.lru_cache.popitem(0)
self.lru_cache[key] = value
def show_entries(self):
print(self.lru_cache)
# Create an LRU Cache with a size of 3
cache = SimpleLRUCache(3)
cache.put("1","1")
cache.put("2","2")
cache.put("3","3")
cache.show_entries() # shows 1,3,4~
cache.get("1")
cache.show_entries()
cache.get("3")
cache.show_entries()
cache.put("4","4") # This will replace 2
cache.show_entries() # shows 1,3,4
cache.put("5","5") # This will replace 1
cache.show_entries() # shows 3,4,5
输出结果
OrderedDict([('1', '1'), ('2', '2'), ('3', '3')])
OrderedDict([('2', '2'), ('3', '3'), ('1', '1')])
OrderedDict([('2', '2'), ('1', '1'), ('3', '3')])
OrderedDict([('1', '1'), ('3', '3'), ('4', '4')])
OrderedDict([('3', '3'), ('4', '4'), ('5', '5')])
