在C#中實(shí)現(xiàn)LRU緩存，你學(xué)會(huì)了嗎？
引言
LRU（比較少用）緩存是一種數(shù)據(jù)結(jié)構(gòu)，它存儲(chǔ)有限數(shù)量的項(xiàng)目，并在緩存達(dá)到容量限制時(shí)優(yōu)先移除最近最少使用的項(xiàng)目。本文介紹了如何在C#中使用字典和雙向鏈表相結(jié)合實(shí)現(xiàn)LRU緩存。
實(shí)現(xiàn)細(xì)節(jié)
LRUCache類使用字典來(lái)實(shí)現(xiàn)Get和Put操作的O(1)時(shí)間復(fù)雜度，并使用雙向鏈表來(lái)維護(hù)緩存項(xiàng)的使用順序。
以下是實(shí)現(xiàn)LRU緩存的兩種方法：
手動(dòng)雙向鏈表
在LRU緩存中，手動(dòng)雙向鏈表用于維護(hù)緩存項(xiàng)的使用順序。當(dāng)通過(guò)Get方法訪問(wèn)某個(gè)項(xiàng)目或通過(guò)Put方法添加/更新項(xiàng)目時(shí)，該項(xiàng)目會(huì)被移動(dòng)到鏈表的末尾。這確保了最近使用的項(xiàng)目始終位于鏈表末尾，最近最少使用的項(xiàng)目位于鏈表開(kāi)頭，當(dāng)需要移除項(xiàng)目時(shí)，首先移除這些項(xià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;
}
}手動(dòng)雙向鏈表是實(shí)現(xiàn)LRU緩存的一種強(qiáng)大技術(shù)，它提供了高效、可控的緩存項(xiàng)管理。通過(guò)手動(dòng)處理節(jié)點(diǎn)及其連接，此方法可確保緩存操作的最佳性能，適用于需要緩存的高性能應(yīng)用程序。
C#中的內(nèi)置鏈表
LRUCacheDLL類使用字典和內(nèi)置的雙向鏈表來(lái)實(shí)現(xiàn)LRU緩存。這種方法確保Get和Put操作的時(shí)間復(fù)雜度為O(1)。
類成員
- capacity：定義緩存最多能存儲(chǔ)的項(xiàng)目數(shù)量。
- keyValuePairs：一個(gè)字典，將鍵映射到鏈表中的對(duì)應(yīng)節(jié)點(diǎn)，允許O(1)時(shí)間復(fù)雜度的節(jié)點(diǎn)訪問(wèn)。
- dll：一個(gè)雙向鏈表，維護(hù)緩存項(xiàng)的使用順序。最近使用的項(xiàng)目位于鏈表末尾，最近最少使用的項(xiàng)目位于鏈表開(kāi)頭。
構(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類通過(guò)結(jié)合字典和雙向鏈表高效管理固定大小的緩存。這種實(shí)現(xiàn)確保Get和Put操作的時(shí)間復(fù)雜度為O(1)，非常適合高性能應(yīng)用。
時(shí)間復(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，存儲(chǔ)鍵值對(duì)，并在超過(guò)容量時(shí)移除最近最少使用的項(xiàng)目。
結(jié)語(yǔ)
LRUCache類通過(guò)結(jié)合字典和雙向鏈表高效管理固定大小的緩存，實(shí)現(xiàn)了Get和Put操作的O(1)時(shí)間復(fù)雜度，適用于高性能應(yīng)用程序。
譯文地址：c-sharpcorner.com/article/implementing-an-lru-cache-in-c-sharp/
作者：Rajiv Singh
