Lru cache python что это

LRU, метод вытеснения из кэша

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

Мы будем под кэшированием понимать сохранение результатов вычислений в ответ на некоторые запросы. То есть, повторный результат запроса не всегда вычисляется заново, но иногда берется из таблицы, называемой кэшем. Сложно переоценить роль кеширования в современных системах. При этом часто возникает проблема, связанная с недостатком памяти. Действительно, что делать, если запросов много, а памяти хватает лишь для хранения ограниченного числа результатов? В этом случае, как правило, кеш стрится следующим образом. Фиксируется размер кэша, пусть будет N, и сохраняются результаты только для N самых «популярных» запросов.

То есть сохраняются результаты вычислений, которые скорее всего запросят заново.
Как определять эти «популярные» запросы? Наиболее известным способом является LRU, о котором я и расскажу в этой статье.

LRU (least recently used) — это алгоритм, при котором вытесняются значения, которые дольше всего не запрашивались. Соответственно, необходимо хранить время последнего запроса к значению. И как только число закэшированных значений превосходит N необходимо вытеснить из кеша значение, которое дольше всего не запрашивалось.

1. Хеш-таблица hashTable, которая будет хранить непосредственно закэшированные значения.
2. Очередь с приоритетамиtimeQueue. Структура, которая поддерживает следующие операции:
   • Добавить пару значение и приоритет timeQueue.Add(val, priority).
   • Извлечь (удалить и вернуть) значение с наименьшим приоритетом timeQueue.extractMinValue().

Предположим, что для исходных вычислений использовался метод calculate(x). Мы заменим метод calculate на новый calculateWithCache, который пополняет кеш, выталкивает устаревшие значения и запрашивает результат у calculate, если не найдет в кеше.

Так будет выглядеть алгоритм работы calculateWithCache:

calculateWithCache(key) < curTime = getCurrentTime(); // Если значение уже было в кэше вернем его if (key in hashTable) < // Сначала обновим время последнего запроса к key timeQueue.set(key, curTime); return hashTable[key]; >// Иначе вычислим результат result = calculate(key); // Если в кэше уже N элементов, то вытесним самый старый if (hashTable.length == N) < minKey = timeQueue.extractMinValue(); hashTable.remove(minKey); >// Добавим в таблицу, и в очередь hashTable.add(key, result); timeQueue.add(key, curTime); return result; > 

Вот и все. Теперь вместо необходимости сбрасывать кэш пользователю необходимо задать размер кэша. При этом приветствуется задание разумного значения по-умолчанию.

Если воспользоваться эффективной реализацией очереди с приоритетами, то оверхед, который требует LRU — O(log N).

B стандартных библиотеках может быть реализована очередь с приоритетами, например, в C++. Но даже если не реализована, а читать лениво, то можно догадаться, как использовать сбалансированное дерево для реализации очереди с приоритетами с такой же сложностью, правда с чуть большим коэффициентом.

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

Можно найти более сложные эвристики, учитывающие время вычисления calculate для данного ключа key, или объем результата, или что-то еще.
Но в большинстве задач LRU наиболее адекватно определяет самые «популярные» запросы.

Примечание 1: Можно ограничить объем памяти на кэш, а не количество хранимых значений. Алгоритм практически не изменится, только вместо длины будет занимаемая память + память для хранения нового значения.
Примечание 2: Специально избегал вопросов многопоточности, так как это не тема данной статьи.

Update (Спасибо ToSHiC22 за комментарий) Для интересующихся ссылка на чуть более продвинутую реализацию 2Q

@lru_cache и Рекурсия, как работает

Сдаю информатику, 19 задание егэ. Никак не могу понять по какому алгоритму работает рекурсия и как она конкретно записывается в кеш. ИЗ КАКОЙ СТУПЕНИ РЕКУРСИИ ВЫВОДИТСЯ ‘B1’ (к примеру если создам функцию в которой напишу две строки — return 1 и return 2, то после вызова выведется 1, тк почему то только первый обьявленный return возвращает). Там я во списковых включениях вызывается та же функция что и в описании, выходит рекурсия. Как вообще работает код? и простыми словами как @lru_cache записывает кеш? что за значение None? я это гуглю два дня уже, и по меркам егэ это непростительно продолжительное время

 from functools import lru_cache # ПО УСЛОВИЮ ЗАДАЧИ ДВА ИГРОКА И ДВЕ КУЧИ КАМНЕЙ # ЗА ОДИН ХОД МОЖНО ДОБАВИТЬ 1 КАМЕНЬ В ОДНУ ИЗ КУЧ ИЛИ УМНОЖИТЬ ОДНУ ИЗ КУЧ ВДВОЕ # В НАЧАЛЬНЫЙ МОМЕНТ В ПЕРВОЙ КУЧЕ 10, ВО ВТОРОЙ S (1 = 62: # вот тут и начинаются все приколы return 'WIN' if any( game(m) == 'WIN' for m in move(h) ): return 'B1' # а вот тут они заканчиваются . (ПОБЕДА ПЕРВОГО ИГРОКА) for S in range(1, 52): if game( (1, S) ) is not None: print('<>: <>'.format(S, game( (10, S) ) )) print(game.cache_info()) # Пытался что гуглить буду, но ниче не нашёл понятного 

