在C#中實現(xiàn)LRU緩存，你學(xué)會了嗎？
引言
LRU（比較少用）緩存是一種數(shù)據(jù)結(jié)構(gòu)，它存儲有限數(shù)量的項目，并在緩存達(dá)到容量限制時優(yōu)先移除最近最少使用的項目。本文介紹了如何在C#中使用字典和雙向鏈表相結(jié)合實現(xiàn)LRU緩存。
實現(xiàn)細(xì)節(jié)
LRUCache類使用字典來實現(xiàn)Get和Put操作的O(1)時間復(fù)雜度，并使用雙向鏈表來維護(hù)緩存項的使用順序。
以下是實現(xiàn)LRU緩存的兩種方法：
手動雙向鏈表
在LRU緩存中，手動雙向鏈表用于維護(hù)緩存項的使用順序。當(dāng)通過Get方法訪問某個項目或通過Put方法添加/更新項目時，該項目會被移動到鏈表的末尾。這確保了最近使用的項目始終位于鏈表末尾，最近最少使用的項目位于鏈表開頭，當(dāng)需要移除項目時，首先移除這些項目。
public class LRUCache
{
int Capacity;
IDictionary<int, LRUNode> keyValuePairs;
LRUNode head;
LRUNode tail;
public LRUCache(int capacity)
{
Capacity = capacity;
keyValuePairs = new Dictionary<int, LRUNode>();
head = new LRUNode(0, 0);
tail = new LRUNode(0, 0);
head.next = tail;
tail.prev = head;
}
private void MoveToTail(LRUNode node)
{
RemoveNode(node);
AddToTail(node);
}
private void RemoveNode(LRUNode node)
{
node.next.prev = node.prev;
node.prev.next = node.next;
}
private void AddToTail(LRUNode node)
{
node.next = tail;
node.prev = tail.prev;
tail.prev.next = node;
tail.prev = node;
}
public int Get(int key)
{
if (keyValuePairs.TryGetValue(key, out LRUNode node))
{
MoveToTail(node);
return node.value;
}
return -1;
}
public void Put(int key, int value)
{
if (!keyValuePairs.TryGetValue(key, out LRUNode node))
{
if (keyValuePairs.Count == Capacity)
{
LRUNode lru = head.next;
RemoveNode(lru);
keyValuePairs.Remove(lru.key);
}
LRUNode newNode = new LRUNode(key, value);
keyValuePairs[key] = newNode;
AddToTail(newNode);
}
else
{
node.value = value;
MoveToTail(node);
}
}
}
public class LRUNode
{
public int key;
public int value;
public LRUNode prev;
public LRUNode next;
public LRUNode(int key, int value)
{
this.key = key;
this.value = value;
}
}手動雙向鏈表是實現(xiàn)LRU緩存的一種強(qiáng)大技術(shù)，它提供了高效、可控的緩存項管理。通過手動處理節(jié)點及其連接，此方法可確保緩存操作的最佳性能，適用于需要緩存的高性能應(yīng)用程序。
C#中的內(nèi)置鏈表
LRUCacheDLL類使用字典和內(nèi)置的雙向鏈表來實現(xiàn)LRU緩存。這種方法確保Get和Put操作的時間復(fù)雜度為O(1)。
類成員
- capacity：定義緩存最多能存儲的項目數(shù)量。
- keyValuePairs：一個字典，將鍵映射到鏈表中的對應(yīng)節(jié)點，允許O(1)時間復(fù)雜度的節(jié)點訪問。
- dll：一個雙向鏈表，維護(hù)緩存項的使用順序。最近使用的項目位于鏈表末尾，最近最少使用的項目位于鏈表開頭。
構(gòu)造函數(shù)
public LRUCacheDLL(int capacity)
{
this.capacity = capacity;
keyValuePairs = new Dictionary<int, LinkedListNode<(int key, int value)>>();
dll = new LinkedList<(int key, int value)>();
}Get方法
public int Get(int key)
{
if (keyValuePairs.TryGetValue(key, out LinkedListNode<(int key, int value)> node))
{
dll.Remove(node);
dll.AddLast(node);
return node.Value.value;
}
return -1;
}Put方法
public void Put(int key, int value)
{
if (keyValuePairs.TryGetValue(key, out LinkedListNode<(int key, int value)> node))
{
dll.Remove(node);
node.Value = (key, value);
dll.AddLast(node);
}
else
{
if (keyValuePairs.Count == capacity)
{
keyValuePairs.Remove(dll.First.Value.key);
dll.RemoveFirst();
}
keyValuePairs[key] = dll.AddLast((key, value));
}
}LRUCacheDLL類通過結(jié)合字典和雙向鏈表高效管理固定大小的緩存。這種實現(xiàn)確保Get和Put操作的時間復(fù)雜度為O(1)，非常適合高性能應(yīng)用。
時間復(fù)雜度
- Get操作：O(1)
- Put操作：O(1)
空間復(fù)雜度
- O(n)，其中n是緩存的容量。
使用示例
LRUCache cache = new LRUCache(2);
cache.Put(1, 1);
cache.Put(2, 2);
Console.WriteLine("Get key 1: " + cache.Get(1));
cache.Put(3, 3);
Console.WriteLine("Get key 2: " + cache.Get(2));
cache.Put(4, 4);
Console.WriteLine("Get key 1: " + cache.Get(1));
Console.WriteLine("Get key 3: " + cache.Get(3));
Console.WriteLine("Get key 4: " + cache.Get(4));輸出
圖片
在此示例中，緩存初始化為容量2，存儲鍵值對，并在超過容量時移除最近最少使用的項目。
結(jié)語
LRUCache類通過結(jié)合字典和雙向鏈表高效管理固定大小的緩存，實現(xiàn)了Get和Put操作的O(1)時間復(fù)雜度，適用于高性能應(yīng)用程序。
譯文地址：c-sharpcorner.com/article/implementing-an-lru-cache-in-c-sharp/
作者：Rajiv Singh
