LRU快取淘汰演算法(連結串列)
LRU(Least recently used)最近最少使用策略演算法:
是根據資料的歷史訪問記錄(按時間排序)來進行淘汰資料的,理念:如果一個數據在最近沒有被訪問過,那麼將來被訪問的可能性也很小,當快取空間已滿的時候,如果有新的快取資料進來,將會刪除時間最早的那條資料;
1.一個空的快取連結串列長度為5,依次進入
E => D => C => B => A
2.當ABCDE這5個節點中任何一個需要新增到快取連結串列中,先查詢連結串列中有沒有這個值,如果存在,將該節點刪除,並重新新增到表頭;
B => E => D => C => A
3.連結串列中插入新一個數據,先遍歷原先的資料,是否存在,不不存在將刪除最後一個節點,並將最新的節點放在連結串列的表頭;
A => E => D => C => B
public static void LRU() { //假設連結串列的長度為3 LinkedList<int> l = new LinkedList<int>(); l.Insert(1); l.Insert(2); l.Insert(3); bool isExist = false; Node<int> newNode = new Node<int>(4); Node<int> temp = l.Head; int i = 1; if (newNode.Data != temp.Data) { while (temp.Next != null) { i++; temp = temp.Next; if (temp.Data == newNode.Data)//連結串列中存在資料 { l.Delete(i); l.Insert(newNode.Data,1);//插入到第一個位置 break; } } if (!isExist) { l.Delete(i);//i = 連結串列長度 刪除最先進入連結串列的資料 l.Insert(newNode.Data, 1);//插入到第一個位置 } } }