Привет, уважаемые читатели Хабрахабра. В этой статье попробуем разобраться что такое мемоизация и каррирование, и как эти методы реализованы в стандартной библиотеке Python.
Это способ оптимизации при котором сохраняется результат выполнения функции и этот результат используется при следующем вызове.
Берем рекурсивную реализацию нахождения числа Фибоначчи и смотрим время выполнения.
![image](https://habrastorage.org/getpro/habr/post_images/72a/dd4/66a/72add466aa40d3ab135d53c84ef14e67.png)
Время работы будет очень быстро расти при увеличении числа которое нужно найти, плюс возможна ошибка RecursionError.
Для оптимизации подобного алгоритма хорошо подходит метод мемоизации, то есть сохранение и повторное использования ранние вычисленных значений (но с начало конечно нужно постараться вовсе отказаться от рекурсивного алгоритма).
Или в виде декоратора:
И хорошая новость в том, что в стандартной библиотеке functools уже отлично реализован подобный декоратор lru_cache.
LRU расшифровывается как Least Recently Used.
lru_cache имеет два необязательных аргумента.
maxsize — это кол-во хранимых результатов.
typed — при равном true например значения 1 и 1.0 будут считаться разными.
Мемоизация довольно простая и эффективная практика. Благодаря functools.lru_cache, ей удобно пользоваться в Python. Под капотом у нее словарь в виде хэш-таблицы, соответственно ключ должен реализовать хеширование.
Карринг — это преобразование функции от многих аргументов в набор функций, каждая из которых является функцией от одного аргумента. Мы можем передать часть аргументов в функцию и получить обратно функцию, ожидающую остальные аргументы.
Создадим простую функцию greet, которая принимает в качестве аргументов приветствие и имя:
Небольшое улучшение позволит нам создать новую функцию для любого типа приветствия и передать этой новой функции имя:
А дальше можно сделать это с любым количеством аргументов:
Или вариант с lambda:
Это процесс применения функции к части ее аргументов.
Другими словами, функция, которая принимает функцию с несколькими параметрами и возвращает функцию с меньшим количеством параметров.
Частичное применение преобразует функцию от n аргументов к (x-n), а карринг создает n функций с 1 аргументов.
Такая возможность есть у Python в стандартной библиотеки functools, это функция
partial.
Еще один пример с partial, решает проблему замыкания в цикле:
На сегодня все. Спасибо!
Мемоизация (memoization)
Это способ оптимизации при котором сохраняется результат выполнения функции и этот результат используется при следующем вызове.
Берем рекурсивную реализацию нахождения числа Фибоначчи и смотрим время выполнения.
@clock
def fib(n):
if n < 2:
return n
return fib(n-2) + fib(n-1)
print('fib(20) =', fib(20))
[0.35938287s] fib(20) -> 6765
@clock
def clock(func):
def clocked(*args, **kwargs):
t0 = time.time()
result = func(*args, **kwargs) # вызов декорированной функции
elapsed = time.time() - t0
name = func.__name__
arg_1st = []
if args:
arg_1st.append(', '.join(repr(arg) for arg in args))
if kwargs:
pairs = ['%s=%r' % (k, w) for k, w in sorted(kwargs.items())]
arg_1st.append(', '.join(pairs))
arg_str = ', '.join(arg_1st)
print('[%0.8fs] %s(%s) -> %r' % (elapsed, name, arg_str, result))
return result
return clocked
![image](https://habrastorage.org/getpro/habr/post_images/72a/dd4/66a/72add466aa40d3ab135d53c84ef14e67.png)
Время работы будет очень быстро расти при увеличении числа которое нужно найти, плюс возможна ошибка RecursionError.
Для оптимизации подобного алгоритма хорошо подходит метод мемоизации, то есть сохранение и повторное использования ранние вычисленных значений (но с начало конечно нужно постараться вовсе отказаться от рекурсивного алгоритма).
_fib_cache = {1: 1, 2: 1} # ключ - номер числа, значения - число Фибоначчи
@clock
def mem_fib(n):
result = _fib_cache.get(n)
if result is None:
result = mem_fib(n-2) + mem_fib(n-1)
_fib_cache[n] = result
return result
print('mem_fib(200) =', mem_fib(200))
[0.03125453s] mem_fib(200) -> 280571172992510140037611932413038677189525
Или в виде декоратора:
def memoize(f):
cache = {}
def decorate(*args):
if args in cache:
return cache[args]
else:
cache[args] = f(*args)
return cache[args]
return decorate
# то же самое через lambda
# def memoize(f):
# cache = {}
# return lambda *args: cache[args] if args in cache else cache.update({args: f(*args)}) or cache[args]
# универсальный декоратор для любого количества аргументов
# def memoize(f):
# cache = {}
#
# def decorate(*args, **kwargs):
# key = (tuple(args), hash(tuple(sorted(kwargs.items()))))
# if key not in cache:
# cache[key] = f(*args, **kwargs)
# return cache[key]
#
# return decorate
@clock
@memoize
def fib(n):
if n < 2:
return n
return fib(n-2) + fib(n-1)
print('fib(20) =', fib(20))
И хорошая новость в том, что в стандартной библиотеке functools уже отлично реализован подобный декоратор lru_cache.
LRU расшифровывается как Least Recently Used.
from functools import lru_cache
@clock
@lru_cache()
def fib(n):
if n < 2:
return n
return fib(n-2) + fib(n-1)
print('fib(20) =', fib(20))
lru_cache имеет два необязательных аргумента.
maxsize — это кол-во хранимых результатов.
typed — при равном true например значения 1 и 1.0 будут считаться разными.
Мемоизация довольно простая и эффективная практика. Благодаря functools.lru_cache, ей удобно пользоваться в Python. Под капотом у нее словарь в виде хэш-таблицы, соответственно ключ должен реализовать хеширование.
Теперь про каррирование или карринг(currying)
Карринг — это преобразование функции от многих аргументов в набор функций, каждая из которых является функцией от одного аргумента. Мы можем передать часть аргументов в функцию и получить обратно функцию, ожидающую остальные аргументы.
Создадим простую функцию greet, которая принимает в качестве аргументов приветствие и имя:
def greet(greeting, name):
print(greeting + ', ' + name)
greet('Hello', 'German')
Небольшое улучшение позволит нам создать новую функцию для любого типа приветствия и передать этой новой функции имя:
def greet_curried(greeting):
def greet(name):
print(greeting + ', ' + name)
return greet
greet_hello = greet_curried('Hello')
greet_hello('German')
greet_hello('Ivan')
# или напрямую greet_curried
greet_curried('Hi')('Roma')
А дальше можно сделать это с любым количеством аргументов:
def greet_deeply_curried(greeting):
def w_separator(separator):
def w_emphasis(emphasis):
def w_name(name):
print(greeting + separator + name + emphasis)
return w_name
return w_emphasis
return w_separator
greet = greet_deeply_curried("Hello")("...")(".")
greet('German')
greet('Ivan')
Или вариант с lambda:
greet_deeply_curried = lambda greeting: lambda separator: lambda emphasis: lambda name: print(greeting + separator + name + emphasis)
Частичное применение (partial application)
Это процесс применения функции к части ее аргументов.
Другими словами, функция, которая принимает функцию с несколькими параметрами и возвращает функцию с меньшим количеством параметров.
Частичное применение преобразует функцию от n аргументов к (x-n), а карринг создает n функций с 1 аргументов.
Такая возможность есть у Python в стандартной библиотеки functools, это функция
partial.
from functools import partial
def greet(greeting, separator, emphasis, name):
print(greeting + separator + name + emphasis)
newfunc = partial(greet, greeting='Hello', separator=',', emphasis='.')
newfunc(name='German')
newfunc(name='Ivan')
newfunc2 = partial(greet, greeting='Hello', emphasis='.')
newfunc2(name='German', separator='...')
newfunc2(name='Ivan', separator='..')
Еще один пример с partial, решает проблему замыкания в цикле:
from functools import partial
def makeActions():
acts = []
for i in range(5):
def func(x, y):
return x * y
acts.append(partial(func, y=i))
# acts.append(partial(lambda x, y: x * y, y=i)) # через lambda
# return [partial(lambda x, y: x * y, y=i) for i in range(5)] # через генератор списка
return acts
for act in makeActions():
print(act(1), end=', ')
На сегодня все. Спасибо!