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可以通过移动键的序列到尾部来管理键的新旧。

但这种实现有性能问题，这里只做演示。