Lru cache что это

Как работать с кэшированием данных в Python

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

Алексей Кодов
Автор статьи
23 июня 2023 в 18:57

Кэширование данных — это важный аспект в разработке приложений, так как это позволяет оптимизировать процесс загрузки и обработки информации. В этой статье мы разберем основные принципы кэширования данных в Python и покажем примеры его использования.

Что такое кэширование данных?

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

Встроенный декоратор functools.lru_cache

Python предоставляет встроенный декоратор functools.lru_cache , который позволяет легко кэшировать результаты функций. LRU (Least Recently Used) кэш — это кэш с ограниченным размером, который автоматически удаляет наименее недавно использованные элементы при необходимости освободить место для новых данных.

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

import functools @functools.lru_cache(maxsize=100) def expensive_function(arg1, arg2): # Здесь выполняется какая-то дорогостоящая операция result = arg1 + arg2 return result # Вызов функции result = expensive_function(1, 2)

В этом примере результаты expensive_function будут кэшироваться и сохраняться в LRU-кэше размером до 100 элементов.

Python-разработчик: новая работа через 9 месяцев
Получится, даже если у вас нет опыта в IT

Кэширование с использованием внешних хранилищ

В некоторых случаях может потребоваться кэширование данных с использованием внешних хранилищ, таких как Redis или Memcached. Это особенно актуально при работе с веб-приложениями и распределенными системами.

Пример кэширования данных с использованием Redis:

import redis cache = redis.Redis(host='localhost', port=6379) def cache_data(key, data, ttl=3600): cache.setex(key, ttl, data) def get_cached_data(key): return cache.get(key) # Кэширование данных cache_data('my_key', 'my_data') # Получение данных из кэша result = get_cached_data('my_key')

В этом примере мы используем библиотеку redis для работы с кэшем Redis. Функции cache_data и get_cached_data позволяют сохранять и получать данные из кэша соответственно.

Заключение

Кэширование данных является полезным инструментом для оптимизации работы приложений и снижения нагрузки на серверы. В Python существует несколько способов реализации кэширования, включая встроенный декоратор functools.lru_cache и использование внешних хранилищ, таких как Redis или Memcached. Экспериментируйте с различными подходами и выбирайте тот, который наиболее подходит для вашего проекта. ��

LRU-кэш в одну строчку

Кэш нужен, чтобы запоминать результаты каких-то тяжелых операций: вычислений, доступа к диску или запросов в сеть. В Python есть отличный декоратор, чтобы элегантно снабдить вашу функцию кэшированием: @functools.lru_cache(maxsize=128, typed=False)

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

�� Пример. Если аргумент декорируемой функции не встречался в кэше, то выполнится тело функции за полсекунды, результат будет сохранен в кэше. И в следующий раз тело функции не будет вызвано, а вернется результат из кэша:

from functools import lru_cache import time @lru_cache(maxsize=4) def slow_sqr(i): print(f'Calculating sqr for . ') time.sleep(0.5) # задумаемся. return i ** 2 for i in [1, 2, 3, 1, 3, 4, 4, 1]: print(f'i = => i ** 2 = ') print(slow_sqr.cache_info()) # CacheInfo(hits=4, misses=4, maxsize=4, currsize=4)

�� Пример. Можно не задавать ограничение размеру кэша. Вычислим числа Фибоначчи рекурсивным методом. Без @lru_cache этот метод экстремально неэффективный с ростом n. Однако, с кэшированием – это уже динамическое программирование и работает сравнительно быстро:

@lru_cache(maxsize=None) def fib(n): if n < 2: return n return fib(n-1) + fib(n-2) print(fib(500)) print(fib.cache_info())

• В основе кэша – словарь, поэтому все аргументы функции должны быть хэшируемы (hash). Надеюсь, никто не путает хэш (hash) и кэш (cache).

• Вызовы f(a=1, b=2) и f(b=2, a=1) – разные и создадут две записи в кэше.

• Рекомендуется ставить maxsize как степень двойки.

• f.cache_info() – информация о размере кэша и статистике его работы

• f.cache_clear() – очистка кэша

• Если аргумент декоратора typed=True, то аргументы разных типов будут кэшироваться отдельно. Пример: f(3) и f(3.0) будут отвечать разным записям в кэше.

Дополнение. С версии Python 3.8 можно применять lru_cache без аргументов (размер кэша по умолчанию 128 элементов):

@lru_cache def f(x): .

�� Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway! ��

Популярные алгоритмы кэширования: LRU кэш

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

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

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

1. Добавить элемент по ключу;
2. Получить элемент по ключу;
3. Удалить элемент по ключу;
4. Очистить кэш.

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

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

Полную реализацию LRU кэша на C#, как всегда, можно посмотреть на GitHub проекта coding-interview.

Начнём с реализации самого простого варианта без стратегии вытеснения. Другими словами добавим обёртку вокруг стандартной реализации ассоциативного массива, которая обычно присутствует в стандартной библиотеке твоего любимого языка программирования:

public class LruCache < public LruCache() < _cache = new Dictionary(); > 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 _cache; >

Теперь ограничим наш кэш максимально допустимым количеством элементов capacity . Создадим общий счётчик доступа к элементам totalAccessSteps , который будем увеличивать при каждом последующем доступе. Также будем хранить для каждого сохранённого элемента время доступа к нему accessStepsByKey , необходимое для определения элемента, который не использовался дольше всего. Забегая вперёд отметим, что данная реализация не является оптимальной, в процессе она будет улучшена.

