キャッシュ機能を実装する場合、メモリが無限に使える場合を除き、キャッシュとして保存する要素数を制限する必要があります。
今回試した方式はLRU(Least Recently Used)と言いまして、直近に参照した要素が一番古いものを捨てることで、要素数を維持する仕組みになっています。
// LRUを使ったキャッシュのサンプルコード
public class LruCache<TKey, TValue> where TKey : notnull
{
private readonly int _capacity;
private readonly Dictionary<TKey, LinkedListNode<(TKey Key, TValue Value)>> _cacheMap;
private readonly LinkedList<(TKey Key, TValue Value)> _lruList;
public LruCache(int capacity)
{
_capacity = capacity;
_cacheMap = new Dictionary<TKey, LinkedListNode<(TKey, TValue)>>(capacity);
_lruList = new LinkedList<(TKey, TValue)>();
}
public void Put(TKey key, TValue value)
{
if (_cacheMap.TryGetValue(key, out var node))
{
// 更新して先頭に移動
_lruList.Remove(node);
}
else if (_cacheMap.Count >= _capacity)
{
// 古い要素を削除
var lru = _lruList.Last!;
_cacheMap.Remove(lru.Value.Key);
_lruList.RemoveLast();
}
var newNode = new LinkedListNode<(TKey, TValue)>((key, value));
_lruList.AddFirst(newNode);
_cacheMap[key] = newNode;
}
public bool TryGet(TKey key, out TValue? value)
{
if (_cacheMap.TryGetValue(key, out var node))
{
// アクセスされたので先頭に移動
_lruList.Remove(node);
_lruList.AddFirst(node);
value = node.Value.Value;
return true;
}
value = default;
return false;
}
public IEnumerable<(TKey Key, TValue Value)> Entries => _lruList;
}
public static class Program
{
public static void PrintCache<TKey, TValue>(LruCache<TKey, TValue> cache) where TKey : notnull
{
Console.WriteLine("キャッシュコンテンツの一覧:");
foreach (var pair in cache.Entries)
{
Console.WriteLine($"{pair.Key} => {pair.Value}");
}
}
public static void Main()
{
var cache = new LruCache<string, string>(3);
cache.Put("A", "Apple");
cache.Put("B", "Banana");
cache.Put("C", "Cherry");
PrintCache(cache);
Console.WriteLine("--- Accessing A ---");
cache.TryGet("A", out _); // Aを取り出したことでAが先頭に
PrintCache(cache);
Console.WriteLine("--- Adding D ---");
cache.Put("D", "Durian"); // 一番古いBが取り除かれる
PrintCache(cache);
}
}
実行結果
キャッシュコンテンツの一覧:
C => Cherry
B => Banana
A => Apple
--- Accessing A ---
キャッシュコンテンツの一覧:
A => Apple
C => Cherry
B => Banana
--- Adding D ---
キャッシュコンテンツの一覧:
D => Durian
A => Apple
C => Cherry
キャッシュ本体はDictionaryでキーと値を保存するだけで実装出来ます。
参照された順番を管理する必要があり、こちらをLinkedListを使っています。
LinkedListは複数の要素を保管するコンテナの一種ですが、各要素が前後の要素への参照(又はポンタ)を持つことで、要素同士の順番を入れ替えたりすることに都合が良い構造となっています。こちらのサンプルコードの様に頻繁に要素の位置を変更するケースにマッチしていると思います。
配列やList<T>でも要素の入れ替えは出来なくは無いですが、配列の再作成に近いコストを払う必要があるので、LinkedListの方が安上がりです。
Main()でLruCacheを使ったコード実行していますが、キャッシュから要素を取り出すと、順番が変更されていることが確認出来ますし、キャッシュに新しい要素を追加すると古い要素が削除されることが確認出来ます。
このままでは、複数のスレッドからアクセスされると破綻してしまいますのでlock機構を加えて、スレッドセーフにするとよいかと思います。
スレッドセーフ版:LruCache
using System;
using System.Collections.Generic;
public class LruCache<TKey, TValue> where TKey : notnull
{
private readonly int _capacity;
private readonly Dictionary<TKey, LinkedListNode<(TKey Key, TValue Value)>> _cacheMap;
private readonly LinkedList<(TKey Key, TValue Value)> _lruList;
private readonly object _syncRoot = new();
public LruCache(int capacity)
{
_capacity = capacity;
_cacheMap = new Dictionary<TKey, LinkedListNode<(TKey, TValue)>>(capacity);
_lruList = new LinkedList<(TKey, TValue)>();
}
public void Put(TKey key, TValue value)
{
lock (_syncRoot)
{
if (_cacheMap.TryGetValue(key, out var node))
{
_lruList.Remove(node);
}
else if (_cacheMap.Count >= _capacity)
{
var lru = _lruList.Last!;
_cacheMap.Remove(lru.Value.Key);
_lruList.RemoveLast();
}
var newNode = new LinkedListNode<(TKey, TValue)>((key, value));
_lruList.AddFirst(newNode);
_cacheMap[key] = newNode;
}
}
public bool TryGet(TKey key, out TValue? value)
{
lock (_syncRoot)
{
if (_cacheMap.TryGetValue(key, out var node))
{
_lruList.Remove(node);
_lruList.AddFirst(node);
value = node.Value.Value;
return true;
}
value = default;
return false;
}
}
public IEnumerable<(TKey Key, TValue Value)> Entries
{
get
{
lock (_syncRoot)
{
// コピーして列挙時の変更を防ぐ
return new List<(TKey, TValue)>(_lruList);
}
}
}
}
コメント