Lru cache python что это
The functools module in Python deals with higher-order functions, that is, functions operating on(taking as arguments) or returning functions and other such callable objects. The functools module provides a wide array of methods such as cached_property(func), cmp_to_key(func), lru_cache(func), wraps(func), etc. It is worth noting that these methods take functions as arguments.
lru_cache()
lru_cache() is one such function in functools module which helps in reducing the execution time of the function by using memoization technique.
Syntax:
@lru_cache(maxsize=128, typed=False)Parameters:
maxsize:This parameter sets the size of the cache, the cache can store upto maxsize most recent function calls, if maxsize is set to None, the LRU feature will be disabled and the cache can grow without any limitations
typed:
If typed is set to True, function arguments of different types will be cached separately. For example, f(3) and f(3.0) will be treated as distinct calls with distinct results and they will be stored in two separate entries in the cache
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 the wrapped function can be used in multiple threads.
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 be achieved by a stacking property() on top of cache() :
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 the wrapped function can be used in multiple threads.
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:
LRU Cache in Python | Let’s talk about caching in Python | Tutorial on caching with functools.lru_cache
There may have been a time, when we have to run a function OVER and OVER again, let’s say we are using a for loop and we have to call a function for thousands of time:
If we could somehow, remove the cost to call that repetitive function, we will speed up our code by significant time. Here we have a very simple add function, it takes two argument “ a” and “ b”, computes and return their sum.
Instead of calling the add() function every time, if we could preserve the output for known argument, our program will run faster.
We are using a for loop, to call add() function multiple times with same argument. Each time we call the add() function, it recalculates the sum and return the output value even the arguments are same. For this case the calculation is simple but many times such calculation can be computationally heavy and recalculation can take a lot time.
LRU Cache in Python Standard Library
Python Standard Library provides lru_cache or Least Recently Used cache. As the name suggests, the cache is going to keep the most recent inputs/results pair by discarding the least recent/oldest entries first.
We can see that the “Expensive…” is printed only one time, that means we are calling the function only once and it saves us a lot of computing time.
Implementation of LRU Cache in Python
Implementing lru cache is very simple. We wrap the function with the decorators as this,
What will happen if we set maxsize parameter to None in lru_cache?
lru_cache has two arguments
The maxsize argument says how many entries we want to consider. If maxsize=1, we will cached only 1 argument/output pair, if it is 2, we will cache 2 arguments/output pair. If maxsize is set to None, the LRU feature is disabled and the cache can grow without bound. The LRU feature performs best when maxsize is a power-of-two.
typed by default is set to False. If typed is set to true, function arguments of different type will be cached separately. That means, sample_function(10) and sample_function(10.0) will be treated as distinct calls with distinct results.
If we set the parameter maxsize toNone, the cache will grow forever for each new different argument pair. The cache size will grow in an unbounded fashion and the system will crash with a MemoryError. On the other hand, if we do not explicitly specify the maxsize parameter in lru_cache then the default value 128 will be used.
How lru_cache works in Python?
When a function wrapped with lru_cache is called, it saves the output and the arguments.
And next time when the function is called, the arguments are searched and, if the
same argument is found, the previously saved output is returned without doing
any calculation.
Example: Using LRU Cache to print Fibonacci Series
Fibonacci Series is series of numbers in which each number is the sum of two preceding numbers. For example 1, 1, 2, 3, 5, 8 etc is a simple Fibonacci Series as 1+1 = 2, 1+2 = 3 and so on. Mathematically It can be defined as
Let’s use timeit to compare the time taken by the function when we use lru_cache and when we don’t use the lru_cache.
Next we will wrap the function using the lru_cache decorator. Doing this, the fibonacci series will be calculated super fast. When we found the outcome of fibo(10), its output will be stored and next when we need to calculate fibo(11) the outcome of fibo(10) will be simpley added. If we don’t have used the lru_cache fibo(10) need to be calculated again.
Using the cache_info() method we can see the cache stats too. This method is used to measure the effectiveness of the cache and tune the maxsize parameter. It returns a named tuple showing hits, misses, maxsize and currsize.
Example: Fetching a webpage
In this example, we will fetch a webpage using urllib,
This function takes url as an argument and fetch the html from particular web address.
If we run the function one time, it will take around 2 seconds and if we run the function
next it will again take around 2 seconds. Imagine we have to run the function for thousands
of time. In such case, we have to wait for very long time.
To our rescue, we got lru_cache.
This function is exactly same as above but it is wrapped with lru_cache which caches the url/output pair. So if the same url is given the output will be cached. That is why when we run the function for 1st time it will take 2 seconds but when we run next, it will give output instantly. We can see the difference in the picture below.
Try lru_cache on your own python interpreter and see the magic. Some tips:
Functools – сила функций высшего порядка в Python
В стандартной библиотеке Python есть множество замечательных модулей, которые помогают делать ваш код чище и проще, и functools определенно является одним из них. В этом модуле есть множество полезных функций высшего порядка, которые можно использовать для кэширования, перегрузки, создания декораторов и в целом для того, чтобы делать код более функциональным, поэтому давайте отправимся на экскурсию по этому модулю и посмотрим, что он может нам предложить.
Кэширование
Давайте начнем с самых простых, но довольно мощных функций модуля functools . Начнем с функций кэширования (а также декораторов) — lru_cache , cache и cached_property . Первая из них — lru_cache предоставляет кэш последних результатов выполнения функций, или другими словами, запоминает результат их работы:
В этом примере мы делаем GET-запросы и кэшируем их результаты (до 32 результатов) с помощью декоратора @lru_cache . Чтобы увидеть, действительно ли кэширование работает, можно проверить информацию о кэше функции, с помощью метода cache_info , который показывает количество удачных и неудачных обращений в кэш. Декоратор также предоставляет методы clear_cache и cache_parameters для аннулирования кэшированных результатов и проверки параметров, соответственно.
Если вам нужно более детализированное кэширование, можете включить необязательный аргумент typed=true , что позволяет кэшировать аргументы разных типов по отдельности.
Еще один декоратор для кэширования в functools – это функция, которая называется просто cache . Она является простой оберткой lru_cache , которая опускает аргумент max_size , уменьшая его, и не удаляет старые значения.
Еще один декоратор, который вы можете использовать для кэширования – это cached_property . Как можно догадаться из названия, он используется для кэширования результатов атрибутов класса. Механика очень полезная, если у вас есть свойство, которое дорого вычислять, но оно при этом остается неизменным.
Этот простой пример показывает. Как можно использовать cached_property , например, для кэширования отрисованной HTML — страницы, которая должна снова и снова показываться пользователю. То же самое можно сделать для определенных запросов к базе данных или долгих математических вычислений.
Еще одна прелесть cached_property в том, что он запускается только при поиске, поэтому позволяет нам менять значение атрибута. После изменения атрибута закэшированное ранее значение меняться не будет, вместо этого будет вычислено и закэшировано новое значение. А еще кэш можно очистить, и все, что нужно для этого сделать – это удалить атрибут.
Я хочу закончить этот раздел предостережением относительно всех вышеперечисленных декораторов – не используйте их, если у вашей функции есть какие-то побочные эффекты или если она при каждом вызове создает изменяемые объекты, поскольку это явно не те функции, которые вы захотите кэшировать.
Сравнение и упорядочивание
Вероятно, вы уже знаете, что в Python можно реализовать операторы сравнения, такие как < , >= или == , с помощью lt , gt или eq . Однако, может быть довольно неприятно реализовывать каждый из eq , lt , le , gt или ge . К счастью, в functools есть декоратор @total_ordering , который может помочь нам в этом, ведь все, что нам нужно реализовать – это eq и один из оставшихся методов, а остальные декоратор сгенерирует автоматически.
Так мы можем реализовать все расширенные операции сравнения несмотря на то, что руками написали только eq и lt . Наиболее очевидным преимуществом является удобство, которое заключается в том, что не нужно писать все эти дополнительные волшебные метода, но, вероятно, важнее здесь уменьшение количества кода и его лучшая читаемость.
Перегрузка
Вероятно, всех нас учили, что перегрузки в Python нет, но на самом деле есть простой способ реализовать ее с помощью двух функций из functools , а именно singledispatch и/или singledispatchmethod . Эти функции помогают нам реализовать то, что мы бы назвали алгоритмом множественной диспетчеризации, который позволяет динамически типизированным языкам программирования, таким как Python, различать типы во время выполнения.
Учитывая, что перегрузка функций сама по себе является довольно обширной темой, я посвятил отдельную статью singledispatch и singledispatchmethod . Если вы хотите узнать о теме побольше, вы можете прочитать о ней здесь.
Partial
Мы все работаем с различными внешними библиотеками или фреймворками, многие из которых предоставляют функции и интерфейсы, требующие от нас передачи коллбэков, например, для асинхронных операций или прослушивания событий. В этом нет ничего нового, но что, если нам нужно еще и передать некоторые аргументы вместе с коллбэком. Именно здесь и пригодится functools.partial . Можно использовать partial для замораживания некоторых (или всех) аргументов функции, создавая новый объект с упрощенной сигнатурой функции. Запутались? Давайте рассмотрим несколько примеров из практики:
Код выше показывает, как можно использовать partial для передачи функции ( output_result ) вместе с аргументом ( log=logger ) в качестве коллбэка. В этом случае мы воспользуемся multiprocessing.apply_async , которая асинхронно вычисляет результат функции ( concat ) и возвращает результат коллбэка. Однако apply_async всегда будет передавать результат в качестве первого аргумента, и, если мы хотим включить какие-то дополнительные аргументы, как в случае с log=logger , нужно использовать partial .
Мы рассмотрели достаточно продвинутый вариант использования, а более простым примером может быть обычное создание функции, которая пишет в stderr вместо stdout :
С помощью этого простого трюка мы создали новую callable-функцию, которая всегда будет передавать file=sys.stderr в качестве именованного аргумента для вывода, что позволяет нам упростить код и не указывать значение именованного аргумента каждый раз.
И последний хороший пример. Мы можем использовать partial в связке с малоизвестной функцией iter , чтобы создать итератор, передав вызываемый объект и sentinel в iter , что можно применить следующим образом:
Обычно при чтении файла мы хотим итерироваться по строкам, но в случае бинарных данных нам может понадобиться итерироваться по записям фиксированного размера. Сделать это можно, создав вызываемый объект с помощью partial , который считывает указанный чанк данных и передает их в iter для создания итератора. Затем этот итератор вызывает функцию чтения до тех пор, пока не дойдет до конца файла, всегда беря только указанный объем чанка ( RECORD_SIZE ). Наконец, по достижении конца файла возвращается значение sentinel (b») и итерация прекращается.
Декораторы
Мы уже говорили о кое-каких декораторах в прошлых разделах, но не о декораторах для создания еще большего количества декораторов. Одним из таких декораторов является functools.wraps . Чтобы понять зачем он нужен, давайте просто посмотрим на пример:
Этот пример показывает, как можно реализовать простой декоратор. Мы оборачиваем функцию, выполняющую определенную задачу ( actual_func ), внешним декоратором, и она сама становится декоратором, который затем можно применить к другим функциям, например, как в случае с greet . При вызове функции greet вы увидите, что она выводит сообщения как от actual_func , так и свои собственные. Вроде выглядит нормально, не так ли? Но что будет, если мы сделаем так:
Когда мы вызываем имя и документацию декорированной функции, мы понимаем, что они были заменены значениями из функции декоратора. Это плохо, поскольку мы не можем перезаписывать все наши имена функций и документацию каждый раз при использовании какого-либо декоратора. Как же решить эту проблему? Конечно же, с помощью functools.wraps :
Единственная задача функции wraps – это копирование имени, документации, списка аргументов и т.д., для предотвращения перезаписи. Если учесть, что wraps – это тоже декоратор, можно просто добавить его в нашу actual_func , и проблема решена!
Reduce
Последнее, но не менее важное в модуле functools – это reduce . Возможно, из других языков, вы можете знать ее как fold (Haskell). Эта функция берет итерируемый объект и сворачивает (складывает) все его значения в одно. Применений этому множество, например:
Как видно из кода, reduce может упростить или сжать код в одну строку, которая в противном случае была бы намного длиннее. С учетом сказанного злоупотреблять этой функцией только ради сокращения кода, делать ее «умнее» — обычно плохая идея, поскольку она быстро становится страшной и нечитаемой. По этой причине, на мой взгляд, пользоваться ей стоит экономно.
А если помнить, что reduce частенько сокращает все до одной строки, ее отлично можно скомбинировать с partial :
И, наконец, если вам нужен не только итоговый «свернутый» результат, то вы можете использовать accumulate – из другого замечательного модуля itertools . Для вычисления максимума ее можно использовать следующим образом:
Заключение
Как видите, в functools есть множество полезных функций и декораторов, которые могут облегчить вам жизнь, но это лишь верхушка айсберга. Как я говорил вначале, в стандартной библиотеке Python есть множество функций, которые помогают писать код лучше, поэтому, помимо функций, которые мы здесь рассмотрели, вы можете обратить внимание на другие модули, такие как operator или itertools (мою статью об этом модуле вы можете прочитать здесь или просто отправляйтесь в Python Module Index и изучите все, на что обратите внимание, и я просто уверен, что вы найдете там что-то полезное.
Всех желающих приглашаем на онлайн-интенсив «Быстрая разработка JSON API приложений на Flask». На этом уроке мы:
— Познакомимся со спецификацией JSON API;
— Узнаем, что такое сериализация/десериализация данных;
— Узнаем, что такое marshmallow и marshmallow-jsonapi;
— Познакомимся со Swagger;
— Посмотрим на обработку и выдачу связей.