LRU算法
洪笳淏 Lv4
 2021-09-21 22:25:07      

LRU算法介绍

  LRU算法(Least Recently Used)算法实质上是一种缓存机制，常用于操作系统的缓存。计算机的缓存容量是有限的，如果缓存满了就要给新的内容腾位置。那淘汰哪些缓存，哪些继续以何种方式留在缓存中就是一个策略性的问题。LRU算法就是其中一种淘汰策略。其内核就是认为最近使用过的数据是最有用的，很久都没使用的数据是无用的，内存满了就应该优先淘汰很久没用过的数据。

  举一个实际例子，安卓手机都可以把软件放到后台运行，比如我先后打开了「设置」「手机管家」「日历」，那么现在他们在后台排列的顺序是这样的：

avatar

  但是这时候如果我访问了一下「设置」界面，那么「设置」就会被提前到第一个，变成这样：

avatar

  假设我的手机只允许我同时开 3 个应用程序，现在已经满了。那么如果我新开了一个应用「时钟」，就必须关闭一个应用为「时钟」腾出一个位置，关那个呢？按照 LRU 的策略，就关最底下的「手机管家」，因为那是最久未使用的，然后把新开的应用放到最上面：

avatar

LRU算法的函数签名

  函数签名可以参考146. LRU 缓存机制的题目要求：

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。

实现 LRUCache 类：

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105 次 get 和 put

LRU算法设计

  分析上面的操作过程，要让 put 和 get 方法的时间复杂度为 O(1)，我们可以总结出 cache 这个数据结构必要的条件：

  1. 显然 cache 中的元素必须有顺序，以区分最近使用的和久未使用的数据，当容量满了之后要删除最久未使用的那个元素腾位置。
  2. 我们要在 cache 中快速找某个 key 是否已存在并得到对应的 val；
  3. 每次访问 cache 中的某个 key，需要将这个元素变为最近使用的，也就是说 cache 要支持在任意位置快速插入和删除元素。

  那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表 LinkedHashMap。LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样：

avatar

  借助这个结构，我们来逐一分析上面的 3 个条件：

  1. 如果我们每次默认从链表尾部添加元素，那么显然越靠尾部的元素就是最近使用的，越靠头部的元素就是最久未使用的。
  2. 对于某一个 key，我们可以通过哈希表快速定位到链表中的节点，从而取得对应 val。
  3. 链表显然是支持在任意位置快速插入和删除的，改改指针就行。只不过传统的链表无法按照索引快速访问某一个位置的元素，而这里借助哈希表，可以通过 key 快速映射到任意一个链表节点，然后进行插入和删除。

  这里先引出两个问题：为什么要是双向链表，单链表行不行？另外，既然哈希表中已经存了 **key**，为什么链表中还要存 key 和 val 呢，只存 val 不就行了？

代码实现

双链表的实现

  首先实现连表的每个节点：

1
2
3
4
5
6
type node struct {
    key			int
    value		int
    prev		*node
    next		*node
}

  然后依靠着这些节点实现一个双链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
type DoubleList struct {
    head		*node		// 头部虚节点
    tail		*node		// 尾部虚节点
    size		int			// 连表节点数
}

func constructDL() *DoubleList {	// 初始化双链表
    dh := &node{
        key : 0,
        value : 0,
    }
    dt := &node{
        key : 0,
        value : 0,
    }
    dh.next,dt.prev = dt,dh // 收尾虚节点形成双链表
    return &DoubleList{
        head : dh,
    	tail : dt,
    	size : 0,
    }
}

双链表的几个API的实现

  接下来我们实现操作双链表的几个API:

  1. addLast(x *node)：将最近使用的节点加入到双链表中（从尾部进入双链表）
  2. remove(x *node)：删除双链表中的节点x（节点x一定存在的条件下）
  3. removeFirst()：当容量满时，将最久未使用的节点（表首的节点）删除
  4. dlSize()：返回双链表的节点数

addLast(x *node)方法的实现细节

  在双链表的尾部虚节点之前插入节点，需要注意插入过程中prev和next指针的插入顺序。

1
2
3
4
5
6
7
func (dl *DoubleList) addLast(x *node) { // 在链表尾部添加节点 x，时间 O(1)
    x.prev = dl.tail.prev
    x.next = dl.tail
    dl.tail.prev.next = x
    dl.tail.prev = x
    dl.size++
}

remove(x *node)方法的实现细节

  删除连表中的某一节点，x存在时才能使用。

1
2
3
4
5
func (dl *DoubleList) remove(x *node) { // 由于是双链表且给的是目标 Node 节点，时间 O(1)
    x.prev.next = x.next
    x.next.prev = x.prev
    dl.size--
}

removeFirst()方法的实现细节

  缓存的空间占满，删除最久不使用节点（首部节点）。返回被删除的节点。

1
2
3
4
5
6
7
8
9
func (dl *DoubleList) removeFirst() *node { // 删除链表中第一个节点，并返回该节点，时间 O(1)
    if dl.head.next == dl.tail {
        return dl.head
    }
    
    first := dl.head.next
    dl.remove(first)
    return first
}

dlSize()返回链表长度

1
2
3
func (dl *DoubleList) dlSize() int { // 返回链表长度，时间 O(1)
    return dl.size
}

LRUCache类的实现

1
2
3
4
5
type LRUCache struct {
    hashMap		map[int]*node
    cache		*DoubleList
    cap			int
}

初始化：

