目录：

1.1 python模拟LRU（Least recently used，最近最少使用）

　　  定义：算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

　　  核心：

　　　　　　1. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；

　　　　　　2. 当链表满的时候，将链表尾部的数据丢弃。

　　1、实现原理

　　　　1）使用三个数据标识这个缓存系统　　　　　　

　　　　　　　　self.cache = {}                   # cache模拟所有缓存系统中数据 key: val

　　　　　　　　self.keys = []                     # keys只存放cache字典中的 key 

　　　　　　　　self.size = size                  # size 来定义这个缓存系统最大容量

　　　　2）模拟数据加入缓存（set）

　　　　　　　　1. 如果缓存为达到最大长度，新数据key插入到 keys列表头部，将key:val存入字典

　　　　　　　　2. 如果达到最大长度，先删除最后列表keys最后一个元素，将这个key:val 从cache字典中删除

　　　　3）模拟获取缓存数据（get）

　　　　　　　　1. 判断获取的key是否在 cache字典中，如果在就从列表keys中先删除原有key,然后将key插入到列表最前面，并返回val

　　　　　　　　2. 如果key不在cache字典中，直接返回None即可

#!/usr/bin/env python# -*- coding:utf-8 -*-class LRUcache:    def __init__(self, size=3):        self.cache = {}        self.keys = []        self.size = size    def get(self, key):        if key in self.cache:            self.keys.remove(key)            self.keys.insert(0, key)            return self.cache[key]        else:            return None    def set(self, key, value):        if key in self.cache:            self.keys.remove(key)            self.keys.insert(0, key)            self.cache[key] = value        elif len(self.keys) == self.size:            old = self.keys.pop()            self.cache.pop(old)            self.keys.insert(0, key)            self.cache[key] = value        else:            self.keys.insert(0, key)            self.cache[key] = valueif __name__ == '__main__':    test = LRUcache()    test.set('a', 1)    test.set('b', 2)    test.set('c', 3)    test.set('d', 4)    print test.keys  # ['d', 'c', 'b']    print test.cache  # {'c': 3, 'b': 2, 'd': 4}    print(test.get('a'))  # None   当d=4加入缓存是，缓存到达上线3，所以把a从缓存中移除了    print(test.get('b'))  # 2    print(test.get('c'))  # 3    print(test.get('d'))  # 4

 

 

 

 

 

 

 

 

 

1111111111111111