LRU和LFU有什么区别

本文介绍了LRU和LFU有什么区别的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

LRU 和 LFU 缓存实现之间有什么区别?

What is the difference between LRU and LFU cache implementations?

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

I know that LRU can be implemented using LinkedHashMap. But how to implement LFU cache?

推荐答案

让我们考虑一个缓存容量为3的恒定缓存请求流，请参见下文:

Let's consider a constant stream of cache requests with a cache capacity of 3, see below:

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

如果我们仅考虑具有HashMap +双链表实现且具有O(1)驱逐时间和O(1)加载时间的最近最少使用(LRU)缓存，我们将获得以下内容如上所述处理缓存请求时缓存的元素.

If we just consider a Least Recently Used (LRU) cache with a HashMap + doubly linked list implementation with O(1) eviction time and O(1) load time, we would have the following elements cached while processing the caching requests as mentioned above.

[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的可能性更高，即使最近使用它，我们也不应将其撤回.

When you look at this example, you can easily see that we can do better - given the higher expected chance of requesting an A in the future, we should not evict it even if it was least recently used.

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

最不常用(LFU)缓存通过跟踪缓存请求在其驱逐算法中已使用了多少次来利用此信息.

Least Frequently Used (LFU) cache takes advantage of this information by keeping track of how many times the cache request has been used in its eviction algorithm.