caching - LRU和LFU有什么区别

Question

LRU和LFU缓存实现有什么区别？

我知道 LRU 可以使用LinkedHashMap. 但是如何实现 LFU 缓存呢？

Answer 1

让我们考虑一个缓存容量为 3 的恒定缓存请求流，如下所示：

A, B, C, A, A, A, A, A, A, A, A, A, A, A, B, C, D

如果我们只考虑一个最近最少使用 (LRU)的缓存，它具有 HashMap + 双向链表实现，具有 O(1) 驱逐时间和 O(1) 加载时间，我们将在处理上述缓存请求时缓存以下元素.

[A]
[A, B]
[A, B, C]
[B, C, A] <- a stream of As keeps A at the head of the list.
[C, A, B]
[A, B, C]
[B, C, D] <- here, we evict A, we can do better! 

当你看这个例子时，你可以很容易地看到我们可以做得更好——考虑到未来请求 A 的预期机会更高，即使它最近最少使用，我们也不应该驱逐它。

A - 12
B - 2
C - 2
D - 1

最不常用 (LFU)缓存通过跟踪缓存请求在其驱逐算法中使用的次数来利用此信息。

Answer 2

LRU 是一种缓存驱逐算法，称为最近最少使用缓存。

看看这个资源

LFU 是一种缓存驱逐算法，称为最不常用缓存。

它需要三个数据结构。一个是用于缓存键/值的哈希表，以便给定一个键，我们可以在 O(1) 检索缓存条目。第二个是每个访问频率的双链表。最大频率以缓存大小为上限，以避免创建越来越多的频率列表条目。如果我们有一个最大大小为 4 的缓存，那么我们最终会得到 4 个不同的频率。每个频率都有一个双链表来跟踪属于该特定频率的缓存条目。第三种数据结构是以某种方式链接这些频率列表。它可以是一个数组或另一个链表，因此在访问缓存条目时，它可以在 O(1) 时间内轻松提升到下一个频率列表。

Answer 3

主要区别在于，在 LRU 中，我们只检查哪个页面最近使用的时间比其他页面旧，即只检查最近使用的页面。但是在 LFU 中，我们检查旧页面以及该页面的频率，如果页面的频率大于旧页面，我们无法删除它，如果我们所有旧页面的频率相同，则采用最后一个，即 FIFO 方法. 并删除页面....

Answer 4

• 恒定时间插入仅适用于 LRU。我们至少可以使用 LFU 保持恒定时间查找，总比没有好。

• 在 LFU 中，根据动态变化的优先级来保持条目顺序的最佳方式当然是优先级队列。它可能是堆、斐波那契堆或任何其他实现，用户可以根据考虑哪种实现最适合他们的任务来选择实现，这取决于他们使用的编程语言，当然还有上下文他们将使用缓存。

• 从 LRU 切换到 LFU，我们的缓存实现只有两点需要改变：

  1- 驱逐政策（所有关于选择要删除的元素的逻辑）

  2- 用于存储元素的数据结构

• 为了创建 LFU 缓存，我们使用 hashmap 和 treap。treap 是二叉树和优先队列的结合。treap 中的想法，你有两个约束，你用二叉树构造一个，另一个用优先级队列。看看这张图：

hashmap 的值指向treap 节点。在陷阱节点中，蓝色小矩形中的数字是访问次数，这是陷阱的优先队列部分。请注意，子节点的优先级总是高于其父节点，但兄弟节点之间没有排序。

• 如果 LFU 缓存运行时间很长，那么不再流行的旧条目的周转时间可能会很长。

这是性能比较：