Во многих задачах биоиноформатики возникает проблема вычисления рекуррентных отношений. Простейший пример рекуррентного отношения — числа Фибоначчи, задаваемые уравнениями

В рамках биоинформатики числа Фибоначчи и подобные используются для описания динамики популяций (числа F(n) равны размеру популяции при условии бессмертия индивидов). Обобщения чисел Фибоначчи рассматриваются в задачах Rosalind FIB и FIBD.

Другой пример рекуррентного отношения — числа Каталана, которые можно задать рекуррентным отношением

C(n) равняется количеству правильных скобочных последовательностей длины 2n. В биоинформатике подобные числам Каталана формулы возникают в задачах сворачивания молекул РНК (см. задачи Rosalind CAT, MMCH, PMCH).

Простейший способ вычисления рекуррентных отношений — использование рекуррентных вызовов функций — на практике редко приводит к эффективным решениям:

• Значение функции для одного и того же набора аргументов при рекуррентных вызовах может вычисляться несколько раз.
• Глубина стека вызовов в современных системах выполнения хоть и велика, но все же ограничена.

Для борьбы с первой проблемой можно использовать кэширование (другое название — мемоизация) результатов вычислений. Справиться с обеими проблемами позволяет динамическое программирование. В рамках Python оба этих средства могут быть реализованы как при помощи императивной парадигмы (то есть так, как в C++ или Pascal), так и с использованием шаблонов функционального программирования.

Кэширование заключается в запоминании вычисленных значений функции для заданных наборов аргументов. В Python для хранения значений естественно использовать словарь (dict).

def fib(n):
    if n not in fib._cache:
        fib._cache[n] = fib(n - 1) + fib(n - 2)
    return fib._cache[n]

# Функции в Python могут хранить произвольные атрибуты
fib._cache = dict()

У такого подхода есть недостатки: программа обрастает инструкциями (в том числе глобальными), в то время как их суть неизменна практически для любой кэшируемой функции. Альтернативный подход состоит в использовании декораторов Python. Декоратор — функция, которая получает на вход функцию и выдает ее после определенного преобразования. Для указания декораторов используется символ @, как в Java.

def decorator(fn):
    def transformed_fn(...):
        # преобразовать функцию fn
    return transformed_fn

@decorator
def foo(...):
    # код функции

# эквивалентный код
def foo(...):
    # код функции
foo = decorator(foo)

При написании декораторов в полной мере раскрываются возможности Python как функционального языка программирования. Сами декораторы возможны, поскольку в Python есть функции первого класса (англ. first class functions), в отличие от, например, Java. Кроме того, для преобразования функций в декораторах обычно используются вложенные декларации функций и замыкания (англ. closure). Это относится и к декоратору кэширования:

def cached(fn):
    cache = dict()
    def cached_fn(*args):
        if not args in cache:
            cache[args] = fn(*args)
        return cache[args]
    return cached_fn

Кэшированная функция cached_fn определяется заново при каждом вызове декоратора; функция fn доступна внутри определения за счет замыкания. Таким образом, декоратор можно привязать к нескольким функциям программы. С помощью «сборки» аргументов функции с помощью синтаксиса fn(*args) становится возможным кэшировать функции с произвольным числом аргументов.

Помимо глобальных функций, декораторы можно применять и к методам классов. Поскольку нестатические методы класса вызываются с неявным первым параметром self, который соответствует экземпляру класса, кэширование будет осуществляться отдельно для каждого экземпляра (если только не переопределить операцию их равенства).

class RecurrentSum(object):
    '''
    Общий класс для последовательностей, задающихся
    рекуррентной формулой
        F(i) = F(i - 1) + F(i - 2) + ... + F(i - k).
    '''

    def __init__(self, count):
        self.count = count

    # Декораторы работают со специальными методами
    # (в данном случае — индексированием).
    @cached
    def __getitem__(self, n):
        if n < self.count: return 1
        sum = 0
        for i in range(max(0, n - self.count), n):
            sum += self[i]
        return sum

fib = RecurrentSum(2) # числа Фибоначчи
trib = RecurrentSum(3) # "числа трибоначчи"

Проблемы с приведенным декоратором могут возникнуть, если аргументы функции не хэшируются, например, если это множества (set) или списки (list). В этом случае не будет хэшироваться и набор аргументов в целом, значит, его нельзя использовать в качестве ключа для словаря cache. Решить эту проблему можно, если ввести дополнительную функцию для приведения аргументов к хэшируемому виду:

def cache(fn):
    cache = dict()
    def cached_fn(*args):
        mapped_args = mapargs(*args)
        if not mapped_args in cache:
            cache[mapped_args] = fn(*args)
        return cache[mapped_args]
    return cached_fn

Использование функции mapargs позволяет игнорировать аргументы функции или ввести нетривиальную операцию их сравнения; в общем, она достаточно полезна. В декоратор эту функцию можно передать при помощи использования параметрического синтаксиса:

def decorator(...):
    def decorate(fn):
        # объявление обычного декоратора на основе аргументов
    return decorate

@decorator(...)
def foo(...):
    # код функции

# эквивалентный код
def foo(...):
    # код функции
foo = decorator(...)(foo)

Параметрический декоратор, в отличие от обычного, принимает произвольные аргументы (а не функцию) и создает на их основе обычный декоратор.

def cached(mapargs = lambda *args: args):
    def decorate(fn):
        # код простого декоратора из предыдущего листинга
    return decorate

# использование c функцией отображения по умолчанию
@cached()
def fib(n): 
    ...
# использование с пользовательской функцией mapargs
@cached(mapargs = lambda x, y, z: x + y + z)
def some_function(x, y, z):
    ...

Единственный недостаток полученного декоратора: теперь его нельзя использовать в форме простого декоратора, то есть без скобок после названия. Это поправимо, если ввести использовать дополнительный декоратор (декоратор-inception :-).

def noargs(decorator):
    ''' Декоратор, позволяющий использовать форму без аргументов
        для параметричексих декораторов. '''

    def noarg_fn(*args, **kvargs):
        if len(args) == 1 and callable(args[0]) and len(kvargs) == 0:
            # Вызван декоратор без аргументов;
            # args[0] - преобразуемая функция
            return decorator()(args[0])
        else:
            return decorator(*args, **kvargs)
    return noarg_fn

# Пример использования
@noargs
def cached(...):
    # объявление параметрического декоратора кэширования

@cached
def foo(...):
    ...
# эквивалентно
@cached()
def foo(...):
    ...

Тип вызова декоратора определяется по типу первого позиционного аргумента: если это функция, то считается, что используется форма без аргументов. Эта проверка не всегда работает корректно — первый аргумент самого декоратора может тоже иметь тип функции (в частности, это так для декоратора кэширования). В таком случае следует задавать этот аргумент с помощью пары «ключ — значение»; как мне кажется, эта форма записи аргументов более естественна для параметрических декораторов.

@noargs
def cached(mapargs = lambda *args: args):
    ...

# Работает некорректно
@cached(lambda s: frozenset(s))
def foo(s):
    ...

# OK
@cached(mapargs = lambda s: frozenset(s))
def foo(s):
    ...

Ссылки

• Демонстрация декораторов и кэширования в Python.