Lru cache python что это

Introduction to Least Recently Used Cache

“In computing, cache algorithms are optimizing instructions, or algorithms, that a computer program or a hardware-maintained structure can utilize in order to manage a cache of information stored on the computer. When the cache is full, the algorithm must choose which items to discard to make room for the new ones. … from Wiki”

Brief

Caching is an optimization technique that can use in the applications to keep recent or often-used data in memory locations that are faster or computationally cheaper to access than their source.

A cache implemented using the LRU strategy organizes its items in order of use. Every time you access an entry, the LRU (least recently used) algorithm will move it to the top of cache. This way, the algorithm can quickly identify the entry that’s gone unused the longest by looking at the bottom of the list.

The LRU algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. In general, the LRU cache should only be used when you want to reuse previously computed values.

In this post, I would like to briefly discuss about the simple concept of LRU cache in python and practice to design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Properties

The basic properties of LRU caches:

Super fast accesses. LRU caches store items in order from most-recently used to least-recently used. That means both can be accessed in O(1) time.
Super fast updates. Each time an item is accessed, updating the cache takes O(1) time.

Higher-Order functools.lru_cache() Function in Python

In python 3.7.13 standard library, the functools module creates higher-order functions that interact with other functions. The functools module defines the LRU caches function as @functools.lru_cache(maxsize=128, typed=False) which is a decorator to wrap a function with a memorizing callable. It can save time when an expensive or I/O bound function is periodically called with the same arguments. (more details, refer to functools.lru_cache or cpython: functools.py)

Example of efficiently computing Fibonacci numbers using a cache to implement a dynamic programming technique:

Another simple example of operation using a cache to add two numbers:

Here is the output of addition operator using a cache:

Exercises

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value + pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1: Input [“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] Output: [null, null, null, 1, null, -1, null, -1, 3, 4]

Solution

The solution was learned from LeetCode Discuss.

Reference

Thanks for reading! Feel free to leave the comments below or email to me. Any pieces of advice or discussions are always welcome. 🙂

functools — Higher-order functions and operations on callable objects¶

The functools module is for higher-order functions: functions that act on or return other functions. In general, any callable object can be treated as a function for the purposes of this module.

The functools module defines the following functions:

@ functools. cache ( user_function ) ¶

Simple lightweight unbounded function cache. Sometimes called “memoize”.

Returns the same as lru_cache(maxsize=None) , creating a thin wrapper around a dictionary lookup for the function arguments. Because it never needs to evict old values, this is smaller and faster than lru_cache() with a size limit.

The cache is threadsafe so that the wrapped function can be used in multiple threads. This means that the underlying data structure will remain coherent during concurrent updates.

It is possible for the wrapped function to be called more than once if another thread makes an additional call before the initial call has been completed and cached.

New in version 3.9.

Transform a method of a class into a property whose value is computed once and then cached as a normal attribute for the life of the instance. Similar to property() , with the addition of caching. Useful for expensive computed properties of instances that are otherwise effectively immutable.

The mechanics of cached_property() are somewhat different from property() . A regular property blocks attribute writes unless a setter is defined. In contrast, a cached_property allows writes.

The cached_property decorator only runs on lookups and only when an attribute of the same name doesn’t exist. When it does run, the cached_property writes to the attribute with the same name. Subsequent attribute reads and writes take precedence over the cached_property method and it works like a normal attribute.

The cached value can be cleared by deleting the attribute. This allows the cached_property method to run again.

Note, this decorator interferes with the operation of PEP 412 key-sharing dictionaries. This means that instance dictionaries can take more space than usual.

Also, this decorator requires that the __dict__ attribute on each instance be a mutable mapping. This means it will not work with some types, such as metaclasses (since the __dict__ attributes on type instances are read-only proxies for the class namespace), and those that specify __slots__ without including __dict__ as one of the defined slots (as such classes don’t provide a __dict__ attribute at all).

If a mutable mapping is not available or if space-efficient key sharing is desired, an effect similar to cached_property() can also be achieved by stacking property() on top of lru_cache() . See How do I cache method calls? for more details on how this differs from cached_property() .

