Папулярныя алгарытмы кэшавання: LFU кэш
Прывітанне, паважаны чытач!
Сённяшні пост я б хацеў пачаць са стандартнага пытання на сумоўі: “Якімі дасягненнямі на працы ты асабліва ганарышся?” Гэтае пытанне можа здзівіць ці нават абразіць, бо сёння аказваецца недастаткова проста добра выконваць свае абавязкі, гэтым трэба абавязкова ганарыцца. Але не дай інтэрв’юеру цябе заспець знянацку. Калі памяшканне прасторнае, то ў гэты момант лепш нават ўстаць з крэсла, твой монаспектакль павінен запальваць агонь у вачах. Абгарнуў на днях метад у try / catch? Не саромейся – ты ўжо асцярог кампанію ад выключнай сітуацыі! Месяц таму выправіў чарговы баг? Гэта было не проста выпраўленне, гэта было выратаванне кампаніі ад патэнцыйнага банкруцтва! І тут галоўнае не перастарацца, бо інтэрв’юер хутчэй за ўсё таксама часта наведвае сумоўя, і ўжо не раз “ратаваў кампанію ад банкруцтва”. А лепш, вядома, загадзя падрыхтавацца да гэтага пытання.
Але гэта стандартнае пытанне. А мы вернемся да нестандартнага. У папярэднім пасце мы ўжо пазнаёміліся з кэшаваннем і алгарытмам LRU выцяснення элементаў. Прапаную разгледзець наступны прыклад:
var cache = new LruCache<string, int>(2);
for (int i = 0; i < 100; ++i)
{
cache.Add("x", 1);
}
cache.Add("y", 3);
cache.Add("z", 1);
if (cache.TryGet("x", out var x))
{
Console.WriteLine($"Element 'x' is equal {x}");
}
else
{
Console.WriteLine($"Element 'x' was not found");
}У кансолі мы пабачым "Element 'x' was not found". Такім чынам, з кэша будзе выцеснены элемент x, да якога было ў 100 разоў больш зваротаў, але LRU стратэгія ніяк гэта не ўлічвае. Гэты прыклад хоць і даволі надуманы, але ён добра ілюструе абмежаванні LRU стратэгіі. У гэтым пасце разгледзім новую стратэгію, якая будзе ўлічваць частату зваротаў да элементаў. Паехалі!
LFU (least frequently used) – стратэгія выцяснення элемента, які выкарыстоўваўся радчэй за ўсё. Пад дадзеным элементам разумеецца элемент, доступ да якога па ключы (метады дадання і атрымання значэння) ажыццяўляўся найменшую колькасць разоў. У выпадку, калі такіх элементаў некалькі, то выцясняецца элемент, доступ да якога не ажыццяўляўся даўжэй за ўсё.
Поўную рэалізацыю LFU кэша на C#, як і заўсёды, можна паглядзець на GitHub праекта coding-interview.
Ну а мы вернемся да рэалізацыі. Пачнем з самага простага варыянту. Рэалізуем абгортку вакол асацыятыўнага масіва без стратэгіі выцяснення:
public class LfuCache<TKey, TValue>
{
public LfuCache()
{
_cache = new Dictionary<TKey, TValue>();
}
public void Add(TKey key, TValue value)
{
_cache[key] = value;
}
public bool TryGet(TKey key, [MaybeNullWhen(false)] out TValue value)
{
return _cache.TryGetValue(key, out value);
}
public bool Remove(TKey key)
{
return _cache.Remove(key);
}
public void Clear()
{
_cache.Clear();
}
private readonly Dictionary<TKey, TValue> _cache;
}Абмяжуем наш кэш максімальна дазволенай колькасцю элементаў capacity. Створым агульны лічыльнік доступу да элементаў totalAccessSteps, які будзем павялічваць пры кожным наступным доступе. Для кожнага захаванага элемента будзем захоўваць час доступу да яго accessStepsByKey і колькасць зваротаў да дадзенага элементу frequenciesByKey. Забягаючы наперад адзначым, што дадзеная рэалізацыя не з’яўляецца аптымальнай, у працэсе яна будзе палепшана.
public class LfuCache<TKey, TValue>
{
public LfuCache(int capacity)
{
if (capacity <= 0)
{
var exMessage = $"must be a positive value";
throw new ArgumentOutOfRangeException(nameof(capacity), capacity, exMessage);
}
_capacity = capacity;
_cache = new Dictionary<TKey, TValue>();
_frequenciesByKey = new Dictionary<TKey, int>();
_accessStepsByKey = new Dictionary<TKey, int>();
_totalAccessSteps = 0;
}
// ...
private readonly Dictionary<TKey, TValue> _cache;
private readonly Dictionary<TKey, int> _frequenciesByKey;
private readonly Dictionary<TKey, int> _accessStepsByKey;
private readonly int _capacity;
private int _totalAccessSteps;
}Абнавім відавочныя аперацыі выдалення элемента і ачысткі кэша:
public bool Remove(TKey key)
{
_accessStepsByKey.Remove(key);
_frequenciesByKey.Remove(key);
return _cache.Remove(key);
}
public void Clear()
{
_cache.Clear();
_frequenciesByKey.Clear();
_accessStepsByKey.Clear();
_totalAccessSteps = 0;
}Разгледзім аперацыю дадання элемента ў кэш. У залежнасці ад сітуацыі могуць узнікнуць тры розных выпадку:
- Калі дадзены элемент прысутнічае ў кэшы, то абнаўляем яго значэнне, колькасць зваротаў і час доступу;
- Калі кэш утрымлівае менш элементаў, чым яго ёмістасць, то проста захоўваем новы элемент;
- Калі кэш ўтрымлівае ўжо максімальна дазволеную колькасць элементаў, то выдаляем элемент, які выкарыстоўваўся найменшую колькасць разоў. Калі такіх элементаў некалькі, то выдаляем элемент, доступ да якога ажыццяўляўся раней за ўсё. Пасля чаго дадаем новы элемент.
public void Add(TKey key, TValue value)
{
if (_cache.ContainsKey(key))
{
Update(key, value);
}
else if (_cache.Count < _capacity)
{
AddNew(key, value);
}
else
{
Evict();
AddNew(key, value);
}
++_totalAccessSteps;
}
private void AddNew(TKey key, TValue value)
{
_cache[key] = value;
_accessStepsByKey[key] = _totalAccessSteps;
_frequenciesByKey[key] = 1;
}
private void Update(TKey key, TValue value)
{
_cache[key] = value;
_accessStepsByKey[key] = _totalAccessSteps;
_frequenciesByKey[key] = _frequenciesByKey[key] + 1;
}
private void Evict()
{
var minFrequency = _frequenciesByKey.Values.Min();
var minFrequencyKeys = _frequenciesByKey
.Where((x) => x.Value == minFrequency)
.Select((x) => x.Key);
var lfuItemKey = minFrequencyKeys
.Aggregate((l, r) => _accessStepsByKey[l] < _accessStepsByKey[r] ? l : r);
Remove(lfuItemKey);
}Аперацыя доступу да элемента па ключы таксама павінна памяняць час доступу і колькасць зваротаў да элемента, таму скарыстаемся ўжо рэалізаваным Update метадам:
public bool TryGet(TKey key, [MaybeNullWhen(false)] out TValue value)
{
if (_cache.TryGetValue(key, out value))
{
Update(key, value);
return true;
}
value = default!;
return false;
}Як адзначалася вышэй, такая рэалізацыя не з’яўляецца аптымальнай. Асноўная праблема знаходзіцца ў метадзе Evict, дзе мы поўным пераборам шукаем элемент, які будзе выцеснены з кэша. Зоймемся аптымізацыяй!
Разаб’ем нашы элементы на групы па частаце выкарыстання. У кожнай групе ўпарадкуем усе нашы элементы ў выглядзе спісу ў парадку дадання ад больш ранняга да больш позняга. Па вертыкалі будзем размяшчаць частотныя групы, а па гарызанталі будзем размяшчаць элементы ў кожнай групе (квадраты пазначаюць частотныя групы, а кругі – элементы, дзе злева запісаны ключ, а справа – значэнне):
Паглядзім, як будзе змяняцца структура пад уздзеяннем розных аперацый. Аперацыя ачысткі кэша відавочная. Таму разгледзім пакінутыя аперацыі (далей чырвоным колерам будзем паказваць выдаленне вяршыні або групы, а сінім – даданне):
- Аперацыя выдалення элемента з кэша. У дадзеным выпадку мы выдаляем элемент з частотнай групы. Калі элемент з’яўляўся апошнім у групе, то выдаляем і дадзеную частотную групу:
- Аперацыя дадання новага элемента, калі кэш утрымлівае менш элементаў, чым максімальна дазволеная значэнне. У дадзеным выпадку дадаецца новы элемент у канцы спісу ў групу элементаў з частатой звароту роўнай адзінцы:
- Аперацыя дадання новага элемента, калі кэш змяшчае максімальна дазволеную колькасць элементаў. У дадзеным выпадку выдаляецца элемент, які знаходзіцца ў спісе першым у групе з самай нізкай частатой зваротаў, так як час доступу да яго менш, чым час доступу да любога іншага элемента. Пасля выдалення мы атрымліваем структуру, у якой колькасць элементаў менш, чым максімальна дазволеная. А значыць слушна тое, што апісана ў пункце вышэй:
- Аперацыя абнаўлення існуючага элемента. Новае значэнне элемента пры гэтым можа быць любым, бо яно не ўплывае на сартаванне элементаў. Заўважым, што калі элемент быў апошнім у групе, то дадзеная група выдаляецца. Пры неабходнасці ствараецца новая частотная група:
- Аперацыя атрымання значэння па ключы. Дадзеная аперацыя эквівалентная аперацыі абнаўлення існуючага элемента з захаваннем яго зыходнага значэння.
Засталося навучыцца хутка знаходзіць элемент у спісе па ключы. Для гэтага будзем захоўваць для кожнага ключа спасылку на патрэбны элемент. Для хуткага пошуку частотнай групы, таксама будзем захоўваць для кожнай частоты спасылку на адпаведную частотную групу.
internal class LfuItem<TKey, TValue>
{
public LfuItem(TKey key, TValue value, int frequency)
{
Key = key;
Value = value;
Frequency = frequency;
}
public TKey Key { get; }
public TValue Value { get; }
public int Frequency { get; }
}
internal class LfuFrequencyGroup<TKey, TValue>
{
public LfuFrequencyGroup(int frequency)
{
Frequency = frequency;
Items = new LinkedList<LfuItem<TKey, TValue>>();
}
public int Frequency { get; }
public LinkedList<LfuItem<TKey, TValue>> Items { get; }
}
public class LfuCache<TKey, TValue>
{
public LfuCache(int capacity)
{
if (capacity <= 0)
{
var exMessage = $"must be a positive value";
throw new ArgumentOutOfRangeException(nameof(capacity), capacity, exMessage);
}
_capacity = capacity;
_itemNodesByKey = new Dictionary<TKey, LinkedListNode<LfuItem<TKey, TValue>>>();
_frequencyGroupsByFrequency = new Dictionary<
int,
LinkedListNode<LfuFrequencyGroup<TKey, TValue>>
>();
_frequencyGroups = new LinkedList<LfuFrequencyGroup<TKey, TValue>>();
}
// ...
private readonly Dictionary<TKey, LinkedListNode<LfuItem<TKey, TValue>>> _itemNodesByKey;
private readonly Dictionary<
int,
LinkedListNode<LfuFrequencyGroup<TKey, TValue>>
> _frequencyGroupsByFrequency;
private readonly LinkedList<LfuFrequencyGroup<TKey, TValue>> _frequencyGroups;
private readonly int _capacity;
}Перапішам метады ачысткі і выдалення элемента з кэша:
public bool Remove(TKey key)
{
if (_itemNodesByKey.TryGetValue(key, out var itemNode))
{
var frequencyGroupNode = _frequencyGroupsByFrequency[itemNode.Value.Frequency];
frequencyGroupNode.Value.Items.Remove(itemNode);
if (frequencyGroupNode.Value.Items.Count == 0)
{
_frequencyGroupsByFrequency.Remove(itemNode.Value.Frequency);
_frequencyGroups.Remove(frequencyGroupNode);
}
_itemNodesByKey.Remove(key);
return true;
}
return false;
}
public void Clear()
{
_itemNodesByKey.Clear();
_frequencyGroups.Clear();
_frequencyGroupsByFrequency.Clear();
}Метады дадання элемента (заўважым, што рэалізацыя асноўнага метаду Add засталася ранейшай):
public void Add(TKey key, TValue value)
{
if (_itemNodesByKey.ContainsKey(key))
{
Update(key, value);
}
else if (_itemNodesByKey.Count < _capacity)
{
AddNew(key, value);
}
else
{
Evict();
AddNew(key, value);
}
}
private void AddNew(TKey key, TValue value)
{
var lfuItem = new LfuItem<TKey, TValue>(key, value, 1);
if (!_frequencyGroupsByFrequency.TryGetValue(1, out var frequencyGroupNode))
{
frequencyGroupNode = _frequencyGroups
.AddFirst(new LfuFrequencyGroup<TKey, TValue>(1));
_frequencyGroupsByFrequency.Add(1, frequencyGroupNode);
}
_itemNodesByKey[key] = frequencyGroupNode.Value.Items.AddLast(lfuItem);
}
private void Update(TKey key, TValue value)
{
var itemNode = _itemNodesByKey[key];
var frequency = itemNode.Value.Frequency;
var frequencyNode = _frequencyGroupsByFrequency[itemNode.Value.Frequency];
var nextFrequency = frequency + 1;
if (!_frequencyGroupsByFrequency.TryGetValue(
nextFrequency,
out var nextFrequencyNode
))
{
nextFrequencyNode = _frequencyGroups.AddAfter(
frequencyNode,
new LfuFrequencyGroup<TKey, TValue>(nextFrequency)
);
_frequencyGroupsByFrequency[nextFrequency] = nextFrequencyNode;
}
Remove(key);
var nextItemNode = nextFrequencyNode.Value.Items.AddLast(new LfuItem<TKey, TValue>(
key,
value,
nextFrequency
));
_itemNodesByKey[key] = nextItemNode;
}
private void Evict()
{
var lfuItemNode = _frequencyGroups.First.Value.Items.First;
Remove(lfuItemNode.Value.Key);
}І метад атрымання элемента (рэалізацыя метаду TryGet амаль не змянілася):
public bool TryGet(TKey key, [MaybeNullWhen(false)] out TValue value)
{
if (_itemNodesByKey.TryGetValue(key, out var itemNode))
{
value = itemNode.Value.Value;
Update(key, value);
return true;
}
value = default!;
return false;
}На гэтым рэалізацыя LFU кэшавання скончана. Мне трэба развітвацца, а табе, дарагі чытач, прапаную азнаёміцца з іншымі разборамі задач, якія могуць трапляцца на тэхнічных сумоўях. Да хуткіх сустрэч!
