Таблица поиска
Материал из Википедии — свободной энциклопедии
Таблица поиска (Lookup table) — это структура данных, обычно массив или ассоциативный массив, используемая с целью заменить вычисления на операцию простого поиска. Увеличение скорости может быть значительным, так как получить данные из памяти зачастую быстрее, чем выполнение трудоёмких вычислений.
Классический пример использования таблиц поиска — вычисление значений тригонометрических функций, например синуса. Его непосредственное вычисление может сильно замедлить работу приложения. Чтобы этого избежать, приложение при первом запуске заранее рассчитывает определённое количество значений синуса, например, для всех целых градусов. Потом, когда программе понадобится значение синуса, она использует таблицу поиска чтобы получить приблизительное значение синуса из памяти, вместо того чтобы вычислять его значение, например, с помощью рядов. Таблицы поиска также используются в математических сопроцессорах; ошибка в таблице поиска привела Intel к печально известному багу уменьшавшему точность операции деления (Pentium FDIV баг).
Задолго до того как таблицы поиска появились в программировании, они уже использовались людьми для облегчения ручных вычислений. Особенно были распространены таблицы тригонометрических и статистических функций и логарифмов.
Существует промежуточное решение, когда используют таблицу поиска в сочетании с простыми вычислениями — интерполяцией. Это позволяет более точно находить значения между двумя вычисленными заранее точками. Затраты времени немного возрастут, но взамен будет обеспечена необходимая точность вычислений. Также эту технику можно применять для уменьшения размеров таблицы поиска без потерь точности.
Таблицы поиска, используемые в обработке изображений, часто называются LUT. Один общий LUT, называемый «палитра», используется, чтобы задать значения цвета и интенсивности, с которыми будет показано конкретное изображение.
Важно отметить, что использование таблиц поиска, когда они не эффективны, жестоко карается ухудшением скорости работы. Это происходит не только потому, что извлечение из памяти данных станет медленней их вычисления, но и потому что таблица поиска может занять всю память и переполнить кэш. Если таблица велика, каждое обращение к ней, скорее всего, будет приводить к промаху кэша. Для некоторых языков, например Java, обращение к таблице поиска может быть даже более дорогим из-за обязательной проверки границ включающей в себя дополнительные сравнения и ветвления для каждой операции поиска.
Есть два фундаментальных ограничения на создание таблиц поиска. Первое — это общее количество доступной памяти: таблица должна влезать в имеющийся объём, хотя можно сделать таблицу поиска и на диске, увеличив тем самым время операции поиска. Другое ограничение — это время необходимое для создания таблицы поиска при первом запуске, хотя обычно эта операция нужна только один раз, она может отнимать непомерно много времени, что делает использование таблиц поиска неподходящим решением.
[править] Примеры
[править] Вычисление синуса
Большинство компьютеров поддерживает только основные арифметические операции и не могут посчитать значение синуса напрямую. Вместо этого, они используют метод CORDIC или используют, например, ряд Тейлора, чтобы вычислить значение синуса с высокой степенью точности:
Однако, это может быть времяёмкое вычисление, особенно на медленном процессоре, и существует множество приложений, взять хотя бы обычную компьютерную графику, которым необходимо вычислять значение тысяч синусов каждую секунду. Распространённое решение — заранее вычислить значения синуса и затем нахождение синуса x сведётся к выбору посчитанного значения ближайшего к x. Оно будет близко к правильному значению, потому что синус — непрерывная и ограниченная функция. Например:
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 таблица синусов const unsigned char sinetable[256] = { 128,131,134,137,140,143,146,149,152,156,159,162,165,168,171,174, 176,179,182,185,188,191,193,196,199,201,204,206,209,211,213,216, 218,220,222,224,226,228,230,232,234,236,237,239,240,242,243,245, 246,247,248,249,250,251,252,252,253,254,254,255,255,255,255,255, 255,255,255,255,255,255,254,254,253,252,252,251,250,249,248,247, 246,245,243,242,240,239,237,236,234,232,230,228,226,224,222,220, 218,216,213,211,209,206,204,201,199,196,193,191,188,185,182,179, 176,174,171,168,165,162,159,156,152,149,146,143,140,137,134,131, 128,124,121,118,115,112,109,106,103,99, 96, 93, 90, 87, 84, 81, 79, 76, 73, 70, 67, 64, 62, 59, 56, 54, 51, 49, 46, 44, 42, 39, 37, 35, 33, 31, 29, 27, 25, 23, 21, 19, 18, 16, 15, 13, 12, 10, 9, 8, 7, 6, 5, 4, 3, 3, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 15, 16, 18, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 42, 44, 46, 49, 51, 54, 56, 59, 62, 64, 67, 70, 73, 76, 79, 81, 84, 87, 90, 93, 96, 99, 103,106,109,112,115,118,121,124 };
