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

如果我们只考虑具有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)高速缓存通过跟踪在其逐出算法中使用高速缓存请求的次数来利用该信息.

Answer 2

LRU是一种称为最近最少使用的缓存的缓存逐出算法.

看看这个资源

LFU是一种称为最不常用的缓存的缓存逐出算法.

它需要三个数据结构.一个是哈希表,用于缓存键/值,以便给定一个键,我们可以在O(1)处检索缓存条目.第二个是每个访问频率的双链表.最大频率限制在高速缓存大小,以避免创建越来越多的频率列表条目.如果我们有一个最大大小为4的缓存,那么我们将得到4个不同的频率.每个频率将具有双链表以跟踪属于该特定频率的高速缓存条目.第三种数据结构将以某种方式链接这些频率列表.它可以是一个数组或另一个链表,这样在访问高速缓存条目时,它可以很容易地在时间O(1)中提升到下一个频率列表.

Answer 3

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