Таблица поиска

Таблица поиска (англ. lookup table) — это структура данных, обычно массив или ассоциативный массив, используемая с целью заменить вычисления на операцию простого поиска. Увеличение скорости может быть значительным, так как получить данные из памяти зачастую быстрее, чем выполнить трудоёмкие вычисления.

Классический пример использования таблиц поиска — вычисление значений тригонометрических функций, например, синуса. Его непосредственное вычисление может сильно замедлить работу приложения. Чтобы этого избежать, приложение при первом запуске заранее рассчитывает определённое количество значений синуса, например, для всех целых градусов. Потом, когда программе понадобится значение синуса, она использует таблицу поиска, чтобы получить приблизительное значение синуса из памяти, вместо того чтобы вычислять его значение (например, с помощью рядов). Таблицы поиска также используются в математических сопроцессорах; ошибка в таблице поиска в процессорах Pentium фирмы Intel привела к печально известной ошибке, уменьшавшей точность операции деления.

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

Существует промежуточное решение, когда используют таблицу поиска в сочетании с простыми вычислениями — интерполяцией. Это позволяет более точно находить значения между двумя вычисленными заранее точками. Затраты времени немного возрастут, но взамен будет обеспечена бо́льшая точность вычислений. Также эту технику можно применять для уменьшения размеров таблицы поиска без потерь точности.

Таблицы поиска широко используются также в компьютерной обработке изображений (в этой области соответствующие таблицы обычно называют «палитрами»).

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

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

Источник: Википедия