11

Повторное использование

вычислений

П ОВТОРНОЕ ИСПОЛЬЗОВАНИЕ ВЫЧИСЛЕНИЙ (COMPUTATIONAL REUSE) представляет собой методику, когда промежуточные данные (т.е. данные, не являющиеся окончательным выводом функции) сохраняются и используются для более эффективного выполнения других вычислений. Повторное использование вычислений имеет долгую историю в компьютерной науке, особенно в компьютерной графике и вычислительной математике. Однако не стоит опасаться столь сложного технического применения данной методики; повторное использование представляет собой просто еще одну форму кэширования.

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

Повторное использование вычислений представляет собой форму кэширования, в которой основное внимание уделено очень мелким блокам данных. Вместо кэширования целых компонентов приложения для повторного использования вычислений в основном кэшируются отдельные объекты или данные, созданные в процессе выполнения какой-либо функции. Часто эти мелкие элементы можно также использовать повторно. Каждая комплексная операция представляет собой объединенный результат множества мелких операций. Если отдельная мелкая операция составляет значительную часть рабочего цикла программы, то оптимизация этой операции посредством кэширования может принести значительный выигрыш в производительности.

Вводный пример: последовательности Фибоначчи

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