LFU(Least Frequently Used)算法是一种经典的缓存淘汰策略算法,它的核心思想是淘汰最近最少使用的对象。在操作系统中,它可以用作进行页面置换算法。
算法题例 (LeetCode-460)实现 LFUCache
类:
LFUCache(int capacity)
- 用数据结构的容量 capacity
初始化对象
int get(int key)
- 如果键 key
存在于缓存中,则获取键的值,否则返回 -1
void put(int key, int value)
- 如果键 key
已存在,则变更其值;如果键不存在,请插入键值对。当缓存达到其容量 capacity
时,则应该在插入新项之前,移除最不经常使用的项。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,应该去除最近最久未使用的键
为了确定最不常使用的键,可以为缓存中的每个键维护一个使用计数器 。使用计数最小的键是最久未使用的键。当一个键首次插入到缓存中时,它的使用计数器被设置为 1
(由于 put
操作)。对缓存中的键执行 get
或 put
操作,使用计数器的值将会递增。函数 get
和 put
必须以 O(1)
的平均时间复杂度运行。
题解 首先LFU
算法要求我们在get
时要达到 O(1)
时间复杂度,那么首先想到的就是利用 HashMap
来进行储存。而且我们在进行get
时,相当于访问了这个元素,那么它的访问频率也需要更新。在进行put
时,在空间不足时要删除某个对象,要想达到O(1)
的时间复杂度那就必须构建一个 频率–>对象 的一个映射,这样一来就需要两个HashMap
来处理了。同时我们要注意的是,多个元素可能会有相同的频率值,因此 频率–>对象 映射中的 value
部分是若干个对象,那么我们可以采用双链表来将这些对象串起来,以方便我们进行增删。
在使用 Java
来编写算法时,可以使用 LinkedHashSet
集合来代替双链表进行处理,当然,为了更好地理解,首先还是自己编写一个双向链表来处理,代码如下:
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 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 public class LFUCache { private class Node { int key, value, freq; Node next, pre; public Node (int key, int value) { this .key = key; this .value = value; this .freq = 1 ; } } private class NodeList { Node head, tail; int size; public NodeList () { head = new Node (0 , 0 ); tail = new Node (0 , 0 ); head.next = tail; tail.pre = head; size = 0 ; } public void removeFirst () { Node delNode = head.next; if (delNode == tail) { throw new IllegalStateException ("the NodeList is empty." ); } removeNode(delNode); } public void addLast (Node node) { Node pre = tail.pre; pre.next = node; node.pre = pre; tail.pre = node; node.next = tail; size++; } public void removeNode (Node node) { Node pre = node.pre; Node next = node.next; pre.next = next; next.pre = pre; size--; node.pre = null ; node.next = null ; } } Map<Integer, Node> nodeMap; Map<Integer, NodeList> freqMap; int capacity; int minFreq; int currSize; public LFUCache (int capacity) { nodeMap = new HashMap <>(capacity); freqMap = new HashMap <>(); freqMap.put(1 , new NodeList ()); this .capacity = capacity; currSize = 0 ; minFreq = 1 ; } public int get (int key) { Node node = nodeMap.get(key); if (node == null ) return -1 ; freqInc(node); return node.value; } public void put (int key, int value) { if (capacity == 0 ) return ; Node node = nodeMap.get(key); if (node == null ) { if (capacity == currSize) { removeLeastFreqNode(); currSize--; } currSize++; node = new Node (key, value); freqMap.get(1 ).addLast(node); nodeMap.put(key, node); if (minFreq > 1 ) minFreq = 1 ; return ; } node.value = value; freqInc(node); } private void freqInc (Node node) { int freq = node.freq; node.freq++; NodeList oldList = freqMap.get(freq); oldList.removeNode(node); if (oldList.size == 0 && minFreq == freq) { minFreq = freq + 1 ; } freqMap.putIfAbsent(freq + 1 , new NodeList ()); NodeList newList = freqMap.get(freq + 1 ); newList.addLast(node); } private void removeLeastFreqNode () { NodeList list = freqMap.get(minFreq); Node delNode = list.head.next; nodeMap.remove(delNode.key); list.removeFirst(); } }