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