Про LRU-кэш (в том числе — на собеседовании) — 3 способа реализации

[wataru]

Честно было бы при сравнении давать последнему, "упрощенному" варианту меньше размер. Ибо ограничение часто - количетство памяти. И поколенческий вариант потребляет почти в 2 раза больше. Ну в среднем там меньше, конечно, будет, но это надо смотреть статистику. Так что для сравнения яблок с яблоками, надо чтобы алгоритмы потребляли сравнимое количество памяти.

Еще непонятно, почему второй вариант быстрее первого. Не верю, что работа со списками настолько медлнее O(N) удаления. У вас там в тестовых данных удалений нет что ли?

[RodionGork]

Честно было бы при сравнении давать последнему, "упрощенному" варианту меньше размер

тут я спорить не собираюсь т.к. с точки зрения данных внутри всё зависит от конкретного случая, конкретных данных. в классическом варианте две коллекции ключей а значений только одна, так выходит. в кэшах где значения "массивны" - ваше замечание абсолютно справедливо.

Еще непонятно, почему второй вариант быстрее первого. Не верю, что работа со списками настолько медлнее O(N) удаления.

тут кажется недопонимание :) удаление во втором варианте не O(N) а O(1) амортизированное - мы ведь договорились удалять группами - т.е. редко. это ещё в тестовом примере группа небольшая (треть что ли данных)

работа со списками не медленная сама по себе - нам всего лишь нужно переставить несколько указателей

проблема в том что это приходится делать на каждый Get - поэтому многие варианты оптимизации этого варианта связаны с тем чтобы этого всё-таки не делать так часто (правда это фактически делает кэш не строго LRU)

В целом же тесты и сравнение сделаны не для того чтобы показать что "это быстрее того" а просто продемонстрировать что они более-менее близки. Всё-таки разница не так велика чтобы из неё делать далеко идущие выводы. Много зависит от реализации мэпы например внутри языка...

[Medi]

А почему бы в способе #2 не добавить сквозной счетчик (там про это есть). Минимальное и максимальное значение храним в отдельных переменных. Тогда при групповом удалении сразу будет понятно с какого значения счетчика удалять. ( если счетчик от min=1 до max=100, и надо удалить 20%, все записи где его значение < 20 удаляем. min устанавливаем в 20. Получится удаление O(N) Значение счетчика используем по модулю равному максимальному размеру словаря.

[RodionGork]

Спасибо за комментарий :) приятно что тема, несмотря на "туманность" действительно даёт повод повыдумывать дополнительные варианты!

Минимальное и максимальное значение храним в отдельных переменных.

Да, это вполне неплохой вариант у которого однако есть нюанс - он будет давать хорошие варианты если элементы используются более-менее равномерно.

Мы же счетчик увеличиваем как на Put-ах так и на Get-ах - и вот представим если к какому-то элементу (или нескольким, небольшому числу) внезапно возникла пиковая нагрузка - за счет него счётчик увеличится, скажем, на несколько тысяч очень быстро. И когда мы попытаемся выбрать 20% от разницы между минимумом и максимумом - то в удаляемые попадут внезапно все элементы кроме этого опрошенного тысячу раз.

Ну, это необязательно катастрофа, просто нужно иметь в виду такую возможность.

Т.е. ваш вариант это тоже некая "эвристика" имеющая право на существование :)

Значение счетчика используем по модулю равному максимальному размеру словаря.

или просто проходя кэш при операции очередного удаления уменьшаем все счетчики на фиксированную величину (например, min).

[cpud47]

Кажется вариант 2 ввиду амортизации неприменим на практике. Обычно же этот lru требуется в онлайн задачах. Крайне редко он нужен в оффлайн алгоритмах.

Ну и использование итерации по мапе в качестве семплирования — не очень хорошо. Сразу по нескольким причинам. Никто же не обещает порядка итерации по мапе — это не то же самое, что и случайный порядок. Ну и в принципе, такая итерация использует внешнюю случайность — то есть она зависит от данных. Это плохо, так как данные могут быть скорелированны. Для робастности нужно использовать внутреннюю случайность.

[RodionGork]

тут опять же не буду спорить т.к. эти соображения зависят от пары вещей:

вариант 2 ввиду амортизации неприменим на практике

это разумеется зависит от размера кэша и времени обращения к нижележащему хранилищу - если речь о кэшировании веб-страниц, условно, то флаш кэша занимающий 5мс очевидно ничтожен по сравнению с запросами в интернет занимающими в десятки и сотни раз больше; но конечно в задачах где нам нужен гарантированно быстрый отклик это действительно неудобно (впрочем в таких задачах и LRU-стратегия под вопросом - как пишет википедия, кэш в процессорах ARM вообще на рандомную стратегию переделали ради простоты и скорости - и норм)

Ну и использование итерации по мапе в качестве семплирования — не очень хорошо. 

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

[cpud47]

то флаш кэша занимающий 5мс очевидно ничтожен по сравнению с запросами в интернет занимающими в десятки и сотни раз больше;

В этом случае у нас просто линейный Put. Амортизация тут неприменима. И тогда выигрыша от реализации 2.5 никакого нет.

Но в любом случае, O(n) кеш штука изначально довольно специфичная. Предлагать её без дополнительных вводных — странно.

кэш в процессорах ARM вообще на рандомную стратегию переделали ...

Ну так там же кеш по бакетам(в каждом бакете независимое вытеснение). И размер одного бакета 4-32, емнип. Это как раз ситуация довольно специфичная.

всё правильно, тут всё таки демонстрационная реализация :) к сожалению устройство и возможности мэпы конкретно в Go делают её особенно неудобной для любого "продвинутого" применения

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

При самописной реализации хештаблицы выигрыш от альтерантивных схем становится меньше. Можно же спокойно хранить ноды в стиле linked hashmap — и тогда выигрыш по памяти становится слабым (+заменить указатели на 32-битные индексы чтобы ещё ближе к другим вариантам стать).

Ну и как правило LRU не прям хорошо работает. Поэтому достаточно часто нужны гибридные стратегии — и там обычно тяжело отказаться от связных списков.

P.S. не поймите неправильно, статья интересная