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

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

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

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

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

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

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

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

Примеры

Вычисление синуса

Большинство компьютеров поддерживает только основные арифметические операции и не могут вычислить значение синуса напрямую. Вместо этого для вычисления значения синуса с высокой степенью точности они используют метод CORDIC или ряд Тейлора:

$\operatorname{sin}(x) = x - \frac{x^3}{6} + \frac{x^5}{120} - \frac{x^7}{5040}+\ldots$

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

real array sine_table[-1000..1000]
 for x from -1000 to 1000
     sine_table[x] := sine(pi * x / 1000)

 function lookup_sine(x)
     return sine_table[round(1000 * x / pi)]

Линейная интерполяция функции синуса на некотором диапазоне.

Таблица требует много памяти — например, если используются числа с плавающей запятой двойной точности, то понадобится 16 000 байт. Можно использовать меньшее количество точек, но тогда точность упадёт. Хорошей практикой в таком случае является линейная аппроксимация.

Вот пример линейной аппроксимации:

 function lookup_sine(x)
     x1 := floor(x*1000/pi)
     y1 := sine_table[x1]
     y2 := sine_table[x1+1]
     return y1 + (y2-y1)*(x/1000/pi-x1)

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

Пример таблицы синусов

// C 8-bit таблица синусов

При этом значения синуса из [-1;1] отражены в целочисленый диапазон от минимального 0 до максимального 255, нулю соответвуюет 128. При работе CPU операции с целыми числами происходят на порядок быстрее, чем с плавающей запятой.