LeetCode 146 LRU Cache
4702 ワード
テーマ:
メモリ管理におけるLRU(Least Recently Used)メモリ管理アルゴリズムの実現
メモリ管理アルゴリズムではLRUとLFUが異なり、LRUは最も長く使われていないページを削除します
LFUは最近の使用回数が最も少ないページを削除します
大まかな考え方:
この問題は、メモリ管理の復習をしたところです.
まず、各メモリブロックが使用されている場合、1つのメモリブロックが最近使用されているが、他のブロックの相対的な位置は変わらないため、チェーンテーブルで表すことを考慮し、ここでは双方向チェーンテーブルを使用し、チェーンテーブルは最初からノードを最後にし、最近使用されているほど、つまり最後のノードは最近アクセスされ、容量がいっぱいになったとき、ヘッダノードを削除し、空間を空け、ノードの挿入と移動の複雑さはO(1)である.
setの場合key対応valueを検索する必要があるためmapでメンテナンスを行うことを考慮し,mapでO(logn)の時間複雑度内に対応するノード位置を見つける
では,ノードがメモリプールに存在するか否かの複雑さ,すなわちO(logn),全体の単語操作の時間的複雑さはO(logn)である.
コードは次のとおりです.
Result : Accepted Time : 96 ms
メモリ管理におけるLRU(Least Recently Used)メモリ管理アルゴリズムの実現
メモリ管理アルゴリズムではLRUとLFUが異なり、LRUは最も長く使われていないページを削除します
LFUは最近の使用回数が最も少ないページを削除します
大まかな考え方:
この問題は、メモリ管理の復習をしたところです.
まず、各メモリブロックが使用されている場合、1つのメモリブロックが最近使用されているが、他のブロックの相対的な位置は変わらないため、チェーンテーブルで表すことを考慮し、ここでは双方向チェーンテーブルを使用し、チェーンテーブルは最初からノードを最後にし、最近使用されているほど、つまり最後のノードは最近アクセスされ、容量がいっぱいになったとき、ヘッダノードを削除し、空間を空け、ノードの挿入と移動の複雑さはO(1)である.
setの場合key対応valueを検索する必要があるためmapでメンテナンスを行うことを考慮し,map
では,ノードがメモリプールに存在するか否かの複雑さ,すなわちO(logn),全体の単語操作の時間的複雑さはO(logn)である.
コードは次のとおりです.
Result : Accepted Time : 96 ms
/*
* Author: Gatevin
* Created Time: 2016/3/7 11:06:11
* File Name: test.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
typedef long long lint;
class LRUCache{
private:
struct listNode{
listNode* next;
listNode* prev;
int key;
int value;
listNode(){
next = NULL;
prev = NULL;
key = -1;
value = 0;
}
};
int lruCapacity;
int curCapacityUsed;
listNode* p_Head;
listNode* p_Tail;
map<int, listNode*> M;// key
public:
LRUCache(int capacity) {
if(capacity <= 0) puts("Error, capacity should be at least 1");
p_Head = NULL;
p_Tail = NULL;
lruCapacity = capacity;
curCapacityUsed = 0;
M.clear();
}
void moveToTail(listNode* now){
if(now->next == NULL)//
return;
else{
if(now->prev == NULL){//
p_Head->next->prev = NULL;
p_Head = p_Head->next;
now->next = NULL;
now->prev = p_Tail;
p_Tail->next = now;
p_Tail = now;
return;
}else{//
now->prev->next = now->next;
now->next->prev = now->prev;
p_Tail->next = now;
now->prev = p_Tail;
now->next = NULL;
p_Tail = now;
return;
}
}
}
int get(int key) {
map<int, listNode*> :: iterator it = M.find(key);
if(it == M.end())//Not found
return -1;
else{// ，
moveToTail(it->second);
return it->second->value;
}
}
void set(int key, int value) {
map<int, listNode*> :: iterator it = M.find(key);
if(it == M.end()){//Not found
if(p_Head == NULL){//
p_Head = new listNode();
p_Head->key = key;
p_Head->value = value;
p_Tail = p_Head;
M[key] = p_Head;
curCapacityUsed++;
return;
}else{// ，
if(curCapacityUsed == lruCapacity){// ，
if(p_Head->next == NULL){
M.erase(p_Head->key);
delete p_Head;
p_Head = NULL;
p_Tail = NULL;
curCapacityUsed--;
}else{
M.erase(p_Head->key);
p_Head = p_Head->next;
delete p_Head->prev;
p_Head->prev = NULL;
curCapacityUsed--;
}
}
//
listNode* newTail = new listNode();
newTail->value = value;
newTail->key = key;
if(p_Tail == NULL){
p_Head = newTail;
p_Tail = p_Head;
}else{
p_Tail->next = newTail;
newTail->prev = p_Tail;
p_Tail = newTail;
}
M[key] = p_Tail;
curCapacityUsed++;
}
}else{
moveToTail(it->second);
it->second->value = value;
return;
}
}
};