New in version 3.8.

Transform an old-style comparison function to a key function . Used with tools that accept key functions (such as sorted() , min() , max() , heapq.nlargest() , heapq.nsmallest() , itertools.groupby() ). This function is primarily used as a transition tool for programs being converted from Python 2 which supported the use of comparison functions.

A comparison function is any callable that accepts two arguments, compares them, and returns a negative number for less-than, zero for equality, or a positive number for greater-than. A key function is a callable that accepts one argument and returns another value to be used as the sort key.

For sorting examples and a brief sorting tutorial, see Sorting HOW TO .

New in version 3.2.

Decorator to wrap a function with a memoizing callable that saves up to the maxsize most recent calls. It can save time when an expensive or I/O bound function is periodically called with the same arguments.

The cache is threadsafe so that the wrapped function can be used in multiple threads. This means that the underlying data structure will remain coherent during concurrent updates.

It is possible for the wrapped function to be called more than once if another thread makes an additional call before the initial call has been completed and cached.

Since a dictionary is used to cache results, the positional and keyword arguments to the function must be hashable .

Distinct argument patterns may be considered to be distinct calls with separate cache entries. For example, f(a=1, b=2) and f(b=2, a=1) differ in their keyword argument order and may have two separate cache entries.

If user_function is specified, it must be a callable. This allows the lru_cache decorator to be applied directly to a user function, leaving the maxsize at its default value of 128:

If maxsize is set to None , the LRU feature is disabled and the cache can grow without bound.

If typed is set to true, function arguments of different types will be cached separately. If typed is false, the implementation will usually regard them as equivalent calls and only cache a single result. (Some types such as str and int may be cached separately even when typed is false.)

Note, type specificity applies only to the function’s immediate arguments rather than their contents. The scalar arguments, Decimal(42) and Fraction(42) are be treated as distinct calls with distinct results. In contrast, the tuple arguments (‘answer’, Decimal(42)) and (‘answer’, Fraction(42)) are treated as equivalent.

The wrapped function is instrumented with a cache_parameters() function that returns a new dict showing the values for maxsize and typed. This is for information purposes only. Mutating the values has no effect.

To help measure the effectiveness of the cache and tune the maxsize parameter, the wrapped function is instrumented with a cache_info() function that returns a named tuple showing hits, misses, maxsize and currsize.

The decorator also provides a cache_clear() function for clearing or invalidating the cache.

The original underlying function is accessible through the __wrapped__ attribute. This is useful for introspection, for bypassing the cache, or for rewrapping the function with a different cache.

The cache keeps references to the arguments and return values until they age out of the cache or until the cache is cleared.

If a method is cached, the self instance argument is included in the cache. See How do I cache method calls?

An LRU (least recently used) cache works best when the most recent calls are the best predictors of upcoming calls (for example, the most popular articles on a news server tend to change each day). The cache’s size limit assures that the cache does not grow without bound on long-running processes such as web servers.

In general, the LRU cache should only be used when you want to reuse previously computed values. Accordingly, it doesn’t make sense to cache functions with side-effects, functions that need to create distinct mutable objects on each call, or impure functions such as time() or random().

Example of an LRU cache for static web content:

Example of efficiently computing Fibonacci numbers using a cache to implement a dynamic programming technique:

6 Python декораторов, которые значительно упростят ваш код

Лучшая функция Python, которая применяет эту философию из «дзен Python», — это декоратор.

Декораторы могут помочь вам писать меньше кода для реализации сложной логики и повторно использовать его повсюду.

Более того, существует множество замечательных встроенных декораторов Python, которые значительно облегчают нам жизнь, поскольку мы можем просто использовать одну строчку кода для добавления сложных функций к существующим функциям или классам.

Болтать не буду. Давайте посмотрим на отобранные мной 6 декораторов, которые покажут вам, насколько элегантен Python.

1. @lru_cache: Ускоряем программы кэшированием

Самый простой способ ускорить работу функций Python с помощью трюков кэширования — использовать декоратор @lru_cache.

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

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

