Мемоизация и каррирование (Python)

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

Мемоизация (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

Время работы будет очень быстро расти при увеличении числа которое нужно найти, плюс возможна ошибка 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=', ')

На сегодня все. Спасибо!