Несмотря на то, что кэширование может быть чрезвычайно полезным для ускорения вычисления рекуррентных отношений, оно не решает проблему переполнения стека вызовов. Например, в ходе вычисления n-го числа Фибоначчи по формуле
стек будет содержать n вызовов F(n - 1), F(n - 2), …, F(1), F(0). Это означает, что при значениях n около 1000 стек вызовов Python исчерпается, возбудив ошибку времени выполнения (RuntimeError).
Для того чтобы избежать переполнения стека, можно воспользоваться техникой динамического программирования. В широком смысле динамическое программирование означает, что решение задачи зависит от решения ограниченного числа подзадач меньшего размера; очевидно, это утверждение справедливо для рекуррентных отношений. Вместе с тем, зачастую под динамическим программированием подразумевается частный способ его реализации, при котором вычисления производятся «снизу вверх» (bottom-up approach). Это означает, что сначала вычисляются простые задачи, а затем на их основе агрегируются решения более сложных задач. Именно этот подход позволяет избавиться от рекурсии и, следовательно, переполнения стека.
Динамическое программирование широко используется в биоинформатике, прежде всего для выравнивания биополимеров (участков ДНК и белков). В системе Rosalind.info выравниванию посвящены задачи EDIT, EDTA, GLOB, LOCA, GAFF, LAFF, OSYM, KSIM и другие. Другое применение динамического программирования — распознавание с использованием скрытых марковских моделей (алгоритм Витерби).
Как и в случае кэширования, динамическое программирование может быть реализовано в Python с применением шаблонов императивного программирования, но больший интерес представляет использование функционального подхода, в частности, декораторов и генераторов.
Значение n-го числа Фибоначчи зависит от значений чисел с меньшим индексом F(m), m < n; если их значения известны, то F(n) вычисляется тривиально. Следовательно, для вычисления n-го числа Фибоначчи достаточно определить в порядке возрастания все предыдущие числа. Декоратор, соответствующий этой логике, напоминает декоратор @cached:
def dp(fn):
cache = []
def dp_fn(n):
if len(cache) <= n:
for i in range(len(cache), n + 1):
cache.append(fn(i))
return cache[n]
return dp_fn
@dp
def fib(n):
if n == 0: return 0
if n == 1: return 1
return fib(n – 2) + fib(n – 1)
Ключевой момент: при вычислении fn(i) в цикле на строке 6 все предыдущие значения функции уже находятся в кэше; таким образом, функция fn не будет вычисляться дважды для одного и того же значения аргумента.
Несколько аргументов
Приведенный декоратор годится для вычисления функций одного целочисленного неотрицательного аргумента (например, чисел Фибоначчи или Каталана). В биоинформатике, между тем, часто используются рекуррентные формулы с несколькими аргументами:
Биномиальные коэффициенты C(n, k) — количество способов выбрать подмножество размера k из n различимых объектов.
Функция, возникающая при определении расстояния Левенштейна (англ. edit distance) между двумя строками s и t и равная расстоянию между префиксами этих строк определенной длины.
(Аналогичные функции возникают при выравнивании биологических последовательностей.)
Для обобщения декоратора @dp можно определить взаимно однозначное отображение I между пространством аргументов рекуррентно заданной функции F и целыми неотрицательными числами, которое упорядочивает аргументы в том порядке, в котором нужно вычислять F:
Для биномиальных коэффициентов наборы аргументов можно упорядочить в виде треугольника:
(0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2), (3, 0), (3, 1), (3, 2), (3, 3), …
В качестве функции упорядочивания можно взять
# прямое преобразование пространства аргументов
def pack_tri(n, k):
return n * (n + 1) / 2 + k
# обратное преобразование
def unpack_tri(i):
n = math.floor(math.sqrt(idx * 2))
n = int(n)
if n * (n + 1) / 2 > idx:
n -= 1
return (n, idx - n * (n + 1) / 2)
При вычислении расстояния Левенштейна наборы аргументов упорядочиваются в виде прямоугольника:
( 0, 0), ( 0, 1), …, ( 0, |t| - 1), ( 0, |t|), ( 1, 0), ( 1, 1), …, ( 1, |t| - 1), ( 1, |t|), …, (|s|, 0), (|s|, 1), …, (|s|, |t| - 1), (|s|, |t|).
Функция упорядочивания в этом случае будет проще:
def edit_distance(s, t):
rect = lambda x, y: x*(len(t) + 1) + y
invrect = lambda i: divmod(i, len(t) + 1)
# другой код
Обобщенный декоратор с использованием прямого и обратного преобразования пространства аргументов будет выглядеть так:
def lindp(pack = lambda i: i, unpack = lambda i: (i,)):
# pack — прямое преобразование, unpack — обратное
def decorate(fn):
cache = []
def dp_fn(*args):
n = pack(*args)
if len(cache) <= n:
for i in range(len(cache), n + 1):
cache.append(fn(*unpack(i)))
return cache[n]
return dp_fn
return decorate
# Использование с биномиальными коэффициентами
@lindp(pack = pack_tri, unpack = unpack_tri)
def binc(n, k):
if k == 0 or k == n: return 1
return binc(n - 1, k - 1) + binc(n - 1, k)
Генераторы
Хоть декоратор @lindp и работает, он не очень питоничен. Его можно улучшить за счет использования итераторов. Итератор — это объект с методом next(), при вызовах которого возвращаются элементы некоторой последовательности. Пусть есть итератор, который возвращает упорядоченные наборы аргументов для рекуррентного отношения; тогда декоратор динамического программирования приобретает вид
def dp(iterator):
def decorate(fn):
cache = dict()
def dp_fn(*args):
if args not in cache:
while True:
i = iterator.next()
cache[i] = fn(*i)
if i == args: break
return cache[args]
return dp_fn
return decorate
Обычные итераторы коллекций, созданные с помощью функции iter(…), не совсем годятся для перебора наборов аргументов — как-никак, количество таких наборов бесконечно; сколько их понадобится, неизвестно до вызова функции. К счастью, в Python есть средство для создания «бесконечных» итераторов — генераторы. Генератор выглядит как функция, в которой значения возвращаются с помощью ключевого слова yield вместо return. При каждом вызове метода next() код генератора выполняется до первой инструкции yield; аргумент этой инструкции и есть результат, возвращаемый next(). Затем состояние функции-генератора сохраняется и его выполнение прекращается до следующего вызова метода next().
def nat():
value = 1
while True:
yield value
value += 1
generator = nat()
print [generator.next() for i in range(10)]
# напечатает [1, 2, …, 10]
С использованием генератора вычисление биномиальных коэффициентов приобретает следующий вид:
def tri():
# Генерирует последовательность
# (0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2), ...
value = 0, 0
while True:
yield value
n, k = value
value = (n, k + 1) if k < n else (n + 1, 0)
@dp(iterator = tri())
def binc(n, k):
if k == 0 or k == n: return 1
return binc(n - 1, k - 1) + binc(n - 1, k)
Бочка дегтя
Несмотря на то, что имплементация рекуррентных отношений в функциональном стиле красива, полученные с их помощью решения работают в Python существенно медленнее, чем императивные реализации (аналогичные реализациям, например, в Java или C++). В случае с кэшированием не всегда ясно, как можно реализовать метод по-другому; для динамического программирования последовательность вычисления рекуррентной функции известна, а значит, проблем с императивной реализацией вычислений «снизу вверх» не должно возникать.
Таким образом, в отличие от кэширования, реализация динамического программирования при помощи декораторов и генераторов носит скорее теоретическую ценность — показать возможности Python.