10分钟写出 Python LRU缓存代码

欢迎大家来到IT世界,在知识的湖畔探索吧!

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。怎样在面试中写出LRU缓存代码。我们先简单介绍一下LRU缓存。

计算机里的RAM就是一个缓存。操作系统把经常使用数据存在RAM，使用内存的地址作为key，数据本身作为value。

在高层次上，我们需要在LRU类中建立两个方法:

1. 取值 – get(key)
2. 放值 – put(key, value)

同时LRU还有一些要求：

1. 当缓存达到最大值，删除最远用过的键值
2. 任何取值或放值都会使得该值成为最近用过的键值
3. 取值和放值必须是O(1)时间复杂度
4. 当要取的值不存在，返回-1

根据以上要求，我们很自然地想到用哈希表来存放键值。但是如何实现LRU呢？我们需要双向链表的帮助。下面是LRU Cache的类代码，里面反映了LRU的主要功能：

class LRUCache:

    def __init__(self, capacity: int):
        self.size = capacity # 缓存的最大空间
        self.cache = {} # 存放键的哈希表
        self.dll = Dlinkedlist() #双向链表
        
    def get(self, key: int) -> int:
    		#如果key存在，返回value，同时把key放在链表最前面
      	if key in self.cache:
            self.dll.move_front(self.cache[key])
            return self.cache[key].val
				#如果key不存在，返回-1
        else:
            return -1

    def put(self, key: int, value: int) -> None:
    		#如果key存在，更新value
        if key in self.cache:
            self.cache[key].val = value
						self.dll.move_front(self.cache[key])
        else:
        	#如果key不存在，而且缓存满了，需要把最后一个key删除
            if len(self.cache) >= self.size:
                removed = self.dll.remove_tail()
                self.cache.pop(removed.key)
						#把新的key加到链表的前面
            self.cache[key] = Node(k=key, v=value)
            self.dll.unshift(self.cache[key])
        

欢迎大家来到IT世界,在知识的湖畔探索吧!

现在我们注意到，我们有几个双向链表的功能要实现：

1. 把节点移到最前面：move_front(node)
2. 删除最后一个节点：remove_tail(）
3. 把新的节点插到最前面： unshift(node)
4. 把一个节点从链表中孤立出来：isolate(node)

第三个功能其实是第一个的特殊情况。功能一和二都会用到功能四。所以总体而言我们只有两个基本函数isolate(node)和move_front(node)。

欢迎大家来到IT世界,在知识的湖畔探索吧!class Node:
    def __init__(self, k=None, v=None, prev=None, nxt=None ):
        self.key = k
        self.val = v
        self.prev = prev
        self.next = nxt

class Dlinkedlist:
    def __init__(self):
        self.root = Node()
        self.root.prev = self.root
        self.root.next = self.root
        self.capacity = 0
    
    def move_front(self, node):
        if node is None:
            return None
        elif node.prev is not None and node.next is not None:
        # Step 1: remove the node from its current position
            self.isolate(node)

        # Step 2: change the node so it points to the root and the old head node
        node.prev = self.root
        node.next = self.root.next
        
        # Step 3: Update the root node so it points to the new head        
        self.root.next.prev = node
        self.root.next = node
        return node
    
    def unshift(self, node):
        # add a node in the front of the DLL
        
        self.move_front(node)
        self.capacity += 1
        return node
    
    def remove_tail(self):
        # if the list is already empty, bail out
        if self.capacity == 0:
            return None
        removed = self.isolate(self.root.prev)
        self.capacity -= 1
        return removed    

    # isolate removes a node from its current position
    # it also sets its next and prev pointers to None to prevent memory leaks
    @staticmethod
    def isolate(node):
        node.next.prev = node.prev
        node.prev.next = node.next
        node.next = None
        node.prev = None
        return node
    

面试中先把LRU的要求写出来，根据要求写出主函数的伪代码。然后再列出双向链表的四个功能。征得面试官的同意，才开始写代码。对着大纲写，不会遗漏，写的也会比较顺畅。