因为最近在补数据结构,正好学到循环双端链表,所以就想到了面试中经典的题LRUcache算法
举一个典型的例子,拿斐波那契数列来说,f(n)=f(n-1)+f(n-2),如果用python来实现

def fib(n):
    if n <= 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

这段代码的时间复杂度为o(2^n),因为其中牵涉到大量的重复计算
如果我们需要对这段代码进行算法的优化,那么我们可以先这样做

利用字典和装饰器进行优化

def cache(func):
    data = {}
    def wrapper(n):
        if n in data:
            return data[n]
        else:
            res = func(n)
            data[n] = res
            return res

    return wrapper

调用装饰器

@cache
def fib(n):
    if n <= 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

我们这里写了一个装饰器,通过引入data这个字典,当我们发现传入的参数在我们的data字典中,则相当于hit cache直接返回字典中的结果,如果没有命中,则通过func()获取到结果,并存入我们的data字典之中,当然这种优化是针对空间没有限制的情况下,如果空间受到限制,这种优化算法会使data变得无限大,而不符合我们的预期

LRUcache

常见的优化算法有LRU和LFU,具体的这两个是怎么实现的,参照这里。这里我只写出LRU算法,因为在面试过程之中,非常容易问到这个点。
首先LRU总结的来说,首先我们得需要构造一个链表,可以看着图片来叙说

  • 我们的访问顺序是ABCB,但是假设我们的字典只能放入两个数据
  • 这样当我们的第三个数据重新进入时,就需要删除最早访问的数据,所以我们通过链表来记录访问的顺序问题
  • 这里的链表如果是用单链表,当我们需要remove头节点时,仍然需要从头遍历,是一个O(n)的时间复杂度,所以我们需要使用双链表

直接上代码!
首先我们构建一个节点类,其中有上一指向,下一指向,键值key以及value

class Node(object):
    def __init__(self, prev=None, next=None, key=None, value=None):
        self.prev, self.next, self.key, self.value = prev, next, key, value

接着我们来写我们的循环双端链表的类

class CircualDoublelinkedlist(object):
    def __init__(self):
        node = Node()
        node.prev, node.next = node, node
        self.rootnode = node

    def headnode(self):
        return self.rootnode.next

    def tailnode(self):
        return self.rootnode.prev

    def remove(self, node):
        if node is self.rootnode:
            return
        else:
            node.prev.next = node.next
            node.next.prev = node.prev

    def append(self, node):
        tailnode = self.tailnode()
        tailnode.next = node
        node.prev = tailnode
        node.next = self.rootnode
        self.rootnode.prev = node

其中只需要构造知道头尾节点的方法,以及remove和append的方法即可,接下来就可以写我们的LRUcache的类
处理逻辑流程图

class LRUCache(object):
    def __init__(self, maxsize=16):
        self.maxsize = maxsize
        self.cache = {} # 缓存字典
        self.access = CircualDoublelinkedlist() # 访问顺序链表
        self.isfull = len(self.cache) >= self.maxsize # 判断是否溢出

    def __call__(self, func):
        def wrapper(n):
            cachenode = self.cache.get(n)
            if cachenode is not None:  # hit cache
                self.access.remove(cachenode)
                self.access.append(cachenode)
                res = cachenode.value
                return res
            else:  # miss cache
                value = func(n)
                if not self.isfull:  # not full
                    tailnode = self.access.tailnode()
                    newnode = Node(tailnode, self.access.rootnode, n, value)
                    self.access.append(newnode)
                    self.cache[n] = newnode

                    self.isfull = len(self.cache) >= self.maxsize
                    return value
                else:  # full
                    headnode = self.access.headnode()
                    tailnode = self.access.tailnode()
                    self.access.remove(headnode)
                    del self.cache[headnode.key]
                    newnode = Node(tailnode, self.access.rootnode, n, value)
                    self.access.append(newnode)
                    self.cache[n] = newnode
                    self.isfull = len(self.cache) >= self.maxsize
                    return value
        return wrapper

最后给我们的fib函数加上装饰器,即可

@LRUCache()
def fib(n):
    if n <= 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)


for i in range(1, 35):
    print(fib(i))

不过好像我套用这个方法到leetcode上面的LRU cache的时候,如果是一组很大很大的数据,在del self.cache[headnode.key]
会报Line 64: KeyError: 9错误。感觉我现阶段解决不了啊,可能是代码在大量摄入数据的时候有bug?

版权声明:本文为原创文章,版权归 heroyf 所有。
本文链接: https://heroyf.club/2019/04/lru_cache/


“苹果是给那些为了爱选择死亡的人的奖励”