В алгоритмах , предвычисление является актом выполнения начального вычисления , прежде чем время выполнения , чтобы создать таблицу поиска , который может быть использован с помощью алгоритма , чтобы избежать повторных вычислений каждый раз , когда она выполняется. Предварительные вычисления часто используются в алгоритмах, которые зависят от результатов дорогостоящих вычислений, которые не зависят от входных данных алгоритма. Тривиальным примером предварительного вычисления является использование жестко запрограммированных математических констант, таких как π и e , вместо вычисления их приближений с необходимой точностью во время выполнения.
В базах данных термин материализация используется для обозначения сохранения результатов предварительного вычисления [1] [2], например, в материализованном представлении . [3] [4]
Обзор
Предварительное вычисление набора промежуточных результатов в начале выполнения алгоритма часто может существенно повысить алгоритмическую эффективность . Это становится выгодным, когда один или несколько входов ограничиваются достаточно малым диапазоном, чтобы результаты можно было сохранить в блоке памяти разумного размера. Поскольку доступ к памяти по существу постоянен по временной сложности (за исключением задержек кэширования ), любой алгоритм с компонентом, который имеет эффективность хуже постоянной в небольшом диапазоне ввода, может быть улучшен путем предварительного вычисления значений. В некоторых случаях эффективные алгоритмы аппроксимации могут быть получены путем вычисления дискретного подмножества значений и интерполяции для промежуточных входных значений, поскольку интерполяция также является линейной операцией.
История
До появления компьютеров люди использовали печатные справочные таблицы значений для ускорения ручных вычислений сложных функций, например, в тригонометрических таблицах , таблицах логарифмов и таблицах статистических функций плотности [5] Школьников часто учат запоминать " таблицы умножения », чтобы избежать вычислений наиболее часто используемых чисел (до 9 x 9 или 12 x 12). Еще в 493 году нашей эры Викториус Аквитанский написал таблицу умножения из 98 столбцов, которая давала ( римскими цифрами ) произведение каждого числа от 2 до 50 раз, а строки представляли собой «список чисел, начинающийся с тысячи, убывающий на от сотен до ста, затем по убыванию от десятков до десяти, затем от единиц к одному, а затем дроби до 1/144 » [6]
Примеры
Даже современные компьютерные реализации цифровых тригонометрических функций часто используют предварительно вычисленные справочные таблицы либо для предоставления коэффициентов для алгоритмов интерполяции , либо для инициализации алгоритмов последовательного приближения .
Многие атаки на криптосистемы включают предварительные вычисления.
Примеры крупномасштабных предварительных вычислений как части современных эффективных алгоритмов включают:
- Радужные столы
- Идеальные хеши
- Куб атаки
- Предварительно рассчитанные деревья BSP для расчетов видимости в 3D-графике
- Radiosity предвычисления для освещения в 3D - графике
Компиляторы широко используют предварительное вычисление как средство увеличения скорости выполнения результирующего кода: это предварительное вычисление можно рассматривать как фактически форму частичной оценки самого программного кода. Примеры такого рода предварительных вычислений включают этапы анализа потока данных и снижения прочности .
Смотрите также
Рекомендации
- ^ Цзявэй Хан; Мишлин Камбер (9 июня 2011 г.). Data Mining: концепции и методы: концепции и методы . Эльзевир. п. 159. ISBN. 978-0-12-381480-7.
- ^ Свен Гроппе (29 апреля 2011 г.). Управление данными и обработка запросов в базах данных семантической сети . Springer Science & Business Media. п. 178. ISBN 978-3-642-19357-6.
- ^ Карен Мортон; Керри Осборн; Робин Сэндс; Риядж Шамсудин; Джаред Стилл (28 октября 2013 г.). Профессиональный Oracle SQL . Апресс. п. 48. ISBN 978-1-4302-6220-6.
- ^ Мари-Од Ауфор; Эстебан Зимани (16 января 2012 г.). Бизнес-аналитика: Первая европейская летняя школа, EBISS 2011, Париж, Франция, 3-8 июля 2011 г., обучающие лекции . Springer Science & Business Media. п. 43. ISBN 978-3-642-27357-5.
- ^ Кэмпбелл-Келли, Мартин; Кроаркен, Мэри; Флуд, Раймонд; и др., ред. (2003). История математических таблиц от Шумера до электронных таблиц . Издательство Оксфордского университета. ISBN 978-0-19-850841-0.
- ^ Махер, Дэвид. WJ и Джон Ф. Маковски. «Литературные доказательства римской арифметики с дробями», «Классическая филология» (2001), т. 96 № 4 (2001) стр. 376–399. (См. Стр. 383.)