【算法与数据结构】LRU 算法

简介: LRU(Least Recently Used),这种算法认为最近使用的数据是热点数据,下一次有很大概率会再次使用这个数据。而最近很少被使用的数据,很大概率下一次不会使用。所以当缓存容量满时,优先淘汰掉最近最少使用的数据。

LRU 算法:

LRU 算法原理:

LRU(Least Recently Used),这种算法认为最近使用的数据是热点数据,下一次有很大概率会再次使用这个数据。而最近很少被使用的数据,很大概率下一次不会使用。所以当缓存容量满时,优先淘汰掉最近最少使用的数据。

LRU 算法相当于把数据按照时间排序,这个需求借助链表很自然就能实现,你一直从链表头部加入元素的话,越靠近头部的元素就是新的数据,越靠近尾部的元素就是旧的数据,我们进行缓存淘汰的时候只要简单地将尾部的元素淘汰掉就行了。

假设内存只能容纳3个页大小,按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间,在上面的,是最近访问的,在下面的是,最远时间访问的,LRU就是这样工作的。

总结一下LRU算法具体实现步骤:

  1. 新数据插入时,直接插入到列表的头部
  2. 缓存数据命中时,将命中的数据移动到列表头部
  3. 缓存满时,移除列表尾部的数据。

LRU 算法实现:

使用双向链表加散列表(HashMap)结构,就能很好的保证了查询效率在O(1)的时间复杂度。

整体的设计思路是,可以使用 HashMap 存储 key,这样可以做到 saveget的时间都是 O(1),而 HashMapValue 指向双向链表实现的 LRUNode 节点,如图所示。

下面展示了,预设大小是 3 的,LRU存储的在存储和访问过程中的变化。为了简化图复杂度,图中没有展示 HashMap部分的变化,仅仅演示了上图 LRU 双向链表的变化。我们对这个LRU缓存的操作序列如下:

save(“key1”, 7)
save(“key2”, 0)
save(“key3”, 1)
save(“key4”, 2)
get(“key2”)
save(“key5”, 3)
get(“key2”)
save(“key6”, 4)

相应的 LRU 双向链表部分变化如下:

总结一下核心操作的步骤:

  1. save(key, value):首先在 HashMap 找到 Key 对应的节点,如果节点存在,更新节点的值,并把这个节点移动队头。如果不存在,需要构造新的节点,并且尝试把节点塞到队头,如果LRU空间不足,则通过 tail 淘汰掉队尾的节点,同时在 HashMap 中移除 Key
  2. get(key):通过 HashMap 找到 LRU 链表节点,把节点插入到队头,返回缓存的值。

首先需要定义节点Node类:

class DLinkedNode {
    int key;
    int value;
    DLinkedNode pre;
    DLinkedNode post;
}

LRUCache内部为了一个索引Map,目的是为了putget时都能实现O(1)的时间复杂度:

private HashMap<Integer, DLinkedNode> cache = new HashMap<>();

内部维护了一个DLinkedNode双向链表,用于记录访问的时间先后:

// DLinkedNode个数:
private int count;
// 缓存容量:
private int capacity;
private DLinkedNode head;
private DLinkedNode tail;

两个核心的方法getput

完整代码实现:

public class LRUCache {
    private HashMap<Integer, DLinkedNode> cache = new HashMap<>();
    private int count;
    private int capacity;
    private DLinkedNode head;
    private DLinkedNode tail;
    public LRUCache(int capacity) {
        this.count = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        head.pre = null;
        tail = new DLinkedNode();
        tail.post = null;
        head.post = tail;
        tail.pre = head;
    }
    public int get(String key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1; // should raise exception here.
        }
        // move the accessed node to the head;
        this.moveToHead(node);
        return node.value;
    }
    public void set(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;
            this.cache.put(key, newNode);
            this.addNode(newNode);
            ++count;
            if (count > capacity) {
                // pop the tail
                DLinkedNode tail = this.popTail();
                this.cache.remove(tail.key);
                --count;
            }
        } else {
            // update the value.
            node.value = value;
            this.moveToHead(node);
        }
    }
    /**
     * Always add the new node right after head;
     */
    private void addNode(DLinkedNode node) {
        node.pre = head;
        node.post = head.post;
        head.post.pre = node;
        head.post = node;
    }
    /**
     * Remove an existing node from the linked list.
     */
    private void removeNode(DLinkedNode node) {
        DLinkedNode pre = node.pre;
        DLinkedNode post = node.post;
        pre.post = post;
        post.pre = pre;
    }
    /**
     * Move certain node in between to the head.
     */
    private void moveToHead(DLinkedNode node) {
        this.removeNode(node);
        this.addNode(node);
    }
    // pop the current tail.
    private DLinkedNode popTail() {
        DLinkedNode res = tail.pre;
        this.removeNode(res);
        return res;
    }
}



相关文章
|
9天前
|
机器学习/深度学习 存储 算法
【数据结构】算法的复杂度
算法的时间复杂度和空间复杂度
16 1
【数据结构】算法的复杂度
|
2天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
9 1
|
7天前
|
算法 安全 调度
逆天改命!Python高级数据结构堆(Heap)与优先队列,让你的算法效率飙升至宇宙级!
【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue实现了堆和优先队列,提供高效算法解决方案。堆用于Dijkstra算法求解最短路径,例如在图论问题中;PriorityQueue则在多线程下载管理中确保高优先级任务优先执行。这两个数据结构提升效率,简化代码,是编程中的强大工具。
10 0
|
8天前
|
算法 搜索推荐 Java
在Java中实现高效的算法与数据结构
在Java中实现高效的算法与数据结构
|
13天前
|
缓存 算法 前端开发
前端 JS 经典:LRU 缓存算法
前端 JS 经典:LRU 缓存算法
11 0
|
17天前
|
存储 算法 调度
算法与数据结构-栈篇
算法与数据结构-栈篇
14 0
|
18天前
|
人工智能 算法
程序技术好文:算法与数据结构
程序技术好文:算法与数据结构
|
19天前
|
算法 Java
Java数据结构与算法:最短路径算法
Java数据结构与算法:最短路径算法
|
2天前
|
算法 数据安全/隐私保护
基于GA遗传优化算法的Okumura-Hata信道参数估计算法matlab仿真
在MATLAB 2022a中应用遗传算法进行无线通信优化,无水印仿真展示了算法性能。遗传算法源于Holland的理论,用于全局优化,常见于参数估计,如Okumura-Hata模型的传播损耗参数。该模型适用于150 MHz至1500 MHz的频段。算法流程包括选择、交叉、变异等步骤。MATLAB代码执行迭代,计算目标值,更新种群,并计算均方根误差(RMSE)以评估拟合质量。最终结果比较了优化前后的RMSE并显示了SNR估计值。
16 7
|
4天前
|
算法 数据挖掘
MATLAB数据分析、从算法到实现
MATLAB数据分析、从算法到实现