快取演算法(頁面置換演算法)-FIFO、LFU、LRU
在前一篇文章中透過leetcode的一道題目瞭解了LRU演算法的具體設計思路,下面繼續來探討一下另外兩種常見的Cache演算法:FIFO、LFU
1.FIFO演算法
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在連結串列中對應的位置。
2.LFU演算法
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)。
如果哪位朋友有更高效的實現方式(比如O(1)時間複雜度),不妨探討一下,不勝感激。
3.LRU演算法
LRU演算法的原理以及實現在前一篇博文中已經談到,在此不進行贅述:
http://www.cnblogs.com/dolphin0520/p/3741519.html
參考連結:http://blog.csdn.net/hexinuaa/article/details/6630384
http://blog.csdn.net/beiyetengqing/article/details/7855933
http://outofmemory.cn/wr/?u=http%3A%2F%2Fblog.csdn.net%2Fyunhua_lee%2Farticle%2Fdetails%2F7648549
http://blog.csdn.net/alexander_xfl/article/details/12993565
快取演算法(頁面置換演算法)-FIFO、LFU、LRU
在前一篇文章中透過leetcode的一道題目瞭解了LRU演算法的具體設計思路,下面繼續來探討一下另外兩種常見的Cache演算法:FIFO、LFU
1.FIFO演算法
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在連結串列中對應的位置。
2.LFU演算法
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應該支援的操作為:
get(key):如果Cache中存在該key,則返回對應的value值,否則,返回-1;
set(key,value):如果Cache中存在該key,則重置value值;如果不存在該key,則將該key插入到到Cache中,若Cache已滿,則淘汰最少訪問的資料。
為了能夠淘汰最少使用的資料,因此LFU演算法最簡單的一種設計思路就是 利用一個數組儲存 資料項,用hashmap儲存每個資料項在陣列中對應的位置,然後為每個資料項設計一個訪問頻次,當資料項被命中時,訪問頻次自增,在淘汰的時候淘汰訪問頻次最少的資料。這樣一來的話,在插入資料和訪問資料的時候都能達到O(1)的時間複雜度,在淘汰資料的時候,透過選擇演算法得到應該淘汰的資料項在陣列中的索引,並將該索引位置的內容替換為新來的資料內容即可,這樣的話,淘汰資料的操作時間複雜度為O(n)。
如果哪位朋友有更高效的實現方式(比如O(1)時間複雜度),不妨探討一下,不勝感激。
3.LRU演算法
LRU演算法的原理以及實現在前一篇博文中已經談到,在此不進行贅述:
http://www.cnblogs.com/dolphin0520/p/3741519.html
參考連結:http://blog.csdn.net/hexinuaa/article/details/6630384
http://blog.csdn.net/beiyetengqing/article/details/7855933
http://outofmemory.cn/wr/?u=http%3A%2F%2Fblog.csdn.net%2Fyunhua_lee%2Farticle%2Fdetails%2F7648549
http://blog.csdn.net/alexander_xfl/article/details/12993565