1
2
3
4
5
6
7
8
9
func Constructor(capacity) LRUCache {
    m := make(map[int]*node,capacity)
    dl := constructDL()
    return LRUCache{
        hashMap	:	m,
        cache	:	dl,
        cap		:	capacity,
    }
}

抽象后的中间层

  为了避免直接对缓存进行操作时忘记同时对双链表和哈希表同时进行删除和插入操作，所以在具体的LRU的方法和数据结构之间添加一层作为抽象层（直接对数据结构进行操作）。

makeRecently(key int)将某个节点提升为最近使用

  当某个节点被使用后，变为最近使用节点，被放到链表尾部。

1
2
3
4
5
func (this *LRUCache) makeRecently(key int) {
    x := this.hashMap[key]
    this.cache.remove(x)	// 现在双链表删除该节点
    this.cache.addLast(x)	// 然后将该节点添加到双链表尾部
}

addRecently(key int, val)将某个新节点提升为最近使用

1
2
3
4
5
6
7
8
func (this *LRUCache) addRecently(key int, val int) {
    x := node{
        key	:	key,
        value	:	val,
    }
    this.cache.addLast(&x)
    this.hashMap[key] = &x
}

deleteKey(key int)删除某一个节点

1
2
3
4
5
func (this *LRUCache) deleteKey(key int) {
    x := this.hashMap[key]
    delete(this.hashMap,x)
    this.cache.remove(x)
}

deleteLeastRecently()删除最久未使用节点

1
2
3
4
5
func (this *LRUCache) deleteLeastRecently() {
    deleteNode := this.cache.removeFirst()
    deleteKey := deleteNode.key
    delete(this.hashMap,deleteKey)
}

LRUCache类的更新Get()和淘汰Put()方法

  Get(key int)方法：如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

1
2
3
4
5
6
7
func (this *LRUCache) Get(key int) int {
    if _,ok := this.hashMap[key]; !ok {
        return -1
    }
    this.makeRecently(key)	// 关键字存在于缓存中，将其置于双链表尾部位置
    return this.hashMap[key].value
}

  Put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

1
2
3
4
5
6
7
8
9
10
11
func (this *LRUCache) Put(key int, val int) {
    if _,ok := this.hashMap[key]; ok { // 如果存在与缓存中
        this.deleteKey(key)	// 先删除原来节点（避免出现更新value的情况）
        this.addRecently(key)	// 然后再将该节点重新插入
    } else {
        if this.cap == this.cache.dlSize { // 缓存容量已经达到上限
            this.deleteLeastRecently()	// 删除最不常使用节点
        }
        this.addRecntly(key,val)	// 然后将该新节点添加到缓存中
    }
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
type node struct {
    key     int
    value   int
    prev    *node
    next    *node
}

type DoubleList struct {
    head    *node
    tail    *node
    size    int
}


func constructDL() *DoubleList {
    dh := &node{
        key :   0,
        value : 0,
    }
    dt := &node{
        key :   0,
        value : 0,
    }
    dh.next,dt.prev = dt,dh

    return &DoubleList{
        head    :   dh,
        tail    :   dt,
        size    :   0,
    }
}

func (dl *DoubleList) addLast(x *node) {
    x.prev = dl.tail.prev
    x.next = dl.tail
    dl.tail.prev.next = x
    dl.tail.prev = x
    dl.size++
}

func (dl *DoubleList) remove(x *node) {
    x.prev.next = x.next
    x.next.prev = x.prev
    dl.size--
}

func (dl *DoubleList) removeFirst() *node {
    if dl.head.next == dl.tail {
        return dl.head
    }
    first := dl.head.next
    dl.remove(first)
    return first
}

func (dl *DoubleList) dlSize() int {
    return dl.size
}



type LRUCache struct {
    hashMap     map[int]*node
    cache       *DoubleList
    cap         int
}


func Constructor(capacity int) LRUCache {
    m := make(map[int]*node,capacity)
    dl := constructDL()

    return LRUCache{
        hashMap :   m,
        cache   :   dl,
        cap     :   capacity,
    }
}


func (this *LRUCache) Get(key int) int {
    if _,ok := this.hashMap[key]; !ok {
        return -1
    }
    this.makeRecently(key)
    return this.hashMap[key].value
}


func (this *LRUCache) Put(key int, value int)  {
    if _,ok := this.hashMap[key]; ok {
        this.deleteKey(key)
        this.addRecently(key,value)
    } else {
        if this.cap == this.cache.dlSize() {
            this.deleteLeastRecently()
        }
        this.addRecently(key,value)
    }
}

func (this *LRUCache) makeRecently(key int) {
    x := this.hashMap[key]
    this.cache.remove(x)
    this.cache.addLast(x)
}

func (this *LRUCache) addRecently(key int, val int) {
    x := &node{
        key :   key,
        value : val,
    }
    this.cache.addLast(x)
    this.hashMap[key] = x
}

func (this *LRUCache) deleteKey(key int) {
    x := this.hashMap[key]
    this.cache.remove(x)
    delete(this.hashMap,key)
}

func (this *LRUCache) deleteLeastRecently() {
    deleteNode := this.cache.removeFirst()
    deleteKey := deleteNode.key
    delete(this.hashMap, deleteKey)
}
  • Post title：LRU算法
  • Post author：洪笳淏
  • Create time：2021-09-21 22:25:07
  • Post link：https://jiahaohong1997.github.io/2021/09/21/LRU算法/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments