優先隊列
現在有一個大小為capacity的儲存空間，會不斷的加入關鍵字以及對應的數值key, value，假如儲存空間滿了，就選擇「最久沒用」的key刪除，然後加入新的key, value。
我們能用一個變數time去紀錄現在操作關鍵字的時間，來讓之後刪除時可以快速找到最舊的key。為了要快速找到時間最小的操作，用優先隊列pq紀錄，並根據操作時間排序，能快速取出最舊的key。
此時有個問題出現了，在更新資料時，會將新的操作時間加入到pq，此時在pq當中有舊版本與新版本的時間，應該要刪去舊版本。為了刪去舊版本，建立一個哈希表key_time，去紀錄key對應的「最新」操作時間，在取出pq時，用以判斷資料是不是最新的。
程式碼
class LRUCache {
public:
using pii = pair<int, int>;
int size; // 紀錄最多可以放幾個資料
int time;
priority_queue<pii, vector<pii>, greater<pii>> pq;// pq = {修改時間, key}, 按照時間排序, 用來取最久沒有被修改的 key
unordered_map<int, int> umap; // 當前 key 對應的數值
unordered_map<int, int> key_time; // 紀錄 key 對應的最新時間
public:
LRUCache(int capacity) : size(capacity), time(0) {}
int get(int key) {
if(umap.find(key) == umap.end()) return -1;
// 取得 key 對應的數值
++time;
key_time[key] = time;
pq.push({time, key});
return umap[key];
}
void put(int key, int value) {
// 將 key 對應的數值覆蓋。
++time;
if(umap.find(key) != umap.end()) { // 不是新資料，不會有空間不足的問題
umap[key] = value;
key_time[key] = time;
pq.push({time, key});
return;
}
else {
if(umap.size() >= size) { // 如果快取滿了，選擇最久以前的那一個項目取代掉
while(!pq.empty()) { // 刪除舊資料, 直到有刪最新資料為止
auto [t, k] = pq.top();
pq.pop();
if(key_time.contains(k) && t == key_time[k]) { // 看時間跟最新資料有沒有對上
key_time.erase(k); // 把最久以前的刪除
umap.erase(k);
break; // 已經刪除資料, 空間足夠
}
// 沒有對上，表示為重複的舊資料， (在判斷前已經從 pq 刪除)
}
}
// 新增現在加入的
umap[key] = value;
key_time[key] = time;
pq.push({time, key});
}
}
};複雜度分析
- 時間複雜度：，為操作次數。
- 空間複雜度：
雙向鏈表
使用鏈表，能將時間複雜度壓縮到。空間複雜度。
- 一個鏈結串列的頭節點，代表最早被操作的key，尾節點則代表最後被操作的key。
- 用一個哈希表紀錄每個key對應到的節點，讓get操作降低到。
- 假如現在的資料到達上限，將最舊的資料刪除，也就是頭節點。
- 當加入新的資料，或是修改現有資料時，將被操作的節點移動到尾端，代表最新的資料。
程式碼
struct DoubleNode {
int key;
int value;
DoubleNode *next, *prev;
DoubleNode(int k, int v) : key(k), value(v), next(nullptr), prev(nullptr) {};
};
class DoubleList {
private:
DoubleNode *head, *tail;
public:
DoubleList() : head(nullptr), tail(nullptr) {}
void addNode(DoubleNode* newNode) {
if(newNode == nullptr) return;
if(head == nullptr) { // 加入第一個節點
head = newNode;
tail = newNode;
}
else { // 將節點連接起來
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
void moveNodeToTail(DoubleNode* node) {
// node 一定在 head 跟 tail 之間有出現過
if(node == tail) return;
if(node == head) {
head = node->next; // 新的頭節點, 跟舊有的斷開
head->prev = nullptr;
}
else {
node->prev->next = node->next;
node->next->prev = node->prev;
}
// 相同的部分
node->prev = tail;
node->next = nullptr;
tail->next = node;
tail = node;
}
DoubleNode* removeHead() { // 刪除最前面的頭節點
if(head == nullptr) return nullptr;
DoubleNode* res = head;
if(head == tail) {
head = nullptr;
tail = nullptr;
}
else {
head = res->next;
head->prev=nullptr;
res->prev = nullptr;
}
return res; // 回傳被斷開的結點
}
};
class LRUCache {
private:
unordered_map<int, DoubleNode*> keyNodemap;
DoubleList nodeList;
int size;
public:
LRUCache(int capacity) : size(capacity) {}
int get(int key) {
if(keyNodemap.find(key) == keyNodemap.end()) {
return -1;
}
DoubleNode* node = keyNodemap[key];
nodeList.moveNodeToTail(node);
return keyNodemap[key]->value;
}
void put(int key, int value) {
if(keyNodemap.find(key) != keyNodemap.end()) { // 舊資料
DoubleNode* node = keyNodemap[key];
node->value = value;
nodeList.moveNodeToTail(node);
}
else { // 新資料
if(keyNodemap.size() == size) { // 資料已滿，需刪除最久沒用的
DoubleNode* oldHead = nodeList.removeHead();
keyNodemap.erase(oldHead->key);
delete oldHead;
}
DoubleNode* newNode = new DoubleNode(key, value);
keyNodemap[key] = newNode;
nodeList.addNode(newNode);
}
}
};複雜度分析
- 時間複雜度：
- 空間複雜度：