Рассмотрим интуитивно понятный пример:

Приведенная выше программа вычисляет N-ое число Фибоначчи с помощью функции Python. Это занимает много времени, поскольку при вычислении fibonacci(30) многие предыдущие числа Фибоначчи будут вычисляться много раз в процессе рекурсии.

Теперь давайте ускорим этот процесс с помощью декоратора @lru_cache:

Как видно из приведенного выше кода, после использования декоратора @lru_cache мы можем получить тот же результат за 0,00002990 секунды, что намного быстрее, чем предыдущие 0,18129450 секунды.

Декоратор @lru_cache имеет параметр maxsize, который определяет максимальное количество результатов для хранения в кэше. Когда кэш заполнен и необходимо сохранить новый результат, наименее использованный результат вытесняется из кэша, чтобы освободить место для нового. Это называется стратегией наименее использованного результата (LRU).

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

2. @total_ordering: Добавляем недостающие методы сравнения

Декоратор @total_ordering из модуля functools используется для генерации недостающих методов сравнения для класса Python на основе тех, которые определены.

Как видно из приведенного выше кода, в классе Student нет определений для методов ge, gt и le. Однако благодаря декоратору @total_ordering результаты наших сравнений между различными экземплярами будут правильными.

Преимущества этого декоратора очевидны:

Он может сделать ваш код чище и сэкономить ваше время. Поскольку вам не нужно писать все методы сравнения.

Некоторые старые классы могут не определять достаточно методов сравнения. Безопаснее добавить к нему декоратор @total_ordering для дальнейшего использования.

3. @contextmanager: Кастомный менеджер контекстов

В Python есть механизм менеджмента контекста, который поможет вам правильно управлять ресурсами.

В основном нам нужно просто использовать операторы with:

Как показано в приведенном выше коде, мы можем открыть файл с помощью оператора with, чтобы он был закрыт автоматически после записи. Нам не нужно явно вызывать функцию f.close(), чтобы закрыть файл.

Иногда нам нужно определить индивидуальный менеджер контекста для каких-то особых требований. В этом случае декоратор @contextmanager — наш друг.

Например, следующий код реализует простой настраиваемый контекстный менеджер, который может выводить соответствующую информацию при открытии или закрытии файла.

4. @property: Настраиваем геттеры и сеттеры для классов

Геттеры и сеттеры — важные понятия в объектно-ориентированном программировании (ООП).

Для каждой переменной экземпляра класса метод getter возвращает ее значение, а метод setter устанавливает или обновляет ее значение. Учитывая это, геттеры и сеттеры также известны как аксессоры и мутаторы, соответственно.

Они используются для защиты данных от прямого и неожиданного доступа или изменения.

Различные языки ООП имеют разные механизмы для определения геттеров и сеттеров. В Python мы можем просто использовать декоратор @property.

Как видно из приведенного выше примера, переменная score не может быть установлена как 999, что является бессмысленным числом. Потому что мы ограничили ее допустимый диапазон внутри функции сеттера с помощью декоратора @property.

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

5. @cached_property: Кешируем результат функции как атрибут

В Python 3.8 в модуле functools появился новый мощный декоратор — @cached_property. Он может превратить метод класса в свойство, значение которого вычисляется один раз, а затем кэшируется как обычный атрибут на протяжении всего существования экземпляра.

В приведенном выше коде мы оптимизировали метод area через свойство @cached_property. Таким образом, нет повторных вычислений для circle.area одного и того же неизменного экземпляра.

6. @atexit.register: Объявляем функцию которая вызывается при выходе из программы

Декоратор @register из модуля atexit может позволить нам выполнить функцию при завершении работы интерпретатора Python.

Этот декоратор очень полезен для выполнения финальных задач, таких как освобождение ресурсов или просто прощание! ��

На выходе получаем

Еще больше примеров использования Python и Machine Learning в современных сервисах можно посмотреть в моем телеграм канале. Я пишу про разработку, ML, стартапы и релокацию в UK для IT специалистов.