Архив за день: Июнь 22, 2015

Rosalind.info — кэширование

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

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

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

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

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

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

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

Читать далее Rosalind.info — кэширование