python实现LRU

LRU简述

Least Recently Used，最近最少使用。LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。
反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是著名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，
找到最近最久未使用的那个页面调出内存。这就是LRU算法的全部内容。
set时注意事项：由于存在内存中的页面个数是有限的，所以当我们把内存中不存在的页面用set把它从外存存到内存的时候，我们要首先查看，内存个数是否已满。此外，当我们要修改已存在页面的时候，我们还要把他重新放置到最右端，因为他很有可能马上会被再次访问。
get时注意事项：如果试图读取不存在的页面会报错。成功读取页面后，还要把读取的页面放置最右端。

用collections.OrderedDict实现LRU

OrderedDict是一个以放入字典的先后顺序为序的有序的dict，我们也通过它的这一特性来区分最久和最新的键值对（刚刚访问的键值对都在最右侧，最少访问的键值对都在最左侧）。
它的内置方法popitem(last=), last=True时，表示pop出最右端的键值对(栈FILO)，last=False时，表示pop出最左端的键值对(队列FIFO)

# 使用OrderedDict, 一个按照放入先后排序的dict, 位于OrderedDict末尾的元素表示最有可能被再次访问
import collections


class LRUCache:
    # size缓存大小
    def __init__(self, size):
        self._size = size
        self._cache = collections.OrderedDict()

    def __setitem__(self, key, value):
        if key in self._cache:
            self._cache.pop(key)
        elif self._size == len(self._cache):  # 如果内存已满，就要删除最久的键值对
            self._cache.popitem(last=False)   # last=True,表示弹出末尾的键值对类似栈的LIFO，last=False，弹出最左端的键值对类似队列FIFO，符合LRU，最前面的表示最久没使用
        self._cache[key] = value  # set的数据就是现在访问的，也是最有可能被再次的访问的元素，通过set放在最右端

    def __getitem__(self, key):
        val = self._cache.pop(key)  # 如果key不存在会报keyerror
        self._cache[key] = val  # 因为被get访问过，key被重新放置到了最右端
        return val

使用双端链表+dict实现LRU

思路是基于OrderedDict的源码，利用双向链表实现dict有序性。OrderedDict源码
虽然dict本身是无序的，但我们既需要它的O(1)的查找时间，其次由于涉及了首元素的删除，用数组明显没有链表有优势，所以我们选择链表。再者，由于要查找链表中的节点，我们就把每个节点以页面标码为key，节点对象为value存在一个dict里。
这样我们查找链表节点的时间为O(1),插入删除也为O(1)。又因为涉及到链表内部节点的插入删除，我们选择双向链表。

class LRUCache:
    '''
    self._map: {key: _Node(prev, nex, key)}  # 节点键值对, _Node双向节点类
    self._cache: {key:value}  # 真正的键值对
    self._head, self._tail: 头节点，尾节点
    '''

    class _Node:
        def __init__(self, prev=None, nex=None, value=None):
            self.prev = prev
            self.nex = nex
            self.value = value

        def __repr__(self):  # print()时被调用，测试时用，注意返回值一定是str类型
            return '({}, {}, {})'.format(self.prev.value, self.nex.value, self.value)

    def __init__(self, size):
        assert isinstance(size, int) and size > 0, 'size must be a positive integer'
        self.size = size
        self._map = {}     # {key:_Node(pre, nex, key)}
        self._cache = {}   # 正式的 cache dict
        self._head = self._Node()
        self._tail = self._Node()
        self._head.nex = self._tail
        self._tail.prev = self._head

    def __setitem__(self, key, value):
        if key in self._map:
            self._delete(key)
        if len(self._map) == self.size:
            last = self._tail.prev
            self._delete(last.value)
        self._cache[key] = value
        self._map[key] = self._Node(self._head, self._head.nex, key)
        self._head.nex.prev = self._map[key]
        self._head.nex = self._map[key]

    def _delete(self, key):
        self._map[key].prev.nex, self._map[key].nex.prev = self._map[key].nex, self._map[key].prev
        del self._map[key]
        del self._cache[key]

    def __getitem__(self, key):
        val = self._cache[key]
        self._delete(key)
        self[key] = val
        return val

    def __repr__(self):
        return repr(self._cache)


lru = LRUCache(5)
for i in range(8):
    lru[i] = i+1
print(lru._map)
print(lru[3]) # get之后lru[3]应该变成第一个节点
print(lru._map)