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]