理解LRU算法

Question

我正试着去理解LRU，它对我来说毫无意义。如果我理解了它，那么我将更容易编码。有人能陪我走过台阶吗？喜欢,

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

我只是看上去跟不上。它是如何跟踪最近使用的最少的？最近最不应该用的不是指数后面的那个吗？

​

​

Answer 1

为每个“项目”存储两个项目。值(当然)和“时间”，它是一个不断增长的整数。

因此，使用您的数据，假设从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 2

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

Answer 3

这是我为LRU缓存提供的简单示例c++实现，它结合了哈希(Unordered_map)和列表。列表中的项具有访问映射的键，映射中的项具有列表的迭代器来访问列表。因此，每个方法调用都是复杂的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;
        };

};