cache的基本介绍

发表于

FIFO算法

FIFO 算法是一种比较容易实现的算法。它的思想是先进先出（FIFO，队列），这是最简单、最公平的一种思想，即如果一个数据是最先进入的，那么可以认为在将来它被访问的可能性很小。空间满的时候，最先进入的数据会被最早置换（淘汰）掉。

FIFO 算法的描述：设计一种缓存结构，该结构在构造时确定大小，假设大小为 K，并有两个功能：

set(key,value)：将记录(key,value)插入该结构。当缓存满时，将最先进入缓存的数据置换掉。
get(key)：返回key对应的value值。
实现：维护一个FIFO队列，按照时间顺序将各数据（已分配页面）链接起来组成队列，并将置换指针指向队列的队首。再进行置换时，只需把置换指针所指的数据（页面）顺次换出，并把新加入的数据插到队尾即可。

缺点：判断一个页面置换算法优劣的指标就是缺页率，而FIFO算法的一个显著的缺点是，在某些特定的时刻，缺页率反而会随着分配页面的增加而增加，这称为Belady现象。产生Belady现象现象的原因是，FIFO置换算法与进程访问内存的动态特征是不相容的，被置换的内存页面往往是被频繁访问的，或者没有给进程分配足够的页面，因此FIFO算法会使一些页面频繁地被替换和重新申请内存，从而导致缺页率增加。因此，现在不再使用FIFO算法。

LRU算法

LRU（The Least Recently Used，最近最久未使用算法）是一种常见的缓存算法，在很多分布式缓存系统（如Redis, Memcached）中都有广泛使用。

LRU算法的思想是：如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最久没有访问的数据最先被置换（淘汰）。

LRU算法的描述： 设计一种缓存结构，该结构在构造时确定大小，假设大小为 K，并有两个功能：

set(key,value)：将记录(key,value)插入该结构。当缓存满时，将最久未使用的数据置换掉。
get(key)：返回key对应的value值。
实现：最朴素的思想就是用数组+时间戳的方式，不过这样做效率较低。因此，我们可以用双向链表（LinkedList）+哈希表（HashMap）实现（链表用来表示位置，哈希表用来存储和查找）

LFU算法#

LFU（Least Frequently Used ，最近最少使用算法）也是一种常见的缓存算法。

顾名思义，LFU算法的思想是：如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰。

LFU 算法的描述：

设计一种缓存结构，该结构在构造时确定大小，假设大小为 K，并有两个功能：

set(key,value)：将记录(key,value)插入该结构。当缓存满时，将访问频率最低的数据置换掉。
get(key)：返回key对应的value值。
算法实现策略：考虑到 LFU 会淘汰访问频率最小的数据，我们需要一种合适的方法按大小顺序维护数据访问的频率。LFU 算法本质上可以看做是一个 top K 问题(K = 1)，即选出频率最小的元素，因此我们很容易想到可以用二项堆来选择频率最小的元素，这样的实现比较高效。最终实现策略为小顶堆+哈希表。

最小堆

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
1.将长度为n的待排序的数组进行堆有序化构造成一个大顶堆
 
2.将根节点与尾节点交换并输出此时的尾节点
 
3.将剩余的n -1个节点重新进行堆有序化
 
4.重复步骤2，步骤3直至构造成一个有序序列

class Max_Heap{
    typedef int index;
public:
    Max_Heap(vector<int> &vec) :v(vec){
        Build_Heapify();
    }
    ~Max_Heap(){};
    void Heap_Sort();
    int Heap_Max() { return v[0]; }
    int Heap_Extract_Max();
    void Insert(int key);
private:
    vector<int> &v;
    void Max_Heapify(index i, int hs);
    void Build_Heapify();
};

void
Max_Heap::Max_Heapify(index i, int hs){
    int l = 2 * i + 1, r = 2 * i + 2;
    int largest = i;
    if (l < hs&&v[l] > v[i])
        largest = l;
    if (r < hs&&v[r] > v[largest])
        largest = r;
    if (largest != i){
        swap(v[i], v[largest]);
        Max_Heapify(largest, hs);
    }
}

void
Max_Heap::Build_Heapify(){
    int hs = v.size();
    for (int i = (hs / 2) - 1; i >= 0; --i)
        Max_Heapify(i, hs);
}

void
Max_Heap::Heap_Sort(){
    int hs = v.size();
    Build_Heapify();
    for (int i = hs - 1; i >= 0; --i){
        swap(v[0], v[i]);
        Max_Heapify(0, i);
    }
}
int
Max_Heap::Heap_Extract_Max() {
    if (v.size() == 0)
    {
        std::cout << "over flow";
        return 0;
    }
    else {
        int temp = v[0];
        swap(v[0], v[v.size() - 1]);
        v.pop_back();
        Max_Heapify(0, v.size());
        return temp;
    }
}
void
Max_Heap::Insert(int key){
    v.push_back(key);
    int sz = v.size();
    while (sz >= 2 && key > v[sz / 2 - 1]){
        swap(v[sz - 1], v[sz / 2 - 1]);
        sz = sz / 2;
    }
}