淘汰算法

将计算机简单看作一个「计算+存储」的工具，那么 CPU 的主要作用就是「计算」，硬盘的主要作用就是「存储」。

计算需要从硬盘里将数据搬运到 CPU 中，但是硬盘的速度是在太慢，从而有了折中的「内存」。即能存储一定的数据，又比硬盘速度更快些，虽然对于 CPU 而言还是太慢了。

计算机将部分数据从硬盘搬到内存中，在 CPU 需要时可以快速给到 CPU，从而提高 CPU 使用率。

但是内存是有限的，她被发明的本意就是为了加快访问。计算机不可能同时将全部的程序都放在内存中，但是我们又需要同时运行许多程序，于是操作系统就站出来负责这些工作。

一台计算机只有 4G 的内存，但是却可以运行 8G 的程序，其原因是由于程序的局部性原理，我们不需要同时运行 8G 的程序。

我们可以将程序中目前需要的部分先加载到内存中，随着程序的运行访问到某个子程序不在内存中，这个时候再去硬盘中加载到内存，这称为「内存页面置换」，也就是操作系统的内存管理的内容之一。

站在操作系统的视角，现在 A 程序运行的时候需要有个子程序 A’ ，但不在内存中，毫无疑问需要去硬盘中加载。但是加载之前有个问题需要考虑：目前内存是否有足够空间容纳子程序 A’？

如果空间足够，那么加载进来就完事儿，如果不够怎么办？答案就是把一部分数据抱回硬盘，再把需要的子程序 A’ 抱进来内存中。

那么，把哪部分数据抱回去？也就是个淘汰谁的问题。于是诞生出许多的淘汰算法。这就是淘汰算法的由来。

!!! summary 由于资源的稀缺，我们建立一个兼顾速度和容量的中间件——内存。但是内存容量依然有限，而我们又有多程序同时运行的需求，所以操作系统站出来负责内存管理。

在进行内存管理的时候，需要将旧数据换下去，把新数据换上来，所以有了把谁换下去的问题，于是有了淘汰算法。

解决方案

淘汰算法不仅仅适用于操作系统的内存管理，同样适用其他空间不足时需要替换数据的场景中。

常见的淘汰算法有：

OPT (Optimum 最佳淘汰算法) (理想化，未来没准能实现)
FIFO (First In First Out 先进先出算法) (绝对公平，但不实用)
LRU (Least Recently Used 最近最少使用算法) (容易把热点数据淘汰掉)
LFU (Least Frequently Used 最近最不常使用算法) (实现比较复杂)
ARC (Adaptive Replacement Cache 自适应缓存替换算法) (结合了 LRU 和 LFU)

首先我们准备一个空队列，然后准备一组编号代表第几号页被访问的顺序：701203042303212

每当访问一个页面的时候，我们就将其编号入队，通过观察其位置来区别不同算法的差异。

LRU

LRU 不仅记录了编号，还记录了其上次被访问至当前的时长。但是我们可以通过每次访问都将该编号放到队头，这样队尾自然演化成上次访问时间最长的那些。

7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	备注
7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	队头
	7	0	1	2	0	3	0	4	2	3	0	3	2	1
		7	0	1	2	2	3	0	4	2	2	0	3	3	队尾

前面三列可以看出，队列未满的时候， 7、0、1 依次入队，此时队头至队尾顺序为 107；

接着 2 入队，这时候 7 是距离入队时间(上次访问时间)最久的，所以被淘汰，于是队列成了 210；

然后 0 再次入队，因为 0 已经在队列中，所以把 0 调整到队头即可，此时队列成了 021；

然后 3 入队，此时 1 是距离入队时间最久的，所以被淘汰，于是队列成了 302，后面的情况也是如此。

这就是朴素的 LRU 算法，之所以实现简单就在于，虽然她带着一个「上次访问时间」的维度，但是这个维度可以通过将编号调整至队头，慢慢的队尾就是最久的一个。

那么实现起来只需要一个链队即可搞定。访问的编号在队中，只需要执行链表结点删除、插入队头两个操作即可；访问的编号不在队中，那么将队尾结点删除，插入队头两个操作即可。由于是链表，所以插入删除的时间复杂度仅为 O(1)。

但是要插入删除之前得先找到该结点，这样就得去遍历链表，时间复杂度是 O(n)，这个问题也简单，只需要增加一个哈希表，在插入和删除的时候维护这个哈希表即可。

??? example

```go
package main

type Node struct {
    Pre, Next *Node
    key       int
    Data      any
}

type LRUCache struct {
    length   int
    capacity int
    H        map[int]*Node
    Head     *Node
    Tail     *Node
}

func NewLRU(capacity int) *LRUCache {
    return &LRUCache{
        H:        make(map[int]*Node, capacity),
        capacity: capacity,
    }
}

func (l *LRUCache) Get(idx int) *Node {
    node := l.H[idx]
    if node == nil {
        return nil
    }
    l.moveToHead(idx)
    return node
}

func (l *LRUCache) moveToHead(idx int) {
    node := l.H[idx]
    node.Next.Pre = node.Pre
    node.Pre.Next = node.Next
    first := l.Head
    first.Pre = node
    node.Next = first
    l.Head = node
}

func (l *LRUCache) eliminate() {
    if l.length < l.capacity {
        return
    }
    last := l.Tail
    if last == nil {
        return
    }
    // 清理map
    delete(l.H, last.key)
    // 断链
    l.Tail = last.Pre
    last.Pre.Next = nil
    last = nil
    // 长度减1
    l.length--
}

func (l *LRUCache) Put(idx int, data any) {
    node := &Node{
        key:  idx,
        Data: data,
    }
    // 数据存在，就放到队头，不存在，就淘汰一个再放队头
    if _, ok := l.H[idx]; ok {
        l.moveToHead(idx)
    }
    // 淘汰数据
    l.eliminate()
    l.put(node)
}

func (l *LRUCache) put(node *Node) {
    if l.Head == nil {
        l.Head = node
        l.Tail = node
        l.length++
        return
    }
    first := l.Head
    first.Pre = node
    node.Next = first
    l.Head = node
    l.H[node.key] = node
    l.length++
}
```

优点热点数据命中率高。
缺点

朴素的 LRU 可能会导致热点数据被淘汰下去。例如，765432176576543243218，除了 1，其他都是反复被访问的页面，然后 1 就一直排在队尾，队列长这样 2345671。

然后访问了一下 1，变成 1234567，再访问下 8，这时候直接把 7 淘汰掉了，变成 8123456。而我们知道 7 的访问次数是比 1 高的。

这样就造成 7 这个热点数据被淘汰，而 1 这个冷数据却留下来了。

还有一种情况就是，当 1234567 的访问次数都很高，也就是他们都是热点数据，这时候 LRU 将失去优点。

LFU

LRU 记录了「上次访问时间」的维度，而 LFU 这是记录了「访问频率」的维度。

淘汰算法#

解决方案#

LRU#

LFU#

淘汰算法

解决方案

LRU

LFU