Отслеживать
Ленд Вульпбп
задан 28 дек 2022 в 16:30
Ленд Вульпбп Ленд Вульпбп
25 6 6 бронзовых знаков
Код приводят форматированным ТЕКСТОМ
28 дек 2022 в 16:50
Код текстом в вопрос, только мат из комментариев уберите, а то ещё хуже всё будет.
28 дек 2022 в 16:58
@CrazyElf приношу дикие извинения, я масля на форуме, в крайнем случае обратился.
28 дек 2022 в 17:10

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Непонятно, какой именно None вам непонятен. Если как параметр декоратора lru_cache , то это просто означает, что размер кэша не ограничен. Если задать кэшу ограничение на кол-во хранимых элементов, то при необходимости положить в кэш ещё одно значение и заполненности кэша до этого указанного значения LRU cache посмотрит у себя статистику — какой из элементов кэша запрашивался наиболее давно — и выкинет этот элемент, чтобы добавить новый. Таким образом, размер кэша никогда не будет больше, чем указанный.

А если вас интересует None как результат работы кэшируемой функции, то None будет возвращён, если в вашей функции не сработают оба if и значит не сработает ни один из return . В питоне если функция закончилась, а return ни один не выполнился, то считается, что как будто выполнился return None . Такая договорённость. Ничего не вернувшая функция считается вернувшей None .

Что касается самого кэша, то всё просто. При обращении к кэшированной функции декоратор проверяет — если был уже вызов этой функции с такими же точно аргументами, то функция не выполняется, а берётся результат из словаря декоратора, в котором ключ — это аргументы функции, а значение — это то, что вернула функция, когда её вызвали с такими аргументами. Если же в кэше нет таких аргументов, то функция выполняется и после её выполнения аргументы и результат запоминаются в словаре-кэше. Ну, пока хватает выделенного под кэш размера словаря. Если же места не хватает — см. первый абзац этого ответа, что в этом случае происходит.

Метод cache_info показывает статистику:

• сколько раз кэш сработал удачно (в кэше нашлись аргументы и он вернул значение не выполняя функцию)
• сколько раз кэш «промахнулся» (пришлось таки вызвать функцию, чтобы получить результат и запомнить его потом в кэше)
• какой был задан максимальный размер для кэша функции
• сколько элементов на данный момент хранится в кэше декоратора этой функции

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

P.S. Попробовал запустить без декоратора, подождал несколько минут, не дождался никакого вывода, но счётчик обращений к функции game уже превысил 200 миллионов. Так что на самом деле кеширующий декоратор играет тут решающую роль, без него этот код вообще не выполнится за разумное время.

Декоратор @lru_cache() модуля functools в Python

Декоратор @lru_cache() модуля functools оборачивает функцию с переданными в нее аргументами и запоминает возвращаемый результат соответствующий этим аргументам. Такое поведение может сэкономить время и ресурсы, когда дорогая или связанная с вводом/выводом функция периодически вызывается с одинаковыми аргументами.

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

Различные аргументы можно рассматривать как отдельные вызовы с отдельными записями в кэше. Например f(a=1, b=2) и f(b=2, a=1) различаются по порядку ключевых аргументов и могут иметь две отдельные записи в кэше.

Если указана user_function , то она должна быть вызываемой. Это позволяет применять декоратор @lru_cache непосредственно к пользовательской функции, оставляя значение maxsize по умолчанию равным 128:

from functools import lru_cache @lru_cache def count_vowels(sentence): sentence = sentence.casefold() return sum(sentence.count(vowel) for vowel in 'aeiou') 

Если для параметра maxsize установлено значение None , функция LRU декоратора отключена и кэш может расти без ограничений. Функция LRU работает лучше всего, когда maxsize является степенью двойки.

Если для typed задано значение True , то аргументы функций разных типов будут кэшироваться отдельно. Например f(3) и f(3.0) будут рассматриваться как отдельные вызовы с разными результатами. Если введено typed=False , ТО реализация обычно будет рассматривать их как эквивалентные вызовы и кэшировать только один результат. (Некоторые типы, такие как str и int , могут кэшироваться отдельно, даже если передано False )

Обратите внимание: специфичность типа применяется только к непосредственным аргументам функции, а не к их содержимому. Скалярные аргументы Decimal(42) и Fraction(42) обрабатываются как отдельные вызовы с разными результатами. Напротив, аргументы кортежа (‘answer’, Decimal(42)) и (‘answer’, Fraction(42)) обрабатываются как эквивалентные.

