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


image

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

На сегодня все. Спасибо!
Метки:
Поделиться публикацией
Похожие публикации
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 22
  • +2

    Я слышал про присутствие функционального стиля в python и теперь в этом убедился. Спасибо.

    • +2

      Факториал и Фибоначчи — близнецы-братья.
      Кто более матери-истории ценен?
      Мы говорим Факториал — подразумеваем (и далее по тексту классика)

      • +4
        Я открыл, что Китай и Испания совершенно одна и та же земля, и только по невежеству считают их за разные государства. Я советую всем нарочно написать на бумаге Испания, то и выйдет Китай.
        Н.В.Гоголь, «Записки сумасшедшего»
      • 0
        Ваша функция называется factorial, а вычисляет числа Фибоначчи.

        В остальном поддерживаю вас и статью. Будет интересно, если продолжите и расскажите о других способах оптимизации, о применении мемоизации, например, в динамическом программировании и т.д.
        • 0
          Хотел пошутить по поводу факториала и фибоначчи, но господа выше уже успели. В остальном интересно, примеры весьма наглядные, хоть и игрушечные.
          • 0
            Я мог бы написать, что это был тест на внимательность, но нет…
            Названия функций исправил. Всем спасибо!
            • 0
              Это, безусловно, тест на внимательность:
              print('200! =', mem_fib(200))
              
            • 0
              Большое спасибо за то, что привели примеры реализации одной и той же функции как в обычном процедурном стиле, так и с помощью лямбд. Так гораздо понятнее для новичка в функциональном программировании — не так страшно :)
              • +1
                С использованием lru_cache можно еще написать синглтон «для ленивых»:

                from functools import lru_cache
                
                @lru_cache(maxsize=None)
                class S: pass
                

                • 0
                  У меня пятничный утренний неunderstand.
                  Поясните, пж!
                  • 0
                    If maxsize is set to None, the LRU feature is disabled and the cache can grow without bound

                    Так что каждый раз вы будете получать один и тот же экземпляр класса.
                    • 0
                      Как это связано? Если конструктор без аргументов, нужен кэш размера 1.
                      • 0
                        Согласен, что для конструктора без аргументов достаточно кеша размера 1.
                        None будет работать для конструктора с любым количеством аргументов.

                        Нужно еще оговориться, что так ни в коем случае не нужно писать синглтоны, конечно.
                • 0

                  Memorize/lru_cashe — вещь понятная(понятно для чего).
                  А вот в чем смысл картирование — не совсем понял к чему применит можно...?

                  • +2
                    Вообще, partial в питоне — это не каррирование, а частичное применение, это разные вещи.
                    Например, вот каррирование в OCaml:
                    # let add x y = x + y;;
                    val add : int -> int -> int = <fun>
                    # let add2 = add 2;;
                    val add2 : int -> int = <fun>
                    # let sum = add2 3;;
                    val sum : int = 5
                    

                    А вот частичное применение в питоне:
                    >>> add = lambda x, y: x + y
                    >>> add    
                    <function <lambda> at 0x7f78aba64aa0>
                    >>> add2 = partial(add, 2)
                    >>> add2 
                    <functools.partial object at 0x7f78aba57520>
                    >>> sum = partial(add2, 3)
                    >>> sum
                    <functools.partial object at 0x7f78aba577e0>
                    >>> sum()
                    5
                    

                    Т.е. мы получаем всё ещё функцию, а не результат, более того, мы можем навесить ещё один partial с какими-нибудь аргументами на функцию sum и узнаем об ошибке только в момент вызова полученной новой функции.

                    А нужно это во многих местах: например, если у какого-нибудь объекта (кнопки, сокета, whatever) подписка на событие требует передать функцию-обработчик, принимающую один аргумент, например, событие, а у вас более сложный обработчик, которому вы хотите передавать больше информации:
                    def complex_handler(obj, logger_name, times_to_log, event):
                        for _ in range(times_to_log):
                            logging.getLogger(logger_name).info("got event from %s: %s", obj, event)
                    obj1.subscribe(partial(complex_handler, obj1, "incoming", 3))
                    obj2.subscribe(partial(complex_handler, obj2, "outgoing", 5))
                    
                    • 0
                      Вы правы, carrying и partial application — это разные вещи.
                      Не хотел в небольшой статье для начинающих вводить еще один термин и описывать разницу между carrying и partial application. Но вероятно это была ошибка. Внес корректировки.
                      Спасибо.
                    • 0
                      Для не чисто функциональных языков, это абсолютно не обязательная штука. Если нет точного понимания, что это наиболее эффективный способ, то всегда можно найти другое решение(особенно если с вашим кодом будут работать люди с разной компетенцией).
                      Достаточно понимать общий смысл, что бы возникало немного меньше вопросов читая чужой код.
                      48 примеров
                      • 0
                        По личному опыту — partial полезен там, где есть работа с callback'ами. Т.е. некий API хочет получить от вас функцию, чтобы потом ее использовать, а у вас уже и функция готовая есть, но беда в том, что ей нужны аргументы. А модуль, принимающий вашу функцию, этих аргументов ей не передает. Тут нас выручает partial, он как-бы фиксирует значения некоторого количества аргументов (на самом деле, создает обертку вокруг вашей функции). Если вам не нужно работать с callback'ами, то скорее всего и partial не пригодится.
                        Да, и как уже отметили выше, каррирование (carrying) и частичное применение (partial application) — это разные вещи.
                      • 0

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


                        Примеры

                        На питоне


                        def sqr(arg): return arg * arg
                        def is_even(arg): return arg % 2 == 0
                        xs = range(1, 4)
                        list(map(sqr, filter(is_even, xs)))
                        >>> [4, 16]

                        Не на питоне, все функции каррированы


                        let sqr = arg * arg
                        let is_even arg = arg % 2 == 0
                        xs = range 4
                        list map sqr filter is_even xs
                        // или с пайп оператором
                        list_of_squared_even xs = xs |> filter is_even |> map sqr |> list

                        Если читать справа налево то даже читаемо


                        То же самое, но подробней


                        let sqr = arg * arg
                        let is_even arg = arg % 2 == 0
                        xs = range 1 4
                        
                        each_square = map sqr  # -> returns func<iterable, iterable>
                        filter_even = filter is_even  # -> returns func<iterable, iterable>
                        list_of_squared_even = each_square filter_even # -> returns func<iterable, iterable>
                        list_of_squared_even xs
                        >>> [4, 16]

                        Если не ошибаюсь так работает F#, поправьте если не прав

                        • 0

                          Не хватает результатов выполнения функций. Было бы удобнее. В целом: спасибо за статью.

                          • 0
                            В последнем примере у вас не генератор, а генерация списка. Генератор будет выглядеть примерно так:
                            def makeActions():
                                acts = []
                                for i in range(5):
                                    def func(x, y):
                                        return x * y
                                    yield partial(lambda x, y: x * y, y=i)
                            • 0
                              Речь про list comprehension, если не ошибаюсь в русской терминологии это списковое включение/абстракция списков/генерация списков/генератор списка.

                              Решение через генераторы:
                              def generator_expression():
                                  return (lambda x: x * i for i in range(5))
                              
                              def generator():
                                  for i in range(5):
                                      yield lambda x: x * i
                              

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