LRU和LFU有什么不同？

Question

LRU和LFU缓存实现的区别是什么？ 我知道可以使用LinkedHashMap实现LRU。但是如何实现LFU缓存？

- Javadroider

---

需要更多的解释... - Kundan

如果爬虫正在爬取您的网站并使大量“不流行的页面”最近被使用，那么LFU可能会很有用。在这种情况下，如果使用LRU算法，所有这些抓取的页面可能会导致被缓存的应该缓存的页面被逐出缓存。 - Rusty Rob

Answer 1

让我们考虑一个具有3个缓存容量的常量缓存请求流，如下所示：

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

如果我们只考虑使用HashMap和双向链表实现的最近最少使用（LRU）缓存，其驱逐时间为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）缓存通过在其驱逐算法中跟踪缓存请求已被使用的次数来利用此信息。

- Zorayr

---

非常清晰易懂的解释，谢谢！ - Khaerul Umam

Answer 2

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

参考文献

LFU是一种缓存淘汰算法，称为最不经常使用缓存。

它需要三个数据结构。第一个是哈希表，用于缓存key/value，这样可以在O(1)的时间复杂度内检索到cache entry。第二个是双重链接列表，用于每个访问频率。最大频率受到缓存大小的限制，以避免创建更多的频率列表项。如果我们有一个最大大小为4的缓存，则将得到4个不同的频率。每个频率都将有一个双重链接列表来跟踪属于该特定频率的缓存条目。 第三个数据结构是如何链接这些频率列表。它可以是数组或另一个链接列表，以便在访问缓存条目时可以很容易地在O(1)时间内将其升级到下一个频率列表。

- AllTooSir

Answer 3

主要区别在于，在LRU中，我们只检查最近使用的页面是否比其他页面旧，即仅基于最近使用的页面进行检查。 但是，在LFU中，我们不仅检查旧页面，还检查页面的频率。如果页面的频率大于旧页面，则不能删除它。如果所有旧页面的频率相同，则采用先进先出（FIFO）方法，删除页面...

- sachin rathod

Answer 4

“常数时间插入”仅适用于LRU，因为我们使用双向链表，插入基于时间。我们只需将元素添加到双向链表的尾部。在LFU中，我们可以保持常数时间查找，但是无法实现常数时间插入。因为插入取决于每个项已被使用的频率，每个元素都存储此信息，因此当我们添加新项时，必须根据此变量对元素进行排序。

在LFU中，根据动态更改的优先级保持条目顺序的最佳方法当然是优先队列。它可能是堆、斐波那契堆或任何其他实现。这里插入的顺序不重要，我们的优先级是每个元素已经被使用的频率，并且与每个节点相关联。

我们只需要更改两件事情就可以从LRU切换到LFU的缓存实现：1-驱逐策略2-用于存储元素的数据结构。

要创建LFU缓存，我们使用哈希映射和treap。treap是二叉树和优先队列的组合。在treap中，您有两个约束条件，一个使用二叉树结构，另一个使用优先队列。请看一下这张图：

哈希映射的值指向treap节点。在treap节点中，小蓝色矩形中的数字是“访问次数”，这是treap的优先队列部分。请注意，子节点始终具有比其父节点更高的优先级，但兄弟节点之间没有顺序。

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

以下是性能比较：

这句话的意思是："

reference

"

- Yilmaz