public class LruCache  < public LruCache(int capacity) < if (capacity _capacity = capacity; _cache = new Dictionary(); _accessStepsByKey = new Dictionary(); _totalAccessSteps = 0; > // . private readonly int _capacity; private readonly Dictionary _cache; private readonly Dictionary _accessStepsByKey; private int _totalAccessSteps; >

Обновим самые очевидные операции удаления и очистки кэша:

public bool Remove(TKey key) < _accessStepsByKey.Remove(key); return _cache.Remove(key); >public void Clear()

Рассмотрим операцию добавления элемента в кэш. В зависимости от ситуации могут возникнуть три следующих случая:

1. Если данный элемент присутствует в кэше, то обновляем его значение и время доступа;
2. Если кэш содержит меньше элементов, чем его вместимость, то просто сохраняем новый элемент;
3. Если кэш содержит уже максимально допустимое количество элементов, то удаляем элемент, который не использовался дольше всего и сохраняем новый элемент.

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

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

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

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

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

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

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

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

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

internal class LruItem  < public LruItem(TKey key, TValue value) < Key = key; Value = value; >public TKey Key < get; >public TValue Value < get; >> public class LruCache  < public LruCache(int capacity) < if (capacity _capacity = capacity; _itemNodesByKey = new Dictionary>(); _items = new LinkedList(); > // . private readonly int _capacity; private readonly Dictionary> _itemNodesByKey; private readonly LinkedList _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()

Методы добавления элемента (заметим, что реализация основного метода 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(key, value); _itemNodesByKey[key] = _items.AddLast(item); > private void Update(TKey key, TValue value) < Remove(key); AddNew(key, value); >private void Evict()

И метод получения элемента (реализация метода 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; >

Вот и всё, наш кэш готов! Можно смело идти на собеседование, а мне пора прощаться. До скорого!

Хранение изображений с помощью LruCache

При разработке приложений разработчик может столкнуться с такой проблемой, когда ему нужно очень часто работать с изображениями. Система каждый раз должна их загружать, обрабатывать, затем, после окончания использования, удалять, либо удалять тогда, когда это не нужно, с помощью сборщика мусора. Чтобы не выполнять все эти операции по кругу достаточно будет кэшировать готовые изображения в памяти устройства и по мере необходимости обращаться к ним. Для таких целей в Android отличным решением является использование кэш-памяти (LruCache) и дискового кэша (DiskLruCache). Оба этих способа основаны на использовании LRU-кэша.

LRU-кэшем называется стратегия кэширования, в которой используется политика Вытеснения давно неиспользуемых (Least Recently Used). То есть, когда кэш заполнен, и мы хотим добавить в него новые данные, из него автоматически будут удалены те данные, которые не использовались наиболее длительное время.

Класс LruCache был добавлен в Android начиная с версии Android 3,1 (API 12), но также доступен через библиотеку поддержки, начиная с версии Android 1.6. Основной его задачей является повторное использование объектов, создание которых затратно по ресурсам. Например, вы можете загрузить изображение из Интернета и поместить его в кэш, чтобы в будущем обращаться только к кэш-памяти.

В нашем приложении «Менеджер системных приложений» при прокрутке списка приложений метод onBindViewHolder() постоянно обращается к PackageManager для загрузки иконок приложений. Правильным решением будет после первой загрузки иконок помещать их в кэш-память, чтобы впоследствии обращаться только к ней.

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

public class IconCache extends LruCache  < public IconCache(int maxSize) < super(maxSize); >public Drawable getBitmapFromMemory(String key) < return this.get(key); >public void setBitmapToMemory(String key, Drawable drawable) < if (getBitmapFromMemory(key) == null) < this.put(key, drawable); Log.d("TEST", key + " добавлен в кэш"); >> >

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

При создании экземпляра LruCache в параметры необходимо передать размер кэша. Важно указать его верно, поскольку слишком маленький размер приведёт к тому, что операции с кэшем станут более затратными, чем текущие, а слишком большой — оставить мало памяти для других приложений на устройстве или даже вызвать исключение java.lang.outOfMemory. Поэтому при определении размера кэша важно сначала определить размер памяти устройства. Единого способа для этого нет, поэтому мы будем использовать класс метод getMemoryClass() класса ActivityManager.

int memClass = mainView.getMemoryClassFromActivity(); int cacheSize = 1024 * 1024 * memClass / 8; IconCache iconCache = new IconCache(cacheSize);

Поскольку в приложении используется MVP паттерн, инициализация происходит на уровне Presenter и затем экземпляр IconCache передаётся в фоновый поток, принимающий запросы на загрузку иконок. Подробнее о MVP можно почитать в предыдущей статье.

Затем, когда ViewHolder запрашивает иконку для приложения, в потоке проверяется, есть ли в кэше объект с данным именем пакета. Если он есть, то берём из кэша и возвращаем результат, а если нет — вызываем PackageManager, загружаем иконку, возвращаем её в главный поток и помещаем в кэш.

private void handleRequest(final T target) < final String packageName = mRequestMap.get(target); final Drawable icon; if (packageName != null) < try < if (iconCache.getBitmapFromMemory(packageName) == null) < icon = packageManager.getApplicationIcon(packageName); iconCache.setBitmapToMemory(packageName, icon); >else < icon = iconCache.getBitmapFromMemory(packageName); >mResponseHandler.post(new Runnable() < @Override public void run() < if (mRequestMap.get(target) == null || !mRequestMap.get(target).equals(packageName)) < return; >mRequestMap.remove(target); mGetIconThreadListener.onIconDownloaded(target, icon); > >); > catch (PackageManager.NameNotFoundException | NullPointerException e) < e.printStackTrace(); >> >

О том, как реализован фоновый поток, можно почитать в данной статье.

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