个人中心
文章发布
退出
作者热门文章
- Java锁的逻辑（结合对象头和ObjectMonitor）
- 还在用饼状图？来瞧瞧这些炫酷的百分比可视化新图形（附代码实现）⛵
- 自动注册实体类到EntityFrameworkCore上下文，并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
32
4
缓存是一种非常常见的设计，通过将数据缓存到访问速度更快的存储设备中，来提高数据的访问速度，如内存、CPU缓存、硬盘缓存等.
但与缓存的高速相对的是，缓存的成本较高，因此容量往往是有限的，当缓存满了之后，就需要一种策略来决定将哪些数据移除出缓存，以腾出空间来存储新的数据.
这样的策略被称为缓存替换策略（Cache Replacement Policy）.
常见的缓存替换策略有：FIFO（First In First Out）、LRU（Least Recently Used）、LFU（Least Frequently Used）等.
今天给大家介绍的是LRU算法.
LRU算法基于这样一个假设：如果数据最近被访问过，那么将来被访问的几率也更高.
大部分情况下这个假设是成立的，因此LRU算法也是比较常用的缓存替换策略.
基于这个假设，我们在实现的时候，需要维护一个有序的数据结构，来记录数据的访问历史，当缓存满了之后，就可以根据这个数据结构来决定将哪些数据移除出缓存.
但如果数据的访问模式不符合LRU算法的假设，那么LRU算法就会失效.
例如：数据的访问模式是周期性的，那么LRU算法就会把周期性的数据淘汰掉，这样就会导致缓存命中率的下降.
换个说法比如，如果现在缓存的数据只在白天被访问，晚上访问的是另一批数据，那么在晚上，LRU算法就会把白天访问的数据淘汰掉，第二天白天又会把昨天晚上访问的数据淘汰掉，这样就会导致缓存命中率的下降.
后面有时间会给大家介绍LFU（Least Frequently Used）算法，以及LFU和LRU的结合LFRU（Least Frequently and Recently Used）算法，可以有效的解决这个问题.
上文提到，LRU算法需要维护一个有序的数据结构，来记录数据的访问历史。通常我们会用双向链表来实现这个数据结构，因为双向链表可以在O(1)的时间复杂度内往链表的头部或者尾部插入数据，以及在O(1)的时间复杂度内删除数据.
我们将数据存储在双向链表中，每次访问数据的时候，就将数据移动到链表的尾部，这样就可以保证链表的尾部就是最近访问的数据，链表的头部就是最久没有被访问的数据.
当缓存满了之后，如果需要插入新的数据，因为链表的头部就是最久没有被访问的数据，所以我们就可以直接将链表的头部删除，然后将新的数据插入到链表的尾部.
如果我们要实现一个键值对的缓存，我们可以用一个哈希表来存储键值对，这样就可以在O(1)的时间复杂度内完成查找操作，.NET 中我们可以使用 Dictionary.
同时我们使用 LinkedList 来作为双向链表的实现，存储缓存的 key，以此记录数据的访问历史.
我们在每次操作 Dictionary 进行插入、删除、查找的时候，都需要将对应的 key 也插入、删除、移动到链表的尾部.
// 实现 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 添加到链表的尾部
// 这样就可以保证链表的尾部就是最近访问的数据，链表的头部就是最久没有被访问的数据
// 但是在链表中删除 key 的时间复杂度是 O(n)，所以这个算法的时间复杂度是 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 已经存在，将 key 对应的值更新，然后将 key 移动到链表的尾部
_dictionary[key] = value;
_list.Remove(key);
_list.AddLast(key);
}
else
{
if (_list.Count == _capacity)
{
// 缓存满了，删除链表的头部，也就是最久没有被访问的数据
_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 // 访问 2
[1, 1] [3, 3] [4, 4] [2, 2] // 2 移动到链表尾部
[3, 3] [4, 4] [2, 2] [5, 5] // 插入 5
[4, 4] [2, 2] [5, 5] // 删除 3
上面的实现中，对缓存的查询、插入、删除都会涉及到链表中数据的删除（移动也是删除再插入）.
因为我们在 LinkedList 中存储的是 key，所以我们需要先通过 key 在链表中找到对应的节点，然后再进行删除操作，这就导致了链表的删除操作的时间复杂度是 O(n).
虽然 Dictionary 的查找、插入、删除操作的时间复杂度都是 O(1)，但因为链表操作的时间复杂度是 O(n)，整个算法的最差时间复杂度是 O(n).
算法优化的关键在于如何降低链表的删除操作的时间复杂度.
优化思路:
也就是说，我们让两个本来不相关的数据结构之间产生联系.
不管是在插入、删除、查找缓存的时候，都可以通过这种联系来将时间复杂度降低到 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();
}
}
因为我们对 双向链表 的存储需求是定制化的，要求节点中存储 key-value，直接使用 C# 的 LinkedList 我们就需要用 KeyValuePair 这样的结构来间接存储，会导致一些不必要的内存开销.
我们可以自己实现一个双向链表，这样就可以直接在节点中存储 key-value，从而减少内存开销.
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; }
}
}
使用 BenchmarkDotNet 对3个版本进行性能测试对比.
[MemoryDiagnoser]
public class WriteBenchmarks
{
// 保证写入的数据有一定的重复性，借此来测试LRU的最差时间复杂度
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
{
// 保证写入的数据有一定的重复性，借此来测试LRU的最差时间复杂度
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);
}
}
}
写入性能测试结果:
| 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 |
查询性能测试结果:
| 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 |
最后此篇关于LRU缓存替换策略及C#实现的文章就讲到这里了,如果你想了解更多关于LRU缓存替换策略及C#实现的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
32
4
0
背景: 我最近一直在使用 JPA，我为相当大的关系数据库项目生成持久层的轻松程度给我留下了深刻的印象。 我们公司使用大量非 SQL 数据库，特别是面向列的数据库。我对可能对这些数据库使用 JPA 有一
我已经在我的 maven pom 中添加了这些构建配置，因为我希望将 Apache Solr 依赖项与 Jar 捆绑在一起。否则我得到了 SolarServerException: ClassNotF
interface ITurtle { void Fight(); void EatPizza(); } interface ILeonardo : ITurtle {
我希望可用于 Java 的对象/关系映射 (ORM) 工具之一能够满足这些要求: 使用 JPA 或 native SQL 查询获取大量行并将其作为实体对象返回。 允许在行(实体)中进行迭代，并在对当前
好像没有，因为我有实现From for 的代码, 我可以转换 A到 B与 .into() , 但同样的事情不适用于 Vec .into()一个Vec . 要么我搞砸了阻止实现派生的事情，要么这不应该发
在 C# 中，如果 A 实现 IX 并且 B 继承自 A ，是否必然遵循 B 实现 IX？如果是，是因为 LSP 吗？之间有什么区别吗: 1. Interface IX; Class A : IX;
就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持，但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the
我正在阅读标准haskell库的(^)的实现代码: (^) :: (Num a, Integral b) => a -> b -> a x0 ^ y0 | y0 a -> b ->a expo x0
我将把国际象棋游戏表示为 C++ 结构。我认为，最好的选择是树结构(因为在每个深度我们都有几个可能的移动)。 这是一个好的方法吗？ struct TreeElement{ SomeMoveType
我正在为用户名数据库实现字符串匹配算法。我的方法采用现有的用户名数据库和用户想要的新用户名，然后检查用户名是否已被占用。如果采用该方法，则该方法应该返回带有数据库中未采用的数字的用户名。 例子: “贾
我正在尝试实现 Breadth-first search algorithm , 为了找到两个顶点之间的最短距离。我开发了一个 Queue 对象来保存和检索对象，并且我有一个二维数组来保存两个给定顶点
我目前正在 ika 中开发我的 Python 游戏，它使用 python 2.5 我决定为 AI 使用 A* 寻路。然而，我发现它对我的需要来说太慢了(3-4 个敌人可能会落后于游戏，但我想供应 4-
我正在寻找 Kademlia 的开源实现C/C++ 中的分布式哈希表。它必须是轻量级和跨平台的(win/linux/mac)。 它必须能够将信息发布到 DHT 并检索它。 最佳答案 OpenDHT是
我在一本书中读到这一行:-“当我们要求 C++ 实现运行程序时，它会通过调用此函数来实现。” 而且我想知道“C++ 实现”是什么意思或具体是什么。帮忙!？ 最佳答案 “C++ 实现”是指编译器加上链接
我正在尝试使用分支定界的 C++ 实现这个背包问题。此网站上有一个 Java 版本:Implementing branch and bound for knapsack 我试图让我的 C++ 版本打印
在很多情况下，我需要在 C# 中访问合适的哈希算法，从重写 GetHashCode 到对数据执行快速比较/查找。 我发现 FNV 哈希是一种非常简单/好/快速的哈希算法。但是，我从未见过 C# 实现的
目录 LRU缓存替换策略 核心思想 不适用场景 算法基本实现 算法优化
1. 绪论 在前面文章中提到 空间直角坐标系相互转换 ，测绘坐标转换时，一般涉及到的情况是：两个直角坐标系的小角度转换。这个就是我们经常在测绘数据处理中，WGS-84坐标系、54北京坐标系
在软件开发过程中，有时候我们需要定时地检查数据库中的数据，并在发现新增数据时触发一个动作。为了实现这个需求，我们在 .Net 7 下进行一次简单的演示. PeriodicTimer .
二分查找 二分查找算法，说白了就是在有序的数组里面给予一个存在数组里面的值key，然后将其先和数组中间的比较，如果key大于中间值，进行下一次mid后面的比较，直到找到相等的，就可以得到它的位置。
我是一名优秀的程序员,十分优秀！