lru和lfu算法有什么區別

這篇文章將為大家詳細講解有關lru和lfu算法有什么區別，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

區別：LRU是最近最少使用頁面置換算法，淘汰最長時間未被使用的頁面；而LFU是最近最不常用頁面置換算法，淘汰一定時期內被訪問次數最少的頁。LRU關鍵是看頁面最后一次被使用到發生調度的時間長短；而LFU關鍵是看一定時間段內頁面被使用的頻率。

常見的緩存算法

• LRU (Least recently used) 最近最少使用，如果數據最近被訪問過，那么將來被訪問的幾率也更高。

• LFU (Least frequently used) 最不經常使用，如果一個數據在最近一段時間內使用次數很少，那么在將來一段時間內被使用的可能性也很小。

• FIFO (Fist in first out) 先進先出， 如果一個數據最先進入緩存中，則應該最早淘汰掉。

LRU緩存

像瀏覽器的緩存策略、memcached的緩存策略都是使用LRU這個算法，LRU算法會將近期最不會訪問的數據淘汰掉。LRU如此流行的原因是實現比較簡單，而且對于實際問題也很實用，良好的運行時性能，命中率較高。下面談談如何實現LRU緩存：

• 新數據插入到鏈表頭部

• 每當緩存命中（即緩存數據被訪問），則將數據移到鏈表頭部

• 當鏈表滿的時候，將鏈表尾部的數據丟棄

LRU Cache具備的操作：

• set(key,value)：如果key在hashmap中存在，則先重置對應的value值，然后獲取對應的節點cur，將cur節點從鏈表刪除，并移動到鏈表的頭部；若果key在hashmap不存在，則新建一個節點，并將節點放到鏈表的頭部。當Cache存滿的時候，將鏈表最后一個節點刪除即可。

• get(key)：如果key在hashmap中存在，則把對應的節點放到鏈表頭部，并返回對應的value值；如果不存在，則返回-1。

LRU和LFU的區別：

LRU是最近最少使用頁面置換算法(Least Recently Used),也就是首先淘汰最長時間未被使用的頁面！

LFU是最近最不常用頁面置換算法(Least Frequently Used),也就是淘汰一定時期內被訪問次數最少的頁！

比如,第二種方法的時期T為10分鐘,如果每分鐘進行一次調頁,主存塊為3,若所需頁面走向為2 1 2 1 2 3 4

注意,當調頁面4時會發生缺頁中斷

若按LRU算法,應換頁面1(1頁面最久未被使用) 但按LFU算法應換頁面3(十分鐘內,頁面3只使用了一次)

關于lru和lfu算法有什么區別就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。