手撕 LRU 算法（更正版）

時間：2021-08-01 01:05:23

關(guān)鍵字：算法 LRU 代碼

手機看文章

掃描二維碼
隨時隨地手機看文章

[導讀]大家好，我是小林。昨天發(fā)了一篇「小林手撕LRU算法」的文章，當時這個算法寫比較趕，導致代碼里面有一些不對的地方，被細心的讀者發(fā)現(xiàn)了。有時候自己寫的代碼真的是當局者迷，旁觀者清，所以codereview環(huán)節(jié)是很重要的，很難有人能一次性寫出「完美」的代碼。問題一上篇文章我說std::...

大家好，我是小林。昨天發(fā)了一篇「小林手撕 LRU 算法」的文章，當時這個算法寫比較趕，導致代碼里面有一些不對的地方，被細心的讀者發(fā)現(xiàn)了。
有時候自己寫的代碼真的是當局者迷，旁觀者清，所以 codereview 環(huán)節(jié)是很重要的，很難有人能一次性寫出「完美」的代碼。

問題一

上篇文章我說 std::map 是哈希表，這里犯了錯誤。

C 使用哈希表數(shù)據(jù)結(jié)構(gòu)的容器是 std::unordered_map，查詢效率是 O(1)。
而 std::map 的底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹，查詢效率是 O(logn)。
這兩個我常常搞混了，老是覺得有 map 字眼的容器的底層數(shù)據(jù)結(jié)構(gòu)是哈希表，這其實是很嚴重的錯誤了，因為當數(shù)據(jù)量非常大的時候，哈希表和紅黑樹的查詢效率的差距很快就顯現(xiàn)出來了。

問題二

在實現(xiàn) get 函數(shù)的時候，我把已經(jīng)被 erase 的迭代器，重新 push_front 到鏈表里了。

這個代碼我當時是在 C 在線編譯網(wǎng)站運行的，當時測試的時候沒問題。然后有個讀者反饋他跑了這個代碼發(fā)現(xiàn)會出問題。
然后，我在 Linux 環(huán)境編譯測試了下，發(fā)現(xiàn)被 erase 的迭代器，就會變成空值了，所以相當于 push_front 了個寂寞。
因此，應該改成重新創(chuàng)建個 pair 來存放即將被 erase 的迭代器的內(nèi)容，然后再將 pair 加入到鏈表里，如下代碼：

反思下，以后驗證代碼還是在實際環(huán)境上跑，雖然 C 在線編譯網(wǎng)站方便，但是有問題未必能發(fā)現(xiàn)出來。
把上面的問題更正后，完整版的 LRU 代碼如下：

犯錯是好事。
至少我比昨天的自己更博學了些。