LRU算法介紹
眾所周知，操作系統(tǒng)緩存是有限的，當緩存快要耗盡的時候冤灾，我們就需要對已經(jīng)存在的頁面進行置換。記得在大二學習操作系統(tǒng)的時候介紹過幾個緩存策略辕近，分別是OPT韵吨，F(xiàn)IFO，LRU移宅，Clock归粉，LFU。我們本文簡單介紹一下LRU算法的實現(xiàn)漏峰。
LRU算法實現(xiàn)
實現(xiàn)簡介
我在網(wǎng)上搜索LRU算法的時候看到leetcode一道題目糠悼，這里我以leetcode 146一套題目為例，講解LRU算法的實現(xiàn)浅乔。我使用的語言是C++绢掰，如果你熟悉C++的話用LinkedList+map，Java的話有現(xiàn)成的數(shù)據(jù)結構即LinkedHashMap。
實現(xiàn)思路
實現(xiàn)主要使用的數(shù)據(jù)結構是LinkedList + map(即鏈表+哈希表)滴劲。實現(xiàn)主要的函數(shù)是init、get和put顾复。init函數(shù)負責初始化班挖，其中包括cache大小的設置等；get函數(shù)負責獲取緩存中的對于的頁面芯砸。put函數(shù)負責將新的頁面插入緩存中萧芙。下面我具體介紹一下這三個函數(shù)的具體實現(xiàn)。
- 在
init函數(shù)中假丧，我們初始化一個LinkedList = NULL;双揪，同時初始化這個cache的大小capacity和現(xiàn)在的頁面數(shù)count。 - 在
get函數(shù)中包帚，我們根據(jù)key到hash表中去查詢有沒有對應的節(jié)點渔期，如果存在，將這個節(jié)點摘出來渴邦，放在鏈表最頭部的位置疯趟。這里摘出來有個小技巧，我們可以將這個節(jié)點和他后面的幾點數(shù)據(jù)互換谋梭，然后刪除后面的節(jié)點信峻。如圖
RemoveNode
- 在
put函數(shù)中，我們先查詢這個節(jié)點是不是存在瓮床，如果存在盹舞，根據(jù)value生成新的節(jié)點，存在map中隘庄，替換原來的節(jié)點踢步，并且push到鏈表的頭部。如果不存在峭沦，直接生成新節(jié)點贾虽，存入map，并push到鏈表頭部吼鱼。
實現(xiàn)代碼
//
// 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優(yōu)勢地粪，增減運用List優(yōu)勢。
*/
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) { // 只有一個節(jié)點
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 { // 最后一個節(jié)點
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代表未命中）
運行結果
