Предварительный расчет
В алгоритмах предварительные вычисления — это действие по выполнению начальных вычислений перед временем выполнения для создания таблицы поиска , которая может использоваться алгоритмом, чтобы избежать повторных вычислений при каждом его выполнении. Предварительные вычисления часто используются в алгоритмах, которые зависят от результатов дорогостоящих вычислений, не зависящих от входных данных алгоритма. Тривиальным примером предварительного вычисления является использование жестко запрограммированных математических констант, таких как π и e , вместо вычисления их аппроксимаций с необходимой точностью во время выполнения.
В базах данных термин « материализация » используется для обозначения хранения результатов предварительного вычисления [1] [2] , например, в материализованном представлении . [3] [4]
Предварительное вычисление набора промежуточных результатов в начале выполнения алгоритма часто может существенно повысить эффективность алгоритма . Это становится выгодным, когда один или несколько входов ограничены достаточно малым диапазоном, чтобы результаты можно было сохранить в блоке памяти разумного размера. Поскольку временная сложность доступа к памяти по существу постоянна (за исключением задержек кэширования ), любой алгоритм с компонентом, который имеет эффективность ниже постоянной в небольшом диапазоне входных данных, может быть улучшен путем предварительного вычисления значений. В некоторых случаях эффективные алгоритмы аппроксимации могут быть получены путем вычисления дискретного подмножества значений и интерполяции для промежуточных входных значений, поскольку интерполяция также является линейной операцией.
До появления компьютеров распечатанные справочные таблицы значений использовались людьми для ускорения ручных вычислений сложных функций, например, в тригонометрических таблицах , таблицах логарифмов и таблицах функций статистической плотности [5] . Школьников часто учат запоминать « таблицы умножения », чтобы избежать вычислений наиболее часто используемых чисел (до 9 х 9 или 12 х 12). Уже в 493 году нашей эры Викторий Аквитанский написал таблицу умножения из 98 столбцов, которая давала ( римскими цифрами) произведение каждого числа от 2 до 50 раз, а строки представляли собой «список чисел, начинающийся с одной тысячи, убывающий по сотням до ста, затем по убыванию по десяткам до десяти, затем по единицам до единицы, а затем дроби вниз до 1/144" [6]
Даже современные компьютерные реализации цифровых тригонометрических функций часто используют предварительно вычисленные справочные таблицы либо для предоставления коэффициентов для алгоритмов интерполяции , либо для инициализации алгоритмов последовательного приближения .
Компиляторы широко используют предварительные вычисления как средство увеличения скорости выполнения результирующего кода: эти предварительные вычисления можно рассматривать как форму частичной оценки самого программного кода. Примеры такого рода предварительных вычислений включают анализ потока данных и этапы снижения прочности .