Обернутая функция в этот декоратор будет иметь метод .cache_parameters() (Новое в версии 3.9), которая возвращает новый dict , показывающий значения maxsize и typed . Этот метод служит только для информационных целей. Изменение значений не имеет никакого эффекта.

Чтобы помочь измерить эффективность кэша и настроить параметр maxsize , декорированная функция получает метод .cache_info() , который возвращает именованный кортеж, показывающий hits , misses , maxsize и currsize . В многопоточной среде hits и misses являются приблизительными.

Декоратор также предоставляет метод .cache_clear() для очистки или аннулирования кэша.

Исходная базовая функция доступна через атрибут __wrapped__ , что полезно для самоанализа, для обхода кеша или для преобразования функции в другой кеш.

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

В общем случае кэш LRU следует использовать только тогда, когда вы хотите повторно использовать ранее вычисленные значения. Нет смысла кэшировать функции, которые должны создавать различные изменяемые объекты при каждом вызове или нечистые функции, такие как time.time() или random.random() .

Примеры использования:

Пример кэша LRU для статического веб-контента:

from functools import lru_cache @lru_cache(maxsize=32) def get_pep(num): 'Retrieve text of a Python Enhancement Proposal' resource = 'http://www.python.org/dev/peps/pep-%04d/' % num try: with urllib.request.urlopen(resource) as s: return s.read() except urllib.error.HTTPError: return 'Not Found' >>> for n in 8, 290, 308, 320, 8, 218, 320, 279, 289, 320, 9991: . pep = get_pep(n) . print(n, len(pep)) >>> get_pep.cache_info() # CacheInfo(hits=3, misses=8, maxsize=32, currsize=8) 

Пример эффективного вычисления чисел Фибоначчи с использованием кэша для реализации техники динамического программирования:

from functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n  2: return n return fib(n-1) + fib(n-2) >>> [fib(n) for n in range(16)] # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] >>> fib.cache_info() # CacheInfo(hits=28, misses=16, maxsize=None, currsize=16) 

Изменено в версии 3.8: Добавлена ​​опция user_function .

Новое в версии 3.9: Добавлен метод .cache_parameters() .

• ОБЗОРНАЯ СТРАНИЦА РАЗДЕЛА
• Способы использования модуля functools
• Декоратор @cached_property модуля functools
• Функция cmp_to_key() модуля functools
• Декоратор @cache() модуля functools, кеширующий декоратор
• Декоратор @lru_cache() модуля functools
• Декоратор @total_ordering модуля functools
• Функция partial() модуля functools
• Класс partialmethod() модуля functools
• Функция reduce() модуля functools
• Декоратор @singledispatch модуля functools
• Декоратор @singledispatchmethod модуля functools
• Декоратор @update_wrapper() модуля functools
• Декоратор @wraps() модуля functools

functools.lru_cache

maxsize=128 — Максимальное хранимое количество результатов (читай: размер кеша). Если установить в ‘None’, то размер не будет ограничен (и кеш перестанет быть LRU). Лучше, если значение будет степенью двойки.

+py3.3. typed=False — Если ‘True’, то разные типы будут кешироваться отдельно: например, результаты ‘f(3)’ и ‘f(3.0)’ будут закешированы по отдельности.

LRU (least recently used) кеш — кеш с конечным размером, где часто используемые записи вытесняют прочие.

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

 from functools import lru_cache

 
@lru_cache(maxsize=30) 
def get_articles(on_date):
 
# Здесь затратная операция, выбирающая статьи 
# на определённую дату. 
articles = [. ]
 
return articles

 
get_articles('2017-12-12') 
get_articles('2017-12-13') 
get_articles('2017-12-12') # Взяты из кеша.

 
# Рассмотрим эффективность кеша: 
get_articles.cache_info() 
# CacheInfo(hits=1, misses=2, maxsize=20, currsize=2)

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

Эту функцию декоратор прикрепит к декорируемой функции. При помощи неё можно замерять эффективность кеша.
Она возвращает именованный кортеж CacheInfo со следующими атрибутами:

hits	Количество попаданий в кеш.
misses	Количество промахов мимо кеша.
maxsize	Максимальный размер кеша.
currsize	Текущий размер кеша.

На заметку
Если используются нити, то значения в hits и misses приблизительны.

cache_clear()

Эту функцию декоратор прикрепит к декорируемой функции. С её помощью можно очистить/инвалидировать кеш.

__wrapped__

Этот атрибут декоратор прикрепит к декорируемой функции. В нём будет содержаться ссылка на оригинальную функцию, к которой был применён декоратор. Может быть полезно для интроспекции, обхода кеша, или для оборачивания в другой кеш.