我正在尝试理解 LRU，但它对我来说毫无意义。如果我理解它，那么我编写代码会更容易。有人可以引导我完成这些步骤吗？ 喜欢，
- 如果您当前所在的引用字符串在数组中，则 你增加到下一个空间吗？
- 当您检查缓冲区中是否有内容时，我们是否需要扫描我们所在的位置或整个数组？
我似乎无法跟上。它是如何跟踪最近最少使用的？最近最少使用的不应该是你的索引之后的那个吗？
最佳答案
为每个“项目”存储两个项目。值(当然)和不断增加的整数“时间”。
因此，使用您的数据，假设按顺序访问 1 到 4:
(1, 1), (2, 2), (3, 3), (4, 4)
访问“1”(为清楚起见按时间排序，时间 = 5)
(2, 2), (3, 3), (4, 4), (1, 5)
访问“2”(为清楚起见按时间排序，时间 = 6)
(3, 3), (4, 4), (1, 5), (2, 6)
访问将找不到的“5”，导致缓存未命中。为了找到存储“5”的“空间”，我们需要刷新最近最少使用(LRU)。这意味着删除“3”。请注意时间 = 7。
(4, 4), (1, 5), (2, 6), (5, 7)
访问“1”(为清楚起见按时间排序，时间 = 8)
(4, 4), (2, 6), (5, 7), (1, 8)
访问“2”(为清楚起见按时间排序，时间 = 9)
(4, 4), (5, 7), (1, 8), (2, 9)
访问将找不到的“3”，导致缓存未命中。为了找到存储“3”的“空间”，我们需要刷新最近最少使用(LRU)。这意味着删除“4”。请注意，时间 = 10。
(5, 7), (1, 8), (2, 9), (3, 10)
访问将找不到的“4”，导致缓存未命中。为了找到存储“4”的“空间”，我们需要刷新最近最少使用(LRU)。这意味着删除“5”。请注意时间 = 11。
(1, 8), (2, 9), (3, 10), (4, 11)
访问将找不到的“5”，导致缓存未命中。为了找到存储“5”的“空间”，我们需要刷新最近最少使用(LRU)。这意味着删除“1”。请注意时间 = 12。
(2, 9), (3, 10), (4, 11), (5, 12)
既然您知道如何选择要刷新的项目，并且有一个工作示例，那么在不在数组中四处移动的情况下刷新项目就由您来实现了。
--- 编辑附加说明---
好的，以列表形式显示东西的想法似乎提出了一些问题，所以我将以数组形式显示它
访问 1，缓存未命中，空槽可用，存储在第一个可用槽中
Value Age
1 1
--- ---
--- ---
--- ---
访问 2，缓存未命中，空槽可用，存储在第一个可用槽中
Value Age
1 1
2 2
--- ---
--- ---
访问 3，缓存未命中，空槽可用，存储在第一个可用槽中
Value Age
1 1
2 2
3 3
--- ---
访问 4，缓存未命中，空槽可用，存储在第一个可用槽中
Value Age
1 1
2 2
3 3
4 4
访问1，缓存命中，更新访问时间
Value Age
1 5
2 2
3 3
4 4
访问2，缓存命中，更新访问时间
Value Age
1 5
2 6
3 3
4 4
访问 5，缓存未命中，没有可用的空，丢弃并替换“最近最少使用”
Value Age
1 5
2 6
5 7
4 4
访问1，缓存命中，更新访问时间
Value Age
1 8
2 6
5 7
4 4
访问2，缓存命中，更新访问时间
Value Age
1 8
2 9
5 7
4 4
访问 3，缓存未命中，没有可用的空，丢弃并替换“最近最少使用”
Value Age
1 8
2 9
5 7
3 10
访问 4，缓存未命中，没有可用的空，丢弃并替换“最近最少使用”
Value Age
1 8
2 9
4 11
3 10
访问 5，缓存未命中，没有可用的空，丢弃并替换“最近最少使用”
Value Age
5 12
2 9
4 11
3 10
关于c++ - 理解 LRU 算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13337854/