c++ - 了解 LRU 算法

Question

我试图理解 LRU，它对我来说毫无意义。如果我理解它，那么我将更容易编码。有人可以帮我完成这些步骤吗？像，

1. 如果您当前所在的引用字符串在数组中，那么您是否递增到下一个空格？
2. 当您检查缓冲区中是否有东西时，我们是否需要扫描我们所在的位置或整个阵列？

我似乎无法跟上。它如何跟踪最近最少使用的？最近最少使用的不应该是您所在索引之后的那个吗？

Answer 1

LRU 通常放在一个列表中。当一个项目被访问时，将它从列表中移除（如果它在那里），并将它推到后面。列表的后面是最近使用的。因为您不断地将使用过的物品移到列表的后面，所以最少使用的物品自然会排在列表的前面。当没有足够的空间时，你从前面弹出。

Answer 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

Answer 3

这是我的 LRU 缓存的简单示例 C++ 实现，结合了 hash(unordered_map) 和 list。列表中的项目具有访问地图的键，地图上的项目具有访问列表的列表迭代器。因此，每个方法调用的复杂度都是 O(1)。

#include <list>
#include <unordered_map>
#include <assert.h>

using namespace std;

template <class KEY_T, class VAL_T> class LRUCache{
private:
        list< pair<KEY_T,VAL_T> > item_list;
        unordered_map<KEY_T, decltype(item_list.begin()) > item_map;
        size_t cache_size;
private:
        void clean(void){
                while(item_map.size()>cache_size){
                        auto last_it = item_list.end(); last_it --;
                        item_map.erase(last_it->first);
                        item_list.pop_back();
                }
        };
public:
        LRUCache(int cache_size_):cache_size(cache_size_){
                ;
        };

        void put(const KEY_T &key, const VAL_T &val){
                auto it = item_map.find(key);
                if(it != item_map.end()){
                        item_list.erase(it->second);
                        item_map.erase(it);
                }
                item_list.push_front(make_pair(key,val));
                item_map.insert(make_pair(key, item_list.begin()));
                clean();
        };
        bool exist(const KEY_T &key){
                return (item_map.count(key)>0);
        };
        VAL_T get(const KEY_T &key){
                assert(exist(key));
                auto it = item_map.find(key);
                item_list.splice(item_list.begin(), item_list, it->second);
                return it->second->second;
        };

};