Green 发表于 2021-8-3 21:41:38

LRU算法

1. LRU是什么

[*]LRU是least Recently Used(LRU) 的缩写,直译的话,称为“最近最少使用”,通常我们也叫做“最久未使用”——我是觉得这样更加贴切
[*]LRU算法,是一种类似Cache替换的算法。                           Cache一般就是一种缓存机制,比如说CPU和主存直接有快速存储的RAM,就是一个Cache,Cache主要用于存储速度相对相差较大的俩硬件之间,作为协调数据传输速度差异,Cache一般是有固定的大小的,不会太大,也不会太小,个中原因也是效率问题;

Cache容量有限,当容量告罄时再有新数据到来时,就会舍弃一部分已经存在的内容(根据某种算法依据),然后存放新到来的数据—对于LRU来说,就是舍弃掉最长时间灭有使用的那个数据,用新数据替换掉它

2.LRU的实现
2.1 考虑前提
LRU需要实现快速的插入和删除
LRU需要快速访问到需要的数据
2.2 实现
快速插入与删除,这里我采用 list标准容器, 快速访问选择了哈希map(unordered_map),关于LRU的实现有许多,我的code如下(运行环境 vs 2019)//LRU.hC
#pragma once
#include<unordered_map>
#include<list>

class LRUCache {
public:
        LRUCache(int capacity);
       
        void put(int key, int value);
        int get(int key); // 获取值
private:
        int capacity_; // 容量
        std::list<std::pair<int, int>> list_;
        std::unordered_map<int, std::list<std::pair<int, int>>::iterator> hashmap_;
//将list的迭代器作为map的val值,为直接访问提供了好大的便捷
};//LRU.cpp
#include"LRu.h"
#include<iostream>

using namespace std;

LRUCache::LRUCache(int capacity)
{
        capacity_ = capacity;
}
void LRUCache::put(int key, int value)
{
        auto hash_it = hashmap_.find(key);
        if (hash_it == hashmap_.end())
        {
                if (list_.size() >= capacity_)
                {
                        hashmap_.erase(list_.back().first);
                        list_.pop_back();
                }
                list_.push_front(make_pair(key, value));
                hashmap_ = list_.begin();
        }
        else {
                auto listits = hash_it->second;
                pair<int, int> val = *listits;

                list_.erase(listits);
                list_.push_front(val);
                hashmap_ = list_.begin();
        }
}
int LRUCache::get(int key)
{
        auto hash_it = hashmap_.find(key);
        if (hash_it == hashmap_.end())
        {
                cout << "can not find " << "key" << "in MAP" << endl;
                return -1;
        }
        auto listits = hash_it->second;
        pair<int, int> val = *listits;

        list_.erase(listits);
        list_.push_front(val);
        hashmap_ = list_.begin();
        std::cout << val.second << endl;
        return val.second;
}//main.cpp
#pragma once
#include"LRu.h"
#include<iostream>

void test()
{
        /*
        int ret;
        //LRUCache lru_m(2);
        ret = lru_m.get(1);
        std::cout << ret << std::endl;
        lru_m.put(1, 2);*/
        //LRUCache cache = new LRUCache(2);
        LRUCache lru_m(2);
        lru_m.put(1, 1);
        lru_m.put(2, 2);

    lru_m.get(1);
        lru_m.put(3, 3);
        lru_m.get(2);
        lru_m.get(1);



}
int main()
{
        test();
        return 0;
}2.3 结果如下:





文档来源:51CTO技术博客https://blog.51cto.com/u_14632688/3260115
页: [1]
查看完整版本: LRU算法