Папулярныя алгарытмы кэшавання: LRU кэш

Прывітанне, паважаны чытач!

Тэхнічнае сумоўе – гэта працэс рашэння цікавых алгарытмічных задач, якія хутчэй за ўсё не спатрэбяцца ні табе, ні твайму інтэрв’юеру ў прафесійнай кар’еры, акрамя як на наступным тэхнічным сумоўі. І тым не менш такія задачы вельмі папулярныя на сумоўях, таму што дазваляюць ацаніць навыкі кандыдата ў пошуку абмежаванняў, прасачыць за яго працэсам абдумвання, а таксама замерыць хуткасць набору цыклаў for у нататніку. Адным з тыпаў папулярных задач з’яўляюцца задачы на рэалізацыю кэша.

Кэш – гэта праграмнае або апаратнае сховішча дадзеных з высакахуткасным доступам. Кэш часта ўжываецца, напрыклад, для захавання вынікаў вылічэнняў, каб паменшыць колькасць паўторных вылічэнняў. Таксама кэш можа прымяняцца для захавання вынікаў доступу да якога-небудзь сховішча з меншай хуткасцю доступу. У любым выпадку, паколькі кэш толькі дублюе нейкія дадзеныя або вынікі, якія могуць быць атрыманы паўторна, то, як правіла, кэш валодае толькі часовай памяццю. Хай і не такой часовай, як у таго самага рэкрутара, які абяцаў ператэлефанаваць, але не ператэлефанаваў.

Звычайна інтэрфейс кэша можна прадставіць у выглядзе наступнага набору аперацый:

Дадаць элемент па ключы;
Атрымаць элемент па ключы;
Выдаліць элемент па ключы;
Ачысціць кэш.

Пры гэтым паколькі дадаваць элементы ў кэш бясконца мы можам толькі ў тэорыі, то кэш павінен таксама апісваць стратэгію выцяснення элементаў. Напрыклад, вызначаць элемент, які павінен быць выдалены пры перавышэнні максімальнай колькасці элементаў.

LRU (least recently used) – стратэгія выцяснення элемента, які не выкарыстоўваўся даўжэй за ўсё. Пад дадзеным элементам разумеецца элемент, доступ да якога па ключы (метады дадання і атрымання значэння) не ажыццяўляўся даўжэй за ўсё.

Поўную рэалізацыю LRU кэша на C#, як заўсёды, можна паглядзець на GitHub праекта coding-interview.

Пачнём з рэалізацыі самага простага варыянту без стратэгіі выцяснення. Іншымі словамі дададзім абгортку вакол стандартнай рэалізацыі асацыятыўнага масіва, якая звычайна прысутнічае ў стандартнай бібліятэцы тваей любімай мовы праграмавання:

public class LruCache<TKey, TValue>
{
    public LruCache()
    {
        _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, неабходнае для вызначэння элемента, які не выкарыстоўваўся даўжэй за ўсё. Забягаючы наперад адзначым, што дадзеная рэалізацыя не з’яўляецца аптымальнай, у працэсе яна будзе палепшана.

public class LruCache<TKey, TValue>
{
    public LruCache(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>();
        _accessStepsByKey = new Dictionary<TKey, int>();
        _totalAccessSteps = 0;
    }

    // ...

    private readonly int _capacity;
    private readonly Dictionary<TKey, TValue> _cache;
    private readonly Dictionary<TKey, int> _accessStepsByKey;
    private int _totalAccessSteps;
}

Абнавім самыя відавочныя аперацыі выдалення і ачысткі кэша:

public bool Remove(TKey key)
{
    _accessStepsByKey.Remove(key);
    return _cache.Remove(key);
}

public void Clear()
{
    _accessStepsByKey.Clear();
    _cache.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;
}

private void Update(TKey key, TValue value)
{
    Remove(key);
    AddNew(key, value);
}

private void Evict()
{
    var minKey = _accessesTime.Aggregate((l, r) => l.Value < r.Value ? l : r).Key;
    Remove(minKey);
}

Аперацыя доступу да элемента па ключы таксама павінна памяняць час доступу да элемента, таму скарыстаемся ўжо рэалізаваным 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 LruItem<TKey, TValue>
{

    public LruItem(TKey key, TValue value)
    {
        Key = key;
        Value = value;
    }

    public TKey Key { get; }
    public TValue Value { get; }
}

public class LruCache<TKey, TValue>
{
    public LruCache(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<LruItem<TKey, TValue>>>();
        _items = new LinkedList<LruItem<TKey, TValue>>();
    }

    // ...

    private readonly int _capacity;
    private readonly Dictionary<TKey, LinkedListNode<LruItem<TKey, TValue>>> _itemNodesByKey;
    private readonly LinkedList<LruItem<TKey, TValue>> _items;
}

Перапішам метады ачысткі і выдалення элемента з кэша:

public bool Remove(TKey key)
{
    if (_itemNodesByKey.TryGetValue(key, out var node))
    {
        _items.Remove(node);
        return _itemNodesByKey.Remove(key);
    }

    return false;
}

public void Clear()
{
    _items.Clear();
    _itemNodesByKey.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 item = new LruItem<TKey, TValue>(key, value);
    _itemNodesByKey[key] = _items.AddLast(item);
}

private void Update(TKey key, TValue value)
{
    Remove(key);
    AddNew(key, value);
}

private void Evict()
{
    var minKey = _items.First.Value.Key;
    Remove(minKey);
}

І метад атрымання элемента (рэалізацыя метаду TryGet амаль не змянілася):

public bool TryGet(TKey key, [MaybeNullWhen(false)] out TValue value)
{
    if (_itemNodesByKey.TryGetValue(key, out var node))
    {
        value = node.Value.Value;
        Update(key, value);
        return true;
    }

    value = default!;
    return false;
}

Вось і ўсё, наш кэш гатовы! Можна смела ісці на сумоўе, а мне пара развітвацца. Да сустрэчы!

Categories:Тэхнічнае сумоўе

Tags:C#Кэшаванне Структуры дадзеных

itdranik

IT Dranik

Папулярныя алгарытмы кэшавання: LRU кэш

Like this:

Leave a ReplyCancel reply

Share this:

Like this:

Leave a ReplyCancel reply