lru算法-DPDK中文网

LRU（Least Recently Used，最近最少使用）算法是一种常用的缓存替换策略，用于管理缓存中的数据。其基本思想是：如果一个数据在最近被访问过，那么将来被访问的可能性也更高；反之，如果一个数据在很久以前被访问过而现在没有使用，说明它不太可能再被使用，因此可以将其淘汰。

LRU 算法的基本步骤

初始化：
- 创建一个固定大小的缓存。
- 使用哈希表（或字典）快速查找缓存中的数据。
- 使用双向链表维护数据的使用顺序。
获取操作 (get(key))：
- 如果该键存在于缓存中：
  - 将对应节点移动到双向链表头部，表示它是最近使用的数据。
  - 返回该节点的值。
- 如果该键不存在，返回-1或其他指示未找到的数据。
插入/更新操作 (put(key, value))：
- 如果该键已经存在：
  - 更新其值，并将对应节点移动到双向链表头部。
- 如果该键不存在且缓存未满：
  - 在链表头部插入新节点，同时在哈希表中记录其位置。
- 如果缓存已满：
  - 淘汰双向链表尾部的数据（即最久未使用的数据），并从哈希表中删除对应项。
  - 将新节点插入到头部，同时更新哈希表。

示例代码

以下是Python实现LRU算法的示例：

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


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity  # 缓存容量
        self.cache = {}  # 哈希表，用于O(1)访问
        # 双向链表头尾哨兵节点
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: Node):
        """移除指定节点"""
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node
        
    def _add_to_head(self, node: Node):
        """将节点添加到双向链表的头部"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
        
    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            # 移动到头部并返回值
            self._remove(node)
            self._add_to_head(node)
            return node.value
        
        return -1

    def put(self, key: int, value: int) -> None:
        
         if key in this.cache:
             # 更新现有节点并移动到头部 
             existing_node= this.cache[key] 
             existing_node.value=value 
             # Move the updated node to head of the list 
             this._remove(existing_node) 
             this._add_to_head(existing_node)
         else:
              newNode=Node(key,value)
              if len(this.cache)==this.capacity:
                   tail=this.tail.prev 
                   this._remove(tail) 
                   del this.cache[tail.key]
               
               this._add_to_head(newNode)
               this.cache[key]=newNode 

# 示例用法：
lru_cache = LRUCache(2)  # 初始化容量为2

lru_cache.put(1, 1)      # 缓存为 {1=1}
lru_cache.put(2, 2)      # 缓存为 {1=1, 2=2}
print(lru_cache.get(1))  # 返回 1，并将 1 移动到最近使用位置，缓存为 {2=2, 1=1}
lru_cache.put(3, 3)      # 淘汰关键字 2，缓存为 {1=1, 3=3}
print(lru_cache.get(2))  # 返回-1 (未找到)
lru_cache.put(4, 4)      # 淘汰关键字 1，缓存为 {3=3, 4=4}
print(lru_cache.get(1))  # 返回-1 (未找到)
print(lru_cache.get(3))  # 返回3，并将其移动到最近使用位置，缓存为 {4=4 ,3=3 }
print(lru_cache.get(4))  # 返回4，并将其移动到最近使用位置，缓存为 {3=3 ,4=4 }