緩存算法（頁面置換算法）-FIFO、LFU、LRU

緩存算法（頁面置換算法）-FIFO、LFU、LRU

　　在前一篇文章中通過leetcode的一道題目了解了LRU算法的具體設計思路，下面繼續來探讨一下另外兩種常見的Cache算法：FIFO、LFU

　　FIFO（First in First out），先進先出。其實在作業系統的設計理念中很多地方都利用到了先進先出的思想，比如作業排程（先來先服務），為什麼這個原則在很多地方都會用到呢？因為這個原則簡單、且符合人們的慣性思維，具備公平性，并且實作起來簡單，直接使用資料結構中的隊列即可實作。

　　在FIFO Cache設計中，核心原則就是：如果一個資料最先進入緩存中，則應該最早淘汰掉。也就是說，當緩存滿的時候，應當把最先進入緩存的資料給淘汰掉。在FIFO Cache中應該支援以下操作;

　　get(key)：如果Cache中存在該key，則傳回對應的value值，否則，傳回-1；

　　set(key,value)：如果Cache中存在該key，則重置value值；如果不存在該key，則将該key插入到到Cache中，若Cache已滿，則淘汰最早進入Cache的資料。

　　舉個例子：假如Cache大小為3，通路資料序列為set(1,1),set(2,2),set(3,3),set(4,4),get(2),set(5,5)

　　則Cache中的資料變化為：

　　(1,1)                               set(1,1)

　　(1,1) (2,2)                       set(2,2)

　　(1,1) (2,2) (3,3)               set(3,3)

　　(2,2) (3,3) (4,4)               set(4,4)

　　(2,2) (3,3) (4,4)               get(2)

　　(3,3) (4,4) (5,5)               set(5,5)

 　　那麼利用什麼資料結構來實作呢？

　　下面提供一種實作思路：

　　利用一個雙向連結清單儲存資料，當來了新的資料之後便添加到連結清單末尾，如果Cache存滿資料，則把連結清單頭部資料删除，然後把新的資料添加到連結清單末尾。在通路資料的時候，如果在Cache中存在該資料的話，則傳回對應的value值；否則傳回-1。如果想提高通路效率，可以利用hashmap來儲存每個key在連結清單中對應的位置。

　　LFU（Least Frequently Used）最近最少使用算法。它是基于“如果一個資料在最近一段時間内使用次數很少，那麼在将來一段時間内被使用的可能性也很小”的思路。

　　注意LFU和LRU算法的不同之處，LRU的淘汰規則是基于通路時間，而LFU是基于通路次數的。舉個簡單的例子：

　　假設緩存大小為3，資料通路序列為set(2,2),set(1,1),get(2),get(1),get(2),set(3,3),set(4,4)，

　　則在set(4,4)時對于LFU算法應該淘汰(3,3)，而LRU應該淘汰(1,1)。

　　那麼LFU Cache應該支援的操作為：

　　set(key,value)：如果Cache中存在該key，則重置value值；如果不存在該key，則将該key插入到到Cache中，若Cache已滿，則淘汰最少通路的資料。

　　為了能夠淘汰最少使用的資料，是以LFU算法最簡單的一種設計思路就是 利用一個數組存儲 資料項，用hashmap存儲每個資料項在數組中對應的位置，然後為每個資料項設計一個通路頻次，當資料項被命中時，通路頻次自增，在淘汰的時候淘汰通路頻次最少的資料。這樣一來的話，在插入資料和通路資料的時候都能達到O(1)的時間複雜度，在淘汰資料的時候，通過選擇算法得到應該淘汰的資料項在數組中的索引，并将該索引位置的内容替換為新來的資料内容即可，這樣的話，淘汰資料的操作時間複雜度為O(n)。

　　另外還有一種實作思路就是利用 小頂堆+hashmap，小頂堆插入、删除操作都能達到O(logn)時間複雜度，是以效率相比第一種實作方法更加高效。

　　如果哪位朋友有更高效的實作方式（比如O(1)時間複雜度），不妨探讨一下，不勝感激。

　　LRU算法的原理以及實作在前一篇博文中已經談到，在此不進行贅述：

本文轉載自海 子部落格園部落格，原文連結：http://www.cnblogs.com/dolphin0520/p/3749259.html如需轉載自行聯系原作者