LRU緩存替換策略及C#實(shí)現(xiàn)方法分享
LRU緩存替換策略
緩存是一種非常常見(jiàn)的設(shè)計(jì)，通過(guò)將數(shù)據(jù)緩存到訪問(wèn)速度更快的存儲(chǔ)設(shè)備中，來(lái)提高數(shù)據(jù)的訪問(wèn)速度，如內(nèi)存、CPU緩存、硬盤(pán)緩存等。
但與緩存的高速相對(duì)的是，緩存的成本較高，因此容量往往是有限的，當(dāng)緩存滿了之后，就需要一種策略來(lái)決定將哪些數(shù)據(jù)移除出緩存，以騰出空間來(lái)存儲(chǔ)新的數(shù)據(jù)。
這樣的策略被稱(chēng)為緩存替換策略（Cache Replacement Policy）。
常見(jiàn)的緩存替換策略有：FIFO（First In First Out）、LRU（Least Recently Used）、LFU（Least Frequently Used）等。
今天給大家介紹的是LRU算法。
核心思想
LRU算法基于這樣一個(gè)假設(shè)：如果數(shù)據(jù)最近被訪問(wèn)過(guò)，那么將來(lái)被訪問(wèn)的幾率也更高。
大部分情況下這個(gè)假設(shè)是成立的，因此LRU算法也是比較常用的緩存替換策略。
基于這個(gè)假設(shè)，我們?cè)趯?shí)現(xiàn)的時(shí)候，需要維護(hù)一個(gè)有序的數(shù)據(jù)結(jié)構(gòu)，來(lái)記錄數(shù)據(jù)的訪問(wèn)歷史，當(dāng)緩存滿了之后，就可以根據(jù)這個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)決定將哪些數(shù)據(jù)移除出緩存。
不適用場(chǎng)景
但如果數(shù)據(jù)的訪問(wèn)模式不符合LRU算法的假設(shè)，那么LRU算法就會(huì)失效。
例如：數(shù)據(jù)的訪問(wèn)模式是周期性的，那么LRU算法就會(huì)把周期性的數(shù)據(jù)淘汰掉，這樣就會(huì)導(dǎo)致緩存命中率的下降。
換個(gè)說(shuō)法比如，如果現(xiàn)在緩存的數(shù)據(jù)只在白天被訪問(wèn)，晚上訪問(wèn)的是另一批數(shù)據(jù)，那么在晚上，LRU算法就會(huì)把白天訪問(wèn)的數(shù)據(jù)淘汰掉，第二天白天又會(huì)把昨天晚上訪問(wèn)的數(shù)據(jù)淘汰掉，這樣就會(huì)導(dǎo)致緩存命中率的下降。
后面有時(shí)間會(huì)給大家介紹LFU（Least Frequently Used）算法，以及LFU和LRU的結(jié)合LFRU（Least Frequently and Recently Used）算法，可以有效的解決這個(gè)問(wèn)題。
算法基本實(shí)現(xiàn)
上文提到，LRU算法需要維護(hù)一個(gè)有序的數(shù)據(jù)結(jié)構(gòu)，來(lái)記錄數(shù)據(jù)的訪問(wèn)歷史。通常我們會(huì)用雙向鏈表來(lái)實(shí)現(xiàn)這個(gè)數(shù)據(jù)結(jié)構(gòu)，因?yàn)殡p向鏈表可以在O(1)的時(shí)間復(fù)雜度內(nèi)往鏈表的頭部或者尾部插入數(shù)據(jù)，以及在O(1)的時(shí)間復(fù)雜度內(nèi)刪除數(shù)據(jù)。
我們將數(shù)據(jù)存儲(chǔ)在雙向鏈表中，每次訪問(wèn)數(shù)據(jù)的時(shí)候，就將數(shù)據(jù)移動(dòng)到鏈表的尾部，這樣就可以保證鏈表的尾部就是最近訪問(wèn)的數(shù)據(jù)，鏈表的頭部就是最久沒(méi)有被訪問(wèn)的數(shù)據(jù)。
當(dāng)緩存滿了之后，如果需要插入新的數(shù)據(jù)，因?yàn)殒湵淼念^部就是最久沒(méi)有被訪問(wèn)的數(shù)據(jù)，所以我們就可以直接將鏈表的頭部刪除，然后將新的數(shù)據(jù)插入到鏈表的尾部。
如果我們要實(shí)現(xiàn)一個(gè)鍵值對(duì)的緩存，我們可以用一個(gè)哈希表來(lái)存儲(chǔ)鍵值對(duì)，這樣就可以在O(1)的時(shí)間復(fù)雜度內(nèi)完成查找操作，.NET 中我們可以使用 Dictionary。
同時(shí)我們使用 LinkedList 來(lái)作為雙向鏈表的實(shí)現(xiàn)，存儲(chǔ)緩存的 key，以此記錄數(shù)據(jù)的訪問(wèn)歷史。
我們?cè)诿看尾僮?Dictionary 進(jìn)行插入、刪除、查找的時(shí)候，都需要將對(duì)應(yīng)的 key 也插入、刪除、移動(dòng)到鏈表的尾部。
// 實(shí)現(xiàn) IEnumerable 接口，方便遍歷
public class LRUCache<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
{
private readonly LinkedList<TKey> _list;
private readonly Dictionary<TKey, TValue> _dictionary;
private readonly int _capacity;
public LRUCache(int capacity)
{
_capacity = capacity;
_list = new LinkedList<TKey>();
_dictionary = new Dictionary<TKey, TValue>();
}
public TValue Get(TKey key)
{
if (_dictionary.TryGetValue(key, out var value))
{
// 在鏈表中刪除 key，然后將 key 添加到鏈表的尾部
// 這樣就可以保證鏈表的尾部就是最近訪問(wèn)的數(shù)據(jù)，鏈表的頭部就是最久沒(méi)有被訪問(wèn)的數(shù)據(jù)
// 但是在鏈表中刪除 key 的時(shí)間復(fù)雜度是 O(n)，所以這個(gè)算法的時(shí)間復(fù)雜度是 O(n)
_list.Remove(key);
_list.AddLast(key);
return value;
}
return default;
}
public void Put(TKey key, TValue value)
{
if (_dictionary.TryGetValue(key, out _))
{
// 如果插入的 key 已經(jīng)存在，將 key 對(duì)應(yīng)的值更新，然后將 key 移動(dòng)到鏈表的尾部
_dictionary[key] = value;
_list.Remove(key);
_list.AddLast(key);
}
else
{
if (_list.Count == _capacity)
{
// 緩存滿了，刪除鏈表的頭部，也就是最久沒(méi)有被訪問(wèn)的數(shù)據(jù)
_dictionary.Remove(_list.First.Value);
_list.RemoveFirst();
}
_list.AddLast(key);
_dictionary.Add(key, value);
}
}
public void Remove(TKey key)
{
if (_dictionary.TryGetValue(key, out _))
{
_dictionary.Remove(key);
_list.Remove(key);
}
}
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
foreach (var key in _list)
{
yield return new KeyValuePair<TKey, TValue>(key, _dictionary[key]);
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}var lruCache = new LRUCache<int, int>(4);
lruCache.Put(1, 1);
lruCache.Put(2, 2);
lruCache.Put(3, 3);
lruCache.Put(4, 4);
Console.WriteLine(string.Join(" ", lruCache));
Console.WriteLine(lruCache.Get(2));
Console.WriteLine(string.Join(" ", lruCache));
lruCache.Put(5, 5);
Console.WriteLine(string.Join(" ", lruCache));
lruCache.Remove(3);
Console.WriteLine(string.Join(" ", lruCache));輸出：
[1, 1] [2, 2] [3, 3] [4, 4] // 初始化 2 // 訪問(wèn) 2 [1, 1] [3, 3] [4, 4] [2, 2] // 2 移動(dòng)到鏈表尾部 [3, 3] [4, 4] [2, 2] [5, 5] // 插入 5 [4, 4] [2, 2] [5, 5] // 刪除 3
算法優(yōu)化
上面的實(shí)現(xiàn)中，對(duì)緩存的查詢(xún)、插入、刪除都會(huì)涉及到鏈表中數(shù)據(jù)的刪除（移動(dòng)也是刪除再插入）。
因?yàn)槲覀冊(cè)?LinkedList 中存儲(chǔ)的是 key，所以我們需要先通過(guò) key 在鏈表中找到對(duì)應(yīng)的節(jié)點(diǎn)，然后再進(jìn)行刪除操作，這就導(dǎo)致了鏈表的刪除操作的時(shí)間復(fù)雜度是 O(n)。
雖然 Dictionary 的查找、插入、刪除操作的時(shí)間復(fù)雜度都是 O(1)，但因?yàn)殒湵聿僮鞯臅r(shí)間復(fù)雜度是 O(n)，整個(gè)算法的最差時(shí)間復(fù)雜度是 O(n)。
算法優(yōu)化的關(guān)鍵在于如何降低鏈表的刪除操作的時(shí)間復(fù)雜度。
優(yōu)化思路：
在 Dictionary 中存儲(chǔ) key 和 LinkedList 中節(jié)點(diǎn)的映射關(guān)系 在 LinkedList 的節(jié)點(diǎn)中存儲(chǔ) key-value
也就是說(shuō)，我們讓兩個(gè)本來(lái)不相關(guān)的數(shù)據(jù)結(jié)構(gòu)之間產(chǎn)生聯(lián)系。
不管是在插入、刪除、查找緩存的時(shí)候，都可以通過(guò)這種聯(lián)系來(lái)將時(shí)間復(fù)雜度降低到 O(1)。
通過(guò) key 在 Dictionary 中找到對(duì)應(yīng)的節(jié)點(diǎn)，然后再?gòu)?LinkedList 節(jié)點(diǎn)中取出 value，時(shí)間復(fù)雜度是 O(1) LinkedList 刪除數(shù)據(jù)之前，先通過(guò) key 在 Dictionary 中找到對(duì)應(yīng)的節(jié)點(diǎn)，然后再刪除，這樣就可以將鏈表的刪除操作的時(shí)間復(fù)雜度降低到 O(1) LinkedList 刪除頭部節(jié)點(diǎn)時(shí)，因?yàn)楣?jié)點(diǎn)中存儲(chǔ)了 key，所以我們可以通過(guò) key 在 Dictionary 中刪除對(duì)應(yīng)的節(jié)點(diǎn)，時(shí)間復(fù)雜度是 O(1)
public class LRUCache_V2<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
{
private readonly LinkedList<KeyValuePair<TKey, TValue>> _list;
private readonly Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> _dictionary;
private readonly int _capacity;
public LRUCache_V2(int capacity)
{
_capacity = capacity;
_list = new LinkedList<KeyValuePair<TKey, TValue>>();
_dictionary = new Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>();
}
public TValue Get(TKey key)
{
if (_dictionary.TryGetValue(key, out var node))
{
_list.Remove(node);
_list.AddLast(node);
return node.Value.Value;
}
return default;
}
public void Put(TKey key, TValue value)
{
if (_dictionary.TryGetValue(key, out var node))
{
node.Value = new KeyValuePair<TKey, TValue>(key, value);
_list.Remove(node);
_list.AddLast(node);
}
else
{
if (_list.Count == _capacity)
{
_dictionary.Remove(_list.First.Value.Key);
_list.RemoveFirst();
}
var newNode = new LinkedListNode<KeyValuePair<TKey, TValue>>(new KeyValuePair<TKey, TValue>(key, value));
_list.AddLast(newNode);
_dictionary.Add(key, newNode);
}
}
public void Remove(TKey key)
{
if (_dictionary.TryGetValue(key, out var node))
{
_dictionary.Remove(key);
_list.Remove(node);
}
}
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
return _list.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}進(jìn)一步優(yōu)化
因?yàn)槲覀儗?duì) 雙向鏈表 的存儲(chǔ)需求是定制化的，要求節(jié)點(diǎn)中存儲(chǔ) key-value，直接使用 C# 的 LinkedList 我們就需要用 KeyValuePair 這樣的結(jié)構(gòu)來(lái)間接存儲(chǔ)，會(huì)導(dǎo)致一些不必要的內(nèi)存開(kāi)銷(xiāo)。
我們可以自己實(shí)現(xiàn)一個(gè)雙向鏈表，這樣就可以直接在節(jié)點(diǎn)中存儲(chǔ) key-value，從而減少內(nèi)存開(kāi)銷(xiāo)。
public class LRUCache_V3<TKey, TValue>
{
private readonly DoubleLinkedListNode<TKey, TValue> _head;
private readonly DoubleLinkedListNode<TKey, TValue> _tail;
private readonly Dictionary<TKey, DoubleLinkedListNode<TKey, TValue>> _dictionary;
private readonly int _capacity;
public LRUCache_V3(int capacity)
{
_capacity = capacity;
_head = new DoubleLinkedListNode<TKey, TValue>();
_tail = new DoubleLinkedListNode<TKey, TValue>();
_head.Next = _tail;
_tail.Previous = _head;
_dictionary = new Dictionary<TKey, DoubleLinkedListNode<TKey, TValue>>();
}
public TValue Get(TKey key)
{
if (_dictionary.TryGetValue(key, out var node))
{
RemoveNode(node);
AddLastNode(node);
return node.Value;
}
return default;
}
public void Put(TKey key, TValue value)
{
if (_dictionary.TryGetValue(key, out var node))
{
RemoveNode(node);
AddLastNode(node);
node.Value = value;
}
else
{
if (_dictionary.Count == _capacity)
{
var firstNode = RemoveFirstNode();
_dictionary.Remove(firstNode.Key);
}
var newNode = new DoubleLinkedListNode<TKey, TValue>(key, value);
AddLastNode(newNode);
_dictionary.Add(key, newNode);
}
}
public void Remove(TKey key)
{
if (_dictionary.TryGetValue(key, out var node))
{
_dictionary.Remove(key);
RemoveNode(node);
}
}
private void AddLastNode(DoubleLinkedListNode<TKey, TValue> node)
{
node.Previous = _tail.Previous;
node.Next = _tail;
_tail.Previous.Next = node;
_tail.Previous = node;
}
private DoubleLinkedListNode<TKey, TValue> RemoveFirstNode()
{
var firstNode = _head.Next;
_head.Next = firstNode.Next;
firstNode.Next.Previous = _head;
firstNode.Next = null;
firstNode.Previous = null;
return firstNode;
}
private void RemoveNode(DoubleLinkedListNode<TKey, TValue> node)
{
node.Previous.Next = node.Next;
node.Next.Previous = node.Previous;
node.Next = null;
node.Previous = null;
}
internal class DoubleLinkedListNode<TKey, TValue>
{
public DoubleLinkedListNode()
{
}
public DoubleLinkedListNode(TKey key, TValue value)
{
Key = key;
Value = value;
}
public TKey Key { get; set; }
public TValue Value { get; set; }
public DoubleLinkedListNode<TKey, TValue> Previous { get; set; }
public DoubleLinkedListNode<TKey, TValue> Next { get; set; }
}
}Benchmark
使用 BenchmarkDotNet 對(duì)3個(gè)版本進(jìn)行性能測(cè)試對(duì)比。
[MemoryDiagnoser]
public class WriteBenchmarks
{
// 保證寫(xiě)入的數(shù)據(jù)有一定的重復(fù)性，借此來(lái)測(cè)試LRU的最差時(shí)間復(fù)雜度
private const int Capacity = 1000;
private const int DataSize = 10_0000;
private List<int> _data;
[GlobalSetup]
public void Setup()
{
_data = new List<int>();
var shared = Random.Shared;
for (int i = 0; i < DataSize; i++)
{
_data.Add(shared.Next(0, DataSize / 10));
}
}
[Benchmark]
public void LRUCache_V1()
{
var cache = new LRUCache<int, int>(Capacity);
foreach (var item in _data)
{
cache.Put(item, item);
}
}
[Benchmark]
public void LRUCache_V2()
{
var cache = new LRUCache_V2<int, int>(Capacity);
foreach (var item in _data)
{
cache.Put(item, item);
}
}
[Benchmark]
public void LRUCache_V3()
{
var cache = new LRUCache_V3<int, int>(Capacity);
foreach (var item in _data)
{
cache.Put(item, item);
}
}
}
public class ReadBenchmarks
{
// 保證寫(xiě)入的數(shù)據(jù)有一定的重復(fù)性，借此來(lái)測(cè)試LRU的最差時(shí)間復(fù)雜度
private const int Capacity = 1000;
private const int DataSize = 10_0000;
private List<int> _data;
private LRUCache<int, int> _cacheV1;
private LRUCache_V2<int, int> _cacheV2;
private LRUCache_V3<int, int> _cacheV3;
[GlobalSetup]
public void Setup()
{
_cacheV1 = new LRUCache<int, int>(Capacity);
_cacheV2 = new LRUCache_V2<int, int>(Capacity);
_cacheV3 = new LRUCache_V3<int, int>(Capacity);
_data = new List<int>();
var shared = Random.Shared;
for (int i = 0; i < DataSize; i++)
{
int dataToPut = shared.Next(0, DataSize / 10);
int dataToGet = shared.Next(0, DataSize / 10);
_data.Add(dataToGet);
_cacheV1.Put(dataToPut, dataToPut);
_cacheV2.Put(dataToPut, dataToPut);
_cacheV3.Put(dataToPut, dataToPut);
}
}
[Benchmark]
public void LRUCache_V1()
{
foreach (var item in _data)
{
_cacheV1.Get(item);
}
}
[Benchmark]
public void LRUCache_V2()
{
foreach (var item in _data)
{
_cacheV2.Get(item);
}
}
[Benchmark]
public void LRUCache_V3()
{
foreach (var item in _data)
{
_cacheV3.Get(item);
}
}
}寫(xiě)入性能測(cè)試結(jié)果：
| Method | Mean | Error | StdDev | Median | Gen0 | Gen1 | Allocated | |------------ |----------:|----------:|----------:|----------:|---------:|---------:|----------:| | LRUCache_V1 | 16.890 ms | 0.3344 ms | 0.8012 ms | 16.751 ms | 750.0000 | 218.7500 | 4.65 MB | | LRUCache_V2 | 7.193 ms | 0.1395 ms | 0.3958 ms | 7.063 ms | 703.1250 | 226.5625 | 4.22 MB | | LRUCache_V3 | 5.761 ms | 0.1102 ms | 0.1132 ms | 5.742 ms | 585.9375 | 187.5000 | 3.53 MB |
查詢(xún)性能測(cè)試結(jié)果：
| Method | Mean | Error | StdDev | Gen0 | Allocated | |------------ |----------:|----------:|----------:|--------:|----------:| | LRUCache_V1 | 19.475 ms | 0.3824 ms | 0.3390 ms | 62.5000 | 474462 B | | LRUCache_V2 | 1.994 ms | 0.0273 ms | 0.0242 ms | - | 4 B | | LRUCache_V3 | 1.595 ms | 0.0187 ms | 0.0175 ms | - | 3 B |
本文詳細(xì)介紹了LRU緩存替換策略的原理和實(shí)現(xiàn)方法，包括使用哈希表和雙向鏈表來(lái)實(shí)現(xiàn)LRU緩存。通過(guò)實(shí)現(xiàn)LRU緩存，可以有效地提高程序的性能和響應(yīng)速度。同時(shí)，本文還介紹了C#語(yǔ)言中實(shí)現(xiàn)LRU緩存的具體步驟和代碼實(shí)現(xiàn)。通過(guò)本文的學(xué)習(xí)，讀者可以深入了解LRU緩存替換策略，并掌握C#語(yǔ)言中實(shí)現(xiàn)LRU緩存的方法。
到此這篇關(guān)于LRU緩存替換策略及C#實(shí)現(xiàn)方法分享的文章就介紹到這了,更多相關(guān)LRU緩存替換策略?xún)?nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C#在DataTable中根據(jù)條件刪除某一行的實(shí)現(xiàn)方法
我們通常的方法是把數(shù)據(jù)源放在DataTable里面，但是偶爾也會(huì)需要把不要的行移除，怎么實(shí)現(xiàn)呢，下面通過(guò)代碼給大家介紹c# atatable 刪除行的方法，需要的朋友一起看下吧2016-05-05
這篇文章主要介紹了使用winapi安裝Windows服務(wù)示例,大家參考使用吧2014-01-01
C#調(diào)用百度地圖API根據(jù)地名獲取經(jīng)緯度geocoding
本文主要介紹了C#調(diào)用百度地圖API根據(jù)地名獲取經(jīng)緯度geocoding，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-04-04
C#中調(diào)用命令行cmd開(kāi)啟wifi熱點(diǎn)的實(shí)例代碼
最近想在win7上開(kāi)啟wifi熱點(diǎn)，于是就弄出下面這個(gè)小東西，里面涉及如何在控制臺(tái)上輸入命令，分享一下。首先在VS中創(chuàng)建一個(gè)window窗口，然后創(chuàng)建兩個(gè)四個(gè)button，兩個(gè)輸入框2013-04-04
C#實(shí)現(xiàn)簡(jiǎn)單的RSA非對(duì)稱(chēng)加密算法示例
這篇文章主要介紹了C#實(shí)現(xiàn)簡(jiǎn)單的RSA非對(duì)稱(chēng)加密算法,結(jié)合實(shí)例形式分析了C#實(shí)現(xiàn)RSA加密的具體步驟與相關(guān)操作技巧,需要的朋友可以參考下2017-08-08
這篇文章主要介紹了c# 實(shí)現(xiàn)KMP算法的示例代碼，幫助大家更好的理解和使用c#，感興趣的朋友可以了解下2020-11-11
ListView用法中與滾動(dòng)相關(guān)的需求實(shí)現(xiàn)
這篇文章主要介紹了ListView用法中與滾動(dòng)相關(guān)的需求實(shí)現(xiàn)，獲取并設(shè)置ListView的滾動(dòng)位置，以及獲取滾動(dòng)位置處的項(xiàng)目，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-06-06
C#反射調(diào)用拓展類(lèi)方法實(shí)例代碼
這篇文章主要給大家介紹了關(guān)于C#反射調(diào)用拓展類(lèi)方法的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2022-01-01
C#實(shí)現(xiàn)動(dòng)態(tài)生成表格的方法
這篇文章主要介紹了C#實(shí)現(xiàn)動(dòng)態(tài)生成表格的方法,是C#程序設(shè)計(jì)中非常實(shí)用的技巧,需要的朋友可以參考下2014-09-09
詳解如何獲取C#類(lèi)中發(fā)生數(shù)據(jù)變化的屬性信息
這篇文章主要介紹了詳解如何獲取C#類(lèi)中發(fā)生數(shù)據(jù)變化的屬性信息，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-05-05