了解LRU算法
8 c c++ algorithm page-replacement
我试图理解LRU,这对我来说毫无意义.如果我理解它,那么我将更容易编码.有人可以带我走过这些台阶吗？喜欢,
- 如果您当前所在的参考字符串在数组中,那么您是否会增加到下一个空格？
- 当您检查缓冲区中是否有某些东西时,我们是否需要扫描我们所处的位置或整个阵列？
我似乎无法跟进.它是如何跟踪最近最少使用的？最近最少使用的是索引后的那个吗？
LRU 通常放在一个列表中。当一个项目被访问时，把它从列表中删除（如果它在那里），然后把它推到后面。列表的后面是最近使用的。因为您不断将使用过的项目移到列表的后面，所以最不常用的项目自然会排在列表的前面。当没有足够的空间时，你从前面弹出。
- @TonyRad：这是正确的（如果映射意味着 _hash_ 映射，则正常的 C++SL 映射具有 _O(log(n))_），但请注意，如果缓存运行良好，您将要求最近的（或通常情况下的第 2 个，最近的第 3 个）项目，它（几乎）与 O(1) 一样好。另一方面，映射（或哈希）具有与 _O_ 相关联的不可忽略的 _k_。这意味着尽管算法复杂度较低，但它很可能会更慢。如果上述关于时间局部性的假设不成立，则基于列表的缓存将表现不佳，但在这种情况下 _any cache_ 将表现得非常糟糕。 (2认同)
为每个"项目"存储两个项目.值(当然)和"时间"是一个不断增加的整数.
因此,使用您的数据,假设按顺序访问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