網(wǎng)站設(shè)計(jì)審美角度怎么去推廣一個(gè)app
什么是 LRU
LRU (最近最少使用算法),
最早是在操作系統(tǒng)中接觸到的, 它是一種內(nèi)存數(shù)據(jù)淘汰策略, 常用于緩存系統(tǒng)的淘汰策略.
LRU算法基于局部性原理, 即最近被訪問(wèn)的數(shù)據(jù)在未來(lái)被訪問(wèn)的概率更高, 因此應(yīng)該保留最近被訪問(wèn)的數(shù)據(jù).
最近最少使用的解釋
LRU (最近最少使用算法), 中的 "最近" 不是其絕對(duì)值的修飾, 而是一個(gè)范圍.
如: 你最近去了那些地方, 最近看了哪些書(shū).
而不是: 離你最近的人是誰(shuí), 離你最近的座位是哪一個(gè).?
了解了最近的意義, 那么串聯(lián)起來(lái)就是: 最近使用的一堆數(shù)據(jù)中, 哪一個(gè)數(shù)據(jù)使用的是最少的
LRU原理
下面展示了 LRU?算法的基本原理.
可以看到, 在 LRU 算法中, 涉及到了對(duì)象的移動(dòng), 如果使用 數(shù)組 來(lái)作為緩存, 那么移動(dòng)對(duì)象的效率很慢. 因?yàn)樵谶@個(gè)算法中, 經(jīng)常涉及到頭插元素, 數(shù)組 的頭插是O(n^2), 非常的慢.
所以推薦使用 雙向鏈表 來(lái)實(shí)現(xiàn).
146. LRU 緩存 - 力扣(LeetCode)
但是在題目中, 要求查找和插入的時(shí)間復(fù)雜度為O(1);
雙向鏈表的插入刪除時(shí)間復(fù)雜度為O(1), 但是查找的時(shí)間復(fù)雜度為O(n).
雙向鏈表 + 哈希表
單使用雙向鏈表, 查找的時(shí)間復(fù)雜度為O(n), 那么數(shù)據(jù)結(jié)構(gòu)的查找操作的時(shí)間復(fù)雜度為O(1)?
答案很明顯: 哈希表
?定義鏈表節(jié)點(diǎn) ListNode
struct ListNode
{
public:ListNode(){}ListNode(int k, int v):key(k),value(v){}~ListNode(){}int key;int value;// 節(jié)點(diǎn)中不僅存儲(chǔ) value, 還存儲(chǔ) key, 這在后面的 put 函數(shù)中有用ListNode* next;ListNode* prev;
};
LRUcache 成員屬性
class LRUCache {
public:int _size = 0; // 記錄緩存中已經(jīng)緩存了多少數(shù)據(jù)int _capacity = 0; // 記錄緩存大小 (可緩存的數(shù)據(jù)個(gè)數(shù))ListNode* head = nullptr; // 雙向鏈表的頭節(jié)點(diǎn)ListNode* tail = nullptr; // 雙向鏈表的尾節(jié)點(diǎn)unordered_map<int, ListNode*> table;// 底層是通過(guò) hashtable 實(shí)現(xiàn)的map, 用來(lái)通過(guò) kev 查找節(jié)點(diǎn)
}
LRUcache 成員方法
構(gòu)造 / get / put 函數(shù)
class LRUCache {
public:LRUCache(int capacity) {_capacity = capacity; // 記錄緩存的大小// 初始化鏈表的 頭節(jié)點(diǎn) 和 尾節(jié)點(diǎn)head = new ListNode;tail = new ListNode;// 將頭尾節(jié)點(diǎn)連接起來(lái)head->next = tail;head->prev = tail;tail->next = head;tail->prev = head;}// 通過(guò) key 獲取對(duì)應(yīng)的 value. 如果 key 不存在, 則返回 -1int get(int key) {auto it = table.find(key); // 通過(guò) hashtable 查找 key 是否存在if(it == table.end()){return -1; // 不存在對(duì)應(yīng)的 [key, value], 返回 -1}// 存在 key, 記錄value, 然后更新這個(gè)節(jié)點(diǎn), 將這個(gè)節(jié)點(diǎn)移動(dòng)到鏈表頭部int ret = it->second->value;MoveToHead(it->second); // 將這個(gè)節(jié)點(diǎn)移動(dòng)到頭部return ret;}// 插入一對(duì)鍵值對(duì) [key, value]void put(int key, int value) {auto it = table.find(key); // 在 hashtable 中查找是否已經(jīng)存在 keyif(it != table.end()) // 已經(jīng)存在 key 則更新節(jié)點(diǎn)的值, 并且將這個(gè)節(jié)點(diǎn)移動(dòng)到鏈表頭部{// 更新節(jié)點(diǎn)it->second->value = value;MoveToHead(it->second); // 將節(jié)點(diǎn)移動(dòng)到鏈表頭部return; // 直接返回, 下面是進(jìn)行插入的操作}// key 不存在, 判斷 空間是否已滿, 滿了就需要?jiǎng)h除 鏈表末尾的節(jié)點(diǎn)if(_size == _capacity){// ListNode 中記錄的 key 就起作用了, 如果只有 value, 那么就還需要遍歷 tableint back = tail->prev->key;table.erase(back); // 刪除 hashtable 中這個(gè)節(jié)點(diǎn)的記錄pop_back(); // 刪除尾部節(jié)點(diǎn)--_size;}// 鏈表末尾的節(jié)點(diǎn)已被刪除, 現(xiàn)在需要向 鏈表頭部 插入 新的節(jié)點(diǎn)ListNode* node = push_front(key, value);table[key] = node; // 在 hashtable 中記錄這個(gè)新的節(jié)點(diǎn)++_size;}
};
MoveToHead / push_front / pop_back 函數(shù)
class LRUCache {
public:// 將 node 移動(dòng)到鏈表頭部void MoveToHead(ListNode* node){if(node == head->next) // 如果這個(gè)節(jié)點(diǎn)就是頭部, 那么就不移動(dòng){return;}ListNode* node_next = node->next; // 記錄 node 節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)ListNode* node_prev = node->prev; // 記錄 node 節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)node_prev->next = node_next; // 將 node 的前后節(jié)點(diǎn)連接起來(lái)node_next->prev = node_prev;// 將 node 節(jié)點(diǎn)鏈接到鏈表首部node->prev = head; node->next = head->next;head->next->prev = node;head->next = node;}// 頭插ListNode* push_front(int key, int value){ListNode* node = new ListNode(key, value);ListNode* next = head->next;head->next = node;node->prev = head;next->prev = node;node->next = next;return node;}// 尾刪void pop_back(){ListNode* prev = tail->prev->prev;ListNode* cur = tail->prev;prev->next = tail;tail->prev = prev;delete cur;}
};
?
?
完整代碼
class LRUCache {
public:struct ListNode{public:ListNode(){}ListNode(int k, int v):key(k),value(v){}~ListNode(){}int key;int value;ListNode* next;ListNode* prev;};int _size = 0;int _capacity = 0;ListNode* head = nullptr;ListNode* tail = nullptr;unordered_map<int, ListNode*> table;LRUCache(int capacity) {_capacity = capacity;head = new ListNode;tail = new ListNode;head->next = tail;head->prev = tail;tail->next = head;tail->prev = head;}int get(int key) {auto it = table.find(key);if(it == table.end()){return -1;}int ret = it->second->value;MoveToHead(it->second); // 將這個(gè)節(jié)點(diǎn)移動(dòng)到頭部return ret;}void put(int key, int value) {auto it = table.find(key);if(it != table.end()){// 更新節(jié)點(diǎn)it->second->value = value;MoveToHead(it->second);return;}if(_size == _capacity){int back = tail->prev->key;table.erase(back); // 刪除 hashtable 中的鍵值對(duì)pop_back(); // 刪除尾部節(jié)點(diǎn)--_size;}ListNode* node = push_front(key, value);table[key] = node;++_size;}void MoveToHead(ListNode* node){if(node == head->next){return;}ListNode* node_next = node->next;ListNode* node_prev = node->prev;node_prev->next = node_next;node_next->prev = node_prev;node->prev = head;node->next = head->next;head->next->prev = node;head->next = node;}ListNode* push_front(int key, int value){ListNode* node = new ListNode(key, value);ListNode* next = head->next;head->next = node;node->prev = head;next->prev = node;node->next = next;return node;}void pop_back(){ListNode* prev = tail->prev->prev;ListNode* cur = tail->prev;prev->next = tail;tail->prev = prev;delete cur;}};