LRU算法介绍
众所周知，操作系统缓存是有限的，当缓存快要耗尽的时候，我们就需要对已经存在的页面进行置换。记得在大二学习操作系统的时候介绍过几个缓存策略，分别是OPT，FIFO，LRU，Clock，LFU。我们本文简单介绍一下LRU算法的实现。
LRU算法实现
实现简介
我在网上搜索LRU算法的时候看到leetcode一道题目，这里我以leetcode 146一套题目为例，讲解LRU算法的实现。我使用的语言是C++，如果你熟悉C++的话用LinkedList+map，Java的话有现成的数据结构即LinkedHashMap。
实现思路
实现主要使用的数据结构是LinkedList + map(即链表+哈希表)。实现主要的函数是init、get和put。init函数负责初始化，其中包括cache大小的设置等；get函数负责获取缓存中的对于的页面。put函数负责将新的页面插入缓存中。下面我具体介绍一下这三个函数的具体实现。
- 在
init函数中，我们初始化一个LinkedList = NULL;，同时初始化这个cache的大小capacity和现在的页面数count。 - 在
get函数中，我们根据key到hash表中去查询有没有对应的节点，如果存在，将这个节点摘出来，放在链表最头部的位置。这里摘出来有个小技巧，我们可以将这个节点和他后面的几点数据互换，然后删除后面的节点。如图
RemoveNode
- 在
put函数中，我们先查询这个节点是不是存在，如果存在，根据value生成新的节点，存在map中，替换原来的节点，并且push到链表的头部。如果不存在，直接生成新节点，存入map，并push到链表头部。
实现代码
//
// main.cpp
// LRU_Demo
//
// Created by 李林 on 2017/9/14.
// Copyright © 2017年 lee. All rights reserved.
//
#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#include <iterator>
using namespace std;
/*
核心思想：map+List。类似于Java中LinkedHashMap。
map变化和List变化需要同步，查询运用map优势，增减运用List优势。
*/
struct Node {
int key;
int val;
Node *next;
Node(int k, int v) : key(k), val(v), next(NULL) {
}
};
class LRUCache {
public:
LRUCache(int capacity) {
count = 0;
size = capacity;
cacheList = NULL;
}
int get(int key) {
if (cacheList == NULL) return -1;
map<int, Node *>::iterator it = mp.find(key);
if (it == mp.end()) {
return -1;
} else {
Node *newNode = it->second;
pushNewNodeToFront(newNode);
return cacheList->val;
}
}
void put(int key, int val) {
if (cacheList == NULL) {
cacheList = new Node(key, val);
cacheList->next = NULL;
mp[key] = cacheList;
count++;
} else {
map<int, Node *>::iterator it = mp.find(key);
if (it == mp.end()) { // 没有这个key
if (count == size) {
Node *p = cacheList;
Node *pre = p;
while (p->next != NULL) {
pre = p;
p = p->next;
}
mp.erase(p->key);
count--;
if (pre == p) { // 只有一个节点
cacheList = NULL;
} else {
pre->next = NULL;
}
free(p);
}
Node *newNode = new Node(key, val);
newNode->next = cacheList;
cacheList = newNode;
mp[key] = cacheList;
count++;
} else { // 有这个key
Node *newNode = it->second;
newNode->val = val;
pushNewNodeToFront(newNode);
}
}
}
void pushNewNodeToFront(Node *newNode) {
if (count == 1) return ;
if (newNode == cacheList) return ;
Node *Next = newNode->next;
if (Next) {
newNode->next = Next->next;
swap(newNode->key, Next->key);
swap(newNode->val, Next->val);
Next->next = cacheList;
cacheList = Next;
// 勿忘map操作
swap(mp[newNode->key], mp[Next->key]);
} else { // 最后一个节点
Node *p = cacheList;
while (p->next != newNode) {
p = p->next;
}
p->next = NULL;
newNode->next = cacheList;
cacheList = newNode;
}
}
private:
int count;
int size;
Node *cacheList;
map<int, Node*> mp;
};
int main(int argc, const char * argv[]) {
LRUCache cache(2);
cache.put(1, 1);
cache.put(2, 2);
cout<<cache.get(1)<<endl; // returns 1
cache.put(3, 3); // evicts key 2
cout<<cache.get(2)<<endl; // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cout<<cache.get(1)<<endl; // returns -1 (not found)
cout<<cache.get(3)<<endl; // returns 3
cout<<cache.get(4)<<endl; // returns 4
return 0;
}
运行结果
运行的结果是1，-1，-1，3，4。（-1代表未命中）
运行结果
