Несмотря на то, что кэширование может быть чрезвычайно полезным для ускорения вычисления рекуррентных отношений, оно не решает проблему переполнения стека вызовов. Например, в ходе вычисления 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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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), …
В качестве функции упорядочивания можно взять
|
1 2 3 4 5 6 7 8 9 10 11 |
# прямое преобразование пространства аргументов 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|).
Функция упорядочивания в этом случае будет проще:
|
1 2 3 4 |
def edit_distance(s, t): rect = lambda x, y: x*(len(t) + 1) + y invrect = lambda i: divmod(i, len(t) + 1) # другой код |
Обобщенный декоратор с использованием прямого и обратного преобразования пространства аргументов будет выглядеть так:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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(), при вызовах которого возвращаются элементы некоторой последовательности. Пусть есть итератор, который возвращает упорядоченные наборы аргументов для рекуррентного отношения; тогда декоратор динамического программирования приобретает вид
|
1 2 3 4 5 6 7 8 9 10 11 12 |
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().
|
1 2 3 4 5 6 7 8 9 |
def nat(): value = 1 while True: yield value value += 1 generator = nat() print [generator.next() for i in range(10)] # напечатает [1, 2, …, 10] |
С использованием генератора вычисление биномиальных коэффициентов приобретает следующий вид:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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.