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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *