Вот почему брат первый83оригинальная статья
LFU, который заставляет людей чесать затылок
Я видел подобное обсуждение в приложении несколько дней назад:
Увидел интересный комментарий:
LFU действительно сложно, голова болит.
Если LRU — это легкий режим, то измените среднюю букву с R (недавно) на F (часто), то есть LFU, то есть жесткий режим.
Не беда, если вы не знаете Часто. Ведь это английский словарный запас 8-го класса. Я, английский 8-й с половиной игрок, научу вас:
Таким образом, полное название LFU — наименее часто используемая стратегия.
Очевидно, что акцент делается на частоте использования.
Полное название алгоритма LRU — «Наименее недавно использовавшийся». Наименее недавно использованный алгоритм.
Акцент делается на время.
Когда размерность статистики изменилась от времени к частоте, что произошло с реализацией алгоритма?
Этот вопрос не указан первым, я первый и ранее написанныйАлгоритм LRUСделайте сравнение.
LRU vs LFU
Идея алгоритма LRU заключается в том, что если к части данных не было доступа в течение последнего периода времени, то маловероятно, что к ним будут обращаться в будущем. Поэтому, когда указанное пространство заполнено данными, данные, к которым не было доступа в течение длительного времени, должны быть удалены.
То есть при исключении данных мы смотрим только на измерение того, как долго данные находятся в кэше.
Когда кэш LFU заполнен и данные необходимо удалить, он смотрит на количество обращений к данным.Чем больше раз выполняется доступ к LFU, тем меньше вероятность, что он будет удален.
Однако к некоторым данным можно обращаться одинаковое количество раз.
Как с этим бороться?
Если количество посещений одинаково, то рассмотрите измерение того, как долго данные остаются в кеше.
Другими словами, алгоритм LFU сначала смотрит на количество посещений, и если время совпадает, то смотрит на время кэширования.
Приведу конкретный пример.
Предполагая, что размер нашего кеша равен 3, доступ выполняется в следующем порядке данных:
Если удаление данных выполняется по алгоритму LRU, то результаты десяти обращений следующие:
После десяти обращений в кэше остаются три элемента b, c и d.
Вы чувствуете, что что-то не так?
Элемент а посещается 5 раз за десять посещений, и, наконец, элемент а удаляется?
Согласно алгоритму LFU, последними тремя элементами, оставшимися в кэше, должны быть b, c, a.
Таким образом, LFU является более разумным и более подходящим, чем LRU.
Предположим, давайте реализуем LFUCache:
class LFUCache {
public LFUCache(int capacity) {
}
public int get(int key) {
}
public void put(int key, int value) {
}
}
Итак, каким должно быть мышление?
Посмотри.
LFU схема 1 - двусвязный список
Если бы мне пришлось хорошенько подумать, прежде чем я вообще не столкнулся с алгоритмом LFU, единственными решениями, которые я мог бы придумать, были бы следующие:
Потому что требуется и частота, и временная последовательность.
Мы можем сделать связанный список, сначала отсортировать по частоте, той же частоте, а потом отсортировать по времени.
Поскольку в этом процессе нам нужно удалять узлы, для эффективности мы используем двусвязный список.
Давайте все же предположим, что емкость нашего кеша равна 3, и воспользуемся только что полученным набором данных для демонстрации.
Мы определяем частоту как freq, тогда после завершения первых трех посещений, то есть после завершения трех посещений по запросу:
Связанный список должен выглядеть так:
Частота обращения всех трех элементов равна 1.
Для первых трех элементов value=a — это элемент, к которому не обращались дольше всего с той же частотой, поэтому это следующий элемент головного узла, ожидающий удаления в любой момент.
Затем пришло значение = запрос:
Когда приходит этот запрос, частота (freq) узла со значением=a в связанном списке становится равной 2.
В этот момент он имеет наибольшую частоту и меньше всего должен быть устранен.
Таким образом, связанный список становится таким:
Затем последовало 3 запроса со значением=a подряд:
Изменения связанного списка в это время сосредоточены на частоте (freq) узла value=a:
Затем приходит этот запрос b:
Частота узла b изменилась с 1 на 2, а также изменилось положение узла:
Затем c запрашивает:
Как вы думаете, что произойдет в это время?
Текущая частота доступа c в связанном списке равна 1. Когда это c запрошено, частота c в связанном списке станет равной 2.
Вы сказали, что это совпадение, что в это время частота узла value=b также равна 2.
Машина разбилась, так что вы сказали, что я должен делать в это время?
Как я уже говорил: когда частота одинакова, посмотрите на время.
Узел со значением = c посещается, поэтому необходимо исключить узел со значением = b, который был посещен ранее.
Связанный список на этом этапе должен выглядеть так:
Затем пришла последняя просьба:
Элемент d ранее не появлялся в связанном списке, и емкость связанного списка в настоящее время заполнена.
Время ликвидации.
Таким образом, следующий узел head (value=b) удаляется, а узел value=d вставляется:
Наконец, все запросы выполнены.
В кэше остаются три элемента d, c, a.
Общий процесс выглядит следующим образом:
Конечно, здесь просто показать изменения в списке цепочек.
По сути, мы ставим пары ключ-значение.
Таким образом, должен быть HashMap для хранения отношения сопоставления между ключами и узлами связанного списка.
Это настолько просто, что я могу думать об этом пальцами ног, поэтому я не буду подробно останавливаться на этом.
В соответствии с приведенной выше идеей, если вы пишете код медленно, вы должны быть в состоянии его написать.
Приведенное выше решение для двусвязного списка — это решение, о котором большинство людей может думать напрямую.
Интервьюер определенно ищет решение с временной сложностью O(1).
Временная сложность этого решения теперь O (N).
О(1) раствор
Если мы хотим найти решение с временной сложностью O(1), мы должны тщательно его проанализировать, и мы не можем просто думать об этом.
Сначала проанализируйте свои потребности.
Первый момент: нам нужно запросить соответствующее ему значение по ключу.
Вы можете думать об этом пальцами ног, используя HashMap для хранения пар ключ-значение.
Временная сложность запроса составляет O(1), что удовлетворяет требованиям.
Второй момент: всякий раз, когда мы оперируем клавишей, будь то запрос или новое добавление, нам нужно поддерживать частоту этой клавиши, которая записывается как freq.
Потому что нам нужно часто оперировать частотой, соответствующей ключу, то есть мы должны получить частоту указанного ключа с временной сложностью O(1).
Ну, пожалуйста, скажи мне вслух, какую структуру данных использовать?
Нужно ли иметь еще один HashMap для хранения соответствия между ключом и частотой?
Третий пункт: Если кеш не помещается, когда данные нужно удалить, удалите ключ с наименьшей частотой.
Обратите внимание на приведенное выше предложение: [удалить ключ с наименьшей частотой].
минимальная частота?
Как узнать, какая клавиша имеет наименьшую частоту?
Как упоминалось ранее, существует HashMap, в котором хранится соответствие между ключом и частотой.
Конечно, мы можем пройтись по этому HashMap, чтобы получить ключ с наименьшей частотой.
Но, друзья, обход идет, так что временная сложность по-прежнему будет O(1)?
тогда что нам делать?
Обратите внимание, когда наступит кульминация, она будет заброшена, как только вы ее выучите, и прервется в один момент.
Мы можем создать переменную для записи этой минимальной частоты, записать ее как minFreq, разве этого недостаточно?
Теперь, когда у нас есть минимальная частота (minFreq), нам нужно получить ключ, соответствующий этой минимальной частоте, а временная сложность равна O(1).
Давай, друг, скажи мне, пожалуйста, вслух, какую структуру данных ты придумал еще раз?
Вы снова подумали о HashMap?
Что ж, теперь у нас есть три HashMaps, позвольте представить их вам:
- HashMap, в котором хранятся ключ и значение, т. е. HashMap
. - HashMap, в котором хранятся ключ и частота, т. е. HashMap
. - Hashmap, который хранит Freq и ключ, т.е. hashmap
.
Каждый из них выполняет свою собственную функцию, и цель состоит в том, чтобы иметь временную сложность O (1).
Но мы можем объединить первые два HashMaps.
Давайте получим объект, который содержит два свойства, значение и частоту.
Предполагая, что объект называется Node, он выглядит так с частотой по умолчанию, равной 1:
class Node {
int value;
int freq = 1;
//构造函数省略
}
Итак, теперь мы можем заменить первые два HashMap одним, а именно HashMap
Точно так же мы можем добавить еще один ключевой атрибут в Node:
class Node {
int key;
int value;
int freq = 1;
//构造函数省略
}
Поскольку Node содержит ключ, вы можете заменить третий HashMap
На данный момент нам все еще не хватает очень важной части информации, а именно следующей.
Четвертый момент: может быть несколько ключей с одинаковой минимальной частотой, в это время удалите тот элемент, который дольше всего находился в кеше.
Для этого требования нам нужно найти Node через freq, тогда операция представляет собой хэш-таблицу HashMap
Вышеупомянутое [несколько ключей имеют одинаковую минимальную частоту], что означает, что через minFreq можно запрашивать несколько узлов.
Итак, хеш-таблица HashMap
HashMap.
Тогда возникает вопрос:Какую коллекцию мы должны использовать для хранения этого объекта Node?
Не паникуйте, давайте сначала разберемся, каким условиям должен соответствовать этот набор.
Во-первых, когда вам нужно удалить Node.
Поскольку эта коллекция содержит данные с одинаковой частотой доступа, есть надежда, что этот пакет данных может иметь временную последовательность, чтобы можно было быстро удалить узел, ожидавший наибольшее время.
Со временем вы можете быстро найти ключ, который был удален дольше всего.Какую структуру данных вы можете придумать?
Разве это не двусвязный список?
Затем, когда вам нужно получить доступ к узлу.
Когда к узлу обращаются, его частота должна быть увеличена на единицу.
Например следующий пример:
Предположим, что минимальная частота доступа равна 5, а 5 соответствует 3 объектам Node.
На данный момент я хочу получить доступ к объекту со значением = b, тогда объект будет удален со значением ключа = 5.
Затем добавьте к частоте единицу, то есть 5+1=6.
Добавьте его к набору значений key=6, и это будет выглядеть так:
То есть мы должны поддерживать быстрое удаление любого узла.
Мы можем настроить двусвязный список для вышеуказанных требований.
Но в классе коллекций Java есть коллекция, удовлетворяющая указанным выше условиям порядка и поддержки быстрого удаления.
Это LinkedHashSet.
Следовательно, HashMap
В заключение.
Нам нужны два HashMap, HashMap
Затем вам также необходимо поддерживать минимальную частоту доступа, minFreq.
Да, кстати, есть еще параметр для записи максимальной емкости, поддерживаемой кешем, емкости.
Ушел.
Некоторые друзья должны спросить: не могли бы вы дать мне код?
Эти анализы выполняются, и код медленно развертывается сам по себе.
Пишите код после того, как ваше мышление станет ясным.Даже если вы не пишете код без ошибок во время собеседования, вы практически неразлучны
Алгоритм LFU в Dubbo
Dubbo поддерживает алгоритм LFU после версии 2.7.7:
Расположение его исходного кода:org.apache.dubbo.common.utils.LFUCache
Код небольшой, всего более 200 строк, что немного отличается от реализации LFU, о которой мы упоминали выше.
Вы можете видеть, что он даже не поддерживает minFreq.
Но это не важно, и отладка точки останова позволит быстро проанализировать идеи автора кода.
Важно отметить, что я обнаружил ошибку, просматривая алгоритм Dubbo LFU.
Это не относится к ошибке в реализации этого алгоритма LFU, я видел, что с реализацией алгоритма проблем нет.
Баг в том, что хотя Dubbo и добавил реализацию алгоритма кэширования LFU, его нельзя использовать от имени пользователя.
В чем проблема?
Я посмотрю на тебя.
Исходный код говорит мне, что я могу использовать стратегию кэширования lfu, настроив ее следующим образом:
Однако, когда я настраиваю его таким образом и инициирую вызов, это выглядит так:
Вы можете видеть, что политика кэширования текущего запроса действительно lfu.
Но вылетает ошибка:
No such extension org.apache.dubbo.cache.CacheFactory by name lfu
Стратегии лфу нет.
Разве это не играет со мной?
Давайте рассмотрим конкретные причины.
существуетorg.apache.dubbo.common.extension.ExtensionLoader#getExtensionClassesПолучено только 4 стратегии кэширования, и нет нужного нам LFU:
Итак, исключение выбрасывается здесь:
Почему мы не нашли LFU, который искали?
Тогда это зависит от того, знакомы ли вы с SPI.
В файле SPI действительно нет конфигурации для lfu:
Это ошибка.
Итак, как решить эту проблему?
Это очень просто, просто добавьте его, и все готово.
Вредоносный, случайно внес еще одну строку исходного кода в Dubbo.
Последнее слово (пожалуйста, обратите внимание)
Если у вас нехватка знаний и знаний, то неизбежно будут ошибки.Если вы найдете что-то не так, вы можете поднять это в фоновом режиме, а я доработаю.
Спасибо за прочтение, настаиваю на оригинальности, очень приветствую и благодарю за внимание.
Я почему, программист, который в основном пишет код, часто пишет статьи и изредка снимает видео.