Jump to content

Предварительные вычисления

(Перенаправлено из Предварительных вычислений )
Часть предварительно вычисленной математической таблицы десятичных логарифмов 20-го века .

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

В базах данных термин «материализация» используется для обозначения хранения результатов предварительных вычислений. [1] [2] например, в материализованном представлении . [3] [4]

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

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

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

Многие атаки на криптосистемы включают предварительные вычисления.

Примеры крупномасштабных предварительных вычислений как части современных эффективных алгоритмов включают:

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

См. также

[ редактировать ]
  1. ^ Цзявэй Хан; Мишлин Камбер (9 июня 2011 г.). Интеллектуальный анализ данных: концепции и методы: концепции и методы . Эльзевир. п. 159. ИСБН  978-0-12-381480-7 .
  2. ^ Свен Гроппе (29 апреля 2011 г.). Управление данными и обработка запросов в базах данных семантической сети . Springer Science & Business Media. п. 178. ИСБН  978-3-642-19357-6 .
  3. ^ Карен Мортон; Керри Осборн; Робин Сэндс; Риядж Шамсудин; Джаред Стилл (28 октября 2013 г.). Про Oracle SQL . Апресс. п. 48. ИСБН  978-1-4302-6220-6 .
  4. ^ Мари-Од Офор; Эстебан Зиманьи (16 января 2012 г.). Бизнес-аналитика: Первая европейская летняя школа, EBISS 2011, Париж, Франция, 3-8 июля 2011 г., Учебные лекции . Springer Science & Business Media. п. 43. ИСБН  978-3-642-27357-5 .
  5. ^ Кэмпбелл-Келли, Мартин ; Кроаркен, Мэри ; Флуд, Рэймонд ; и др., ред. (2003). История математических таблиц от Шумера до электронных таблиц . Издательство Оксфордского университета. ISBN  978-0-19-850841-0 .
  6. ^ Махер, Дэвид. WJ и Джон Ф. Маковски. «Литературные доказательства римской арифметики с дробями», «Классическая филология» (2001), Vol. 96 № 4 (2001), стр. 376–399. (См. стр. 383.)
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: b2527f5b15922a8f035fdacd69e8fc4c__1712630100
URL1:https://arc.ask3.ru/arc/aa/b2/4c/b2527f5b15922a8f035fdacd69e8fc4c.html
Заголовок, (Title) документа по адресу, URL1:
Precomputation - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)