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

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

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

Или в виде декоратора(про декораторы подробней в Декораторы функций в Python)

def memoize(f):
    cache = {}

    def decorate(*args):
        if args in cache:
            return cache[args]
        else:
            cache[args] = f(*args)
            return cache[args]
    return decorate

# 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 mem_fib(n):
    if n < 2:
        return n
    return mem_fib(n-2) + mem_fib(n-1)

print('mem_fib(20) =', mem_fib(20))

И хорошая новость в том, что в стандартной библиотеке functools уже отлично реализован подобный декоратор lru_cache.
LRU расшифровывается как Least Recently Used.

from functools import lru_cache


@clock
@lru_cache()
def mem_fib(n):
    if n < 2:
        return n
    return mem_fib(n-2) + mem_fib(n-1)

print('mem_fib(20) =', mem_fib(20))

lru_cache имеет два необязательных аргумента.
maxsize - это кол-во хранимых результатов.
typed - при равном true например значения 1 и 1.0 будут считаться разными.


Теперь про каррирование или карринг(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)

Но обычно используют функцию которая способна создать каррированые функции из обычных.
Такая возможность есть у 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, решает проблему замыкания в цикле(Область видимости и замыкания в Python)

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=', ')