漫畫:什麼是LRU演算法?
————— 兩個月前 —————
使用者資訊當然是存在資料庫裡。但是由於我們對使用者系統的效能要求比較高,顯然不能每一次請求都去查詢資料庫。
所以,小灰在記憶體中建立了一個雜湊表作為快取,每次查詢一個使用者的時候先在雜湊表中查詢,以此提高訪問效能。
很快,使用者系統上線了,小灰美美地休息了幾天。
一個多月之後......
———————————————
什麼是雜湊連結串列呢?
我們都知道,雜湊表是由若干個Key-Value所組成。在“邏輯”上,這些Key-Value是無所謂排列順序的,誰先誰後都一樣。
在雜湊連結串列當中,這些Key-Value不再是彼此無關的存在,而是被一個鏈條串了起來。每一個Key-Value都具有它的前驅Key-Value、後繼Key-Value,就像雙向連結串列中的節點一樣。
這樣一來,原本無序的雜湊表擁有了固定的排列順序。
讓我們以使用者資訊的需求為例,來演示一下LRU演算法的基本思路:
1.假設我們使用雜湊連結串列來快取使用者資訊,目前快取了4個使用者,這4個使用者是按照時間順序依次從連結串列右端插入的。
2.此時,業務方訪問使用者5,由於雜湊連結串列中沒有使用者5的資料,我們從資料庫中讀取出來,插入到快取當中。這時候,連結串列中最右端是最新訪問到的使用者5,最左端是最近最少訪問的使用者1。
3.接下來,業務方訪問使用者2,雜湊連結串列中存在使用者2的資料,我們怎麼做呢?我們把使用者2從它的前驅節點和後繼節點之間移除,重新插入到連結串列最右端。這時候,連結串列中最右端變成了最新訪問到的使用者2,最左端仍然是最近最少訪問的使用者1。
4.接下來,業務方請求修改使用者4的資訊。同樣道理,我們把使用者4從原來的位置移動到連結串列最右側,並把使用者資訊的值更新。這時候,連結串列中最右端是最新訪問到的使用者4,最左端仍然是最近最少訪問的使用者1。
5.後來業務方換口味了,訪問使用者6,使用者6在快取裡沒有,需要插入到雜湊連結串列。假設這時候快取容量已經達到上限,必須先刪除最近最少訪問的資料,那麼位於雜湊連結串列最左端的使用者1就會被刪除掉,然後再把使用者6插入到最右端。
以上,就是LRU演算法的基本思路。
需要注意的是,這段不是執行緒安全的,要想做到執行緒安全,需要加上synchronized修飾符。
告訴大家一個好訊息,小灰的《漫畫演算法》全面上架啦,在短短的兩週裡,本書一度霸佔著各大暢銷榜榜首!
掃碼檢視詳情
小灰把兩年多以來積累的漫畫作品進行了篩選和優化,並加上了一些更為基礎和系統的入門章節,最終完成了本書的六大篇章:
第一章 演算法概述
介紹了演算法和資料結構的相關概念,告訴大家演算法是什麼,資料結構又是什麼,它們有哪些用途,如何分析時間複雜度,如何分析空間複雜度。
第二章 資料結構基礎
介紹了最基本的資料結構,包括陣列、連結串列、棧、佇列、雜湊表的概念和讀寫操作。
第三章 樹
介紹了樹和二叉樹的概念、二叉樹的各種遍歷方式、二叉堆和優先佇列的應用。
第四章 排序演算法
介紹了幾種典型的排序演算法,包括氣泡排序、快速排序、堆排序、計數排序、桶排序。
第五章 面試中的演算法
介紹了10餘道職場上流行的演算法面試題及詳細的解題思路。例如怎樣判斷連結串列有環、怎樣計算大整數相加等。
第六章 演算法的實際應用
介紹了演算法在職場上的一些應用,例如使用LRU演算法來淘汰冷資料,使用Bitmap演算法來統計使用者特徵等。
本書是全綵印製,書中的每一章、每一節、每一句話、每一幅圖、每一行程式碼,都經過了小灰和編輯們的精心打磨,力求用最為直白的方式把知識講明白、講透徹。
早期的漫畫中存在一些敘述錯誤和表達不清晰的地方,小灰在本書中做了修正和補充;同時書中增加了許多全新的篇章,使得本書的內容更加系統和全面。
對於渴望學習演算法的小夥伴,無論你是正在學習計算機專業的學生,還是已經進入職場的新人,亦或是擁有多年工作經驗卻不擅長演算法的老手,這本《漫畫演算法》都能幫助你告別對演算法的恐懼,認識演算法、掌握演算法。
掃碼購買
新品8折優惠中