Популярные алгоритмы кэширования: 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, где мы полным перебором ищем элемент с самым ранним временем доступа. Ну что, почему бы не заняться тогда оптимизацией?

Так как наши операции с кэшем вызываются последовательно, то мы можем упорядочить все наши элементы в виде списка в порядке добавления от более раннего к более позднему (слева записан ключ, а справа — значение):

Посмотрим, как будет изменяться список под воздействием различных операций. Операции очистки кэша и удаления определённого элемента очевидны. Поэтому рассмотрим оставшиеся операции (далее красным цветом будем показывать удаление вершины, а синим — добавление):

Операция добавления нового элемента, если кэш содержит меньше элементов, чем максимально допустимое значение. В данном случае добавляется новый элемент в конец списка, так как его время добавления будет в любом случае больше, чем время доступа к любому другому элементу:

Операция добавления нового элемента, если кэш содержит максимально допустимое количество элементов. В данном случае удаляется элемент, который находится в списке первым, так как время доступа к нему меньше, чем время доступа к любому другому элементу. После удаления мы получаем список, в котором количество элементов меньше, чем максимально допустимое. А значит верно то, что описано в пункте выше:

Добавление элемента в заполненный LRU кэш

Операция обновления существующего элемента и операция получения значения по ключу. Оба данных случая эквивалентны удалению элемента и добавлению его в конец списка. Новое значение элемента может быть любым (в примере ниже мы оставили исходное значение), так как не влияет на сортировку элементов:

Осталось научиться быстро находить элемент в списке по ключу. Для этого будем хранить для каждого ключа ссылку на нужный элемент списка:

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 кэш

Понравилось это:

Добавить комментарийОтменить ответ

Поделиться ссылкой:

Понравилось это:

Добавить комментарийОтменить ответ