Fantasy
0%

LRU和LFU

发表于
本文字数： 5.3k 阅读时长 ≈ 5 分钟

缓存淘汰算法

缓存是为了解决存储介质间读写速度相差过大而设置的一块大小有限的数据缓存区。经由缓存中转，可极大地提高数据的读写速度，从而提高系统性能。由于缓存大小有限，当存储的数据达到其大小限制时就需要淘汰掉其中一部分“价值最小”的数据，从而使其可以装入新的数据。这就是缓存淘汰算法的工作。缓存淘汰算法在计算机科学中应用十分广泛，从最底层的硬件到最上层的应用层都有着它的身影。例如缓和CPU和内存间速度差异的Cache，操作系统层的虚拟内存，应用层的缓存中间件等等。不同的评判数据价值的方式催生了不同的缓存淘汰算法，常见的有FIFO、LRU、LFU等。本文将结合两道题目分析LRU和LFU两种缓存淘汰算法。

LRU

简介

LRU的全称是Least Recently Used，即最近最少使用。该算法认为最近最少使用的数据块是“最没有价值的”，因此在每次缓存满时淘汰它。

举个例子，当缓存容量为3，数据序列为 2 1 2 1 2 3 4 时，被淘汰的数据是1。

Leetcode 146-LRU缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：

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

示例：

1
2
3
4
5
6
7
8
9
10
11
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

分析

利用双向链表+哈希表实现。维护一个由value节点链成的双向链表和一个从key到value节点的哈希表。

  • get

    首先检查哈希表，看key是否存在，若不存在直接返回-1。若存在，将当前value节点从链表中删除，再插入到链表头，最后返回value。

  • put

    首先直接调用get方法检查哈希表，看key是否已存在。若存在，经过get方法，value节点已经到达表头，只需要更新value的值即可。若不存在，则需要在链表中插入新节点。插入前需要先检查链表中的元素数是否已经等于capacity。若是，链表尾元素就是最近最少使用的元素，淘汰即可。之后再将新节点插入到链表头。最后将映射关系加入哈希表。

get和put的时间复杂度均为 。

代码如下：

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
class LRUCache {
    class Node {
        public int key;
        public int value;
        public Node pre;
        public Node next;

        public Node(int k, int v) {
            this.key = k;
            this.value = v;
        }
    }

    private int capacity;
    private Node head;
    private Node tail;
    private Map<Integer, Node> hash;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.hash = new HashMap<>();
    }
    
    public int get(int key) {
        if (capacity == 0)
            return -1;
        Node cur = hash.get(key);
        if (cur == null)
            return -1;
        Node pre = cur.pre, next = cur.next;
        if (pre != null) { // 说明cur不为head，将其放于head
            pre.next = next;
            if (next != null)
                next.pre = pre;
            else
                tail = pre;
            cur.next = head;
            head.pre = cur;
            cur.pre = null;
            head = cur;
        }
        return cur.value;
    }
    
    public void put(int key, int value) {
        if (capacity == 0)
            return;
        
        if (this.get(key) != -1) {
            hash.get(key).value = value;
            return;
        }

        Node cur = new Node(key, value);
        // 新节点都插入为head
        if (head == null)
            head = tail = cur;
        else {
            cur.next = head;
            head.pre = cur;
            head = cur;
        }

        if (hash.size() == capacity) { //若已达容量删除tail
            hash.remove(tail.key);
            tail = tail.pre;
            tail.next = null;
        }
        hash.put(key, cur);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

LFU

简介

LFU的全称是Least Frequently Used，即最不常使用。该算法在选择淘汰的数据块时以其使用次数为依据，使用次数最少的将被淘汰。

还是使用LRU的例子，缓存容量为3，数据序列为 2 1 2 1 2 3 4 ，LFU中被淘汰的数据是3。

Leetcode 460-LFU缓存

设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。

get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。

进阶：
你是否可以在 O(1) 时间复杂度内执行两项操作？

示例：

1
2
3
4
5
6
7
8
9
10
11
12
LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

分析

采用和LRU相似的思路，我们希望在淘汰操作时所有节点也可以按淘汰顺序形成一个列表，待淘汰的元素位于表头。LFU中根据使用频率来决定淘汰的节点，每次淘汰使用频率最少的那个。当多个节点频率值相同时，再采用LRU来淘汰节点。因此，最终我们需要的列表应该是这样的：使用频率从头到尾依次增大，使用频率相等时，使用时间戳从头到尾依次增大。这样一个序列我们可以通过一颗平衡二叉树实现，在Java中，使用TreeSet即可。此外，为了获取到value节点，仍然需要一个哈希表。

  • get

    首先检查哈希表，看key是否存在，若不存在直接返回-1。若存在，先将value节点从TreeSet中移除，更新其使用频率和时间戳，再将其重新插入TreeSet中，最后返回value。

  • put

    首先直接调用get方法检查哈希表，看key是否已存在。若存在，经过get方法，value节点已经到达树中的新位置，只需要更新value的值即可。若不存在，则需要在链表中插入新节点。插入前需要先检查TreeSet中的元素数是否已经等于capacity。若是，树中最左端的元素就是需要淘汰的元素。可调用pollFirst方法获取。之后再将新节点插入到TreeSet中。最后将映射关系加入哈希表。

由于get和put操作中都需要对平衡二叉树进行插入删除操作，因此二者的最终时间复杂度均为 。还可以使用双链表实现真正的 。（有机会再补

代码如下：

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
class LFUCache {
    class Node implements Comparable<Node> {
        public int key;
        public int value;
        public int freq;
        public int time;

        public Node(int k, int v, int t) {
            this.key = k;
            this.value = v;
            this.time = t;
            this.freq = 1;
        }

        public int compareTo(Node n) {
            if (this.freq < n.freq)
                return -1;
            else if (this.freq > n.freq)
                return 1;
            else if (this.time < n.time)
                return -1;
            else if (this.time > n.time)
                return 1;
            else
                return 0;
        }
    }

    private int capacity;
    private int time;
    private TreeSet<Node> tree;
    private Map<Integer, Node> hash;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.time = 0;
        this.tree = new TreeSet<>();
        this.hash = new HashMap<>();
    }
    
    public int get(int key) {
        if (capacity == 0)
            return -1;
        
        Node cur = hash.get(key);
        if (cur == null)
            return -1;
        tree.remove(cur);
        cur.freq++;
        cur.time = ++time;
        tree.add(cur);
        return cur.value;
    }
    
    public void put(int key, int value) {
        if (capacity == 0)
            return;

        if (this.get(key) != -1) {
            hash.get(key).value = value;
            return;
        }

        if (tree.size() == capacity) { //若已达容量删除TreeSet中首个元素
            Node drop = (Node) tree.pollFirst();
            hash.remove(drop.key);
        }
        Node cur = new Node(key, value, ++time);
        tree.add(cur);
        hash.put(key, cur);
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */