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