Алгоритм LRU является относительно распространенной темой на собеседованиях с бэкенд-инженерами.В этой статье каждый должен понять алгоритм LRU и, наконец, использовать Python для простой реализации кэша на основе алгоритма LRU.
что такое кеш
Давайте сначала посмотрим на картинку Когда мы посещаем веб-страницу, браузер отправляет запрос на сервер, и сервер выполняет ряд операций, чтобы вернуть страницу в браузер.
При одновременном доступе нескольких браузеров за короткий промежуток времени будет инициировано несколько запросов, и сервер будет выполнять ряд идентичных операций для каждого запроса. Дублирование работы не только приводит к трате ресурсов, но также может привести к увеличению времени отклика.
Кэш может сохранить страницу, возвращенную сервером, и при повторном посещении других браузеров нет необходимости беспокоить сервер, и страница возвращается прямо из кеша. Чтобы обеспечить скорость отклика, кеш обычно основан на относительно дорогом оборудовании, таком как ОЗУ, что определяет, что нам сложно использовать большой объем кеша для хранения всех страниц. не получилось закешировать, его еще нужно запросить.сервер. Так как емкость кэша ограничена, а объем данных не ограничен (количество новых страниц, генерируемых Интернетом каждый день, неоценимо), необходимо поместить наиболее полезную информацию на край кэша.
что такое ЛРУ
LRU — это алгоритм устранения кеша (также называемый алгоритмом подкачки памяти в ОС).Поскольку пространство кеша ограничено, необходимо исключить данные, которые обычно не используются в кеше, и оставить часто используемые данные, чтобы максимизировать эффективность кеша. . LRU - это такой алгоритм, чтобы решить, "кто выбывает, а кто остается".
Логика ликвидации LRU
Мы используем изображение, чтобы описать логику исключения LRU.Кэш на картинке представляет собой структуру списка.Верхний узел-голова, а нижний-хвост узел.Емкость кеша 8 (8 маленьких сеток):
- Когда есть новые данные (это означает, что данные не были кэшированы ранее), добавьте в начало списка
- Когда кеш достигает максимальной емкости, необходимо удалить лишние данные, а в это время удаляются данные в конце списка.
- Когда данные в кеше попадаются, переместите данные в начало списка (эквивалентно добавлению нового кеша).
Согласно приведенной выше логике, мы можем видеть, что если к части данных часто обращаются, то она будет постоянно перемещаться в начало списка и не будет исключаться из кеша, и чем реже к данным обращаются, тем проще быть выжатым из кеша.
20 строк кода Python для практики LRU
Далее мы используем Python для реализации кеша с использованием алгоритма LRU.
Из предыдущей статьи мы можем знать, что кеш упрощен до двух функций: одна — загружать данные (кешировать данные), а другая — выплевывать данные (хит-кеш), поэтому наш кеш нужно только поместить и получить извне. , Интерфейс в порядке.
В соответствии с предыдущей диаграммой нам нужен только список (список) внутри кеша для реализации логики LRU, но хотя список можно использовать для реализации логики, скорость может быть очень низкой при оценке того, следует ли попасть в кеш (список list нужно пройти, чтобы узнать, что данных в нем нет). В Python мы можем использовать структуры на основе хэшей, такие как словари (dict) или наборы (set), чтобы быстро определить, существуют ли данные, и решить проблему производительности реализации списка. Но словари и наборы не имеют порядка, и было бы неплохо, если бы существовала структура данных, которую можно было бы сортировать и хранить на основе хеша.
В пакет collections Python встроена эта служебная структура OrderedDict.OrderedDict является подклассом dict, но элементы, хранящиеся внутри, упорядочены (характеристика списков).
Решили проблему структуры данных, можем напрямую написать логику, код такой:
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.queue = collections.OrderedDict()
def get(self, key):
if key not in self.queue:
return -1 // 要找的数据不在缓存中返回-1
value = self.queue.pop(key) // 将命中缓存的数据移除
self.queue[key] = value // 将命中缓存的数据重新添加到头部
return self.queue[key]
def put(self, key, value):
if key in self.queue: // 如果已经在缓存中，则先移除老的数据
self.queue.pop(key)
elif len(self.queue.items()) == self.capacity:
self.queue.popitem(last=False) // 如果不在缓存中并且到达最大容量，则把最后的数据淘汰
self.queue[key] = value // 将新数据添加到头部
В следующем интервью, когда вы столкнетесь с темой LRU, вы готовы к этому?