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

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

Таблицы поиска отличаются от хеш-таблиц тем, что для получения значения ${\displaystyle v}$ по ключу ${\displaystyle k}$ в хеш-таблице значение ${\displaystyle v}$ сохраняется в ячейке ${\displaystyle h(k)}$ (где ${\displaystyle h}$ — хеш-функция, то есть ${\displaystyle k}$ используется для вычисления адреса), а в таблице поиска значение ${\displaystyle v}$ помещается непосредственно в ячейку ${\displaystyle k}$, что обеспечивает прямую адресацию^[2].^:{{{1}}}

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

В Индии около 499 года н. э. Арьябхата составил одну из первых таблиц синусов, зашифрованную с помощью числовой системы на санскрите. В 493 году Викторий Аквитанский создал 98-колоночную таблицу умножения, в которой произведения чисел от 2 до 50 выражались римскими цифрами, а строки представляли последовательности от тысячи (по сотням до сотни, затем по десяткам до десяти, по единицам до одного и далее дроби вплоть до 1/144)^[4]. В наше время обучающиеся зачастую заучивают «таблицу умножения», чтобы избежать повторных вычислений популярных одноразрядных произведений.

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

Таблицы поиска стали одними из первых реализованных функций в компьютерных электронных таблицах: уже в первой версии VisiCalc (1979) имелась функция LOOKUP среди 20 базовых^[5]. Позже подобные функции стали стандартом в других таблицах, например Microsoft Excel, где появились также VLOOKUP и HLOOKUP для вертикального и горизонтального поиска.

Хотя производительность поиска в таблице поиска гарантировано составляет ${\displaystyle O(1)}$ на одну операцию, ни две сущности, ни два значения не могут иметь одинаковый ключ ${\displaystyle k}$. Если размер универсума ${\displaystyle \cup }$, из которого выбираются ключи, велик, размещение таблицы поиска в оперативной памяти становится непрактичным или невозможным. В таких случаях предпочтение отдается хеш-таблицам.^[2]:468

При использовании тривиальной хеш-функции сырое значение беззнакового типа применяется непосредственно в качестве индекса одномерного массива для получения результата. Для небольших диапазонов такой поиск может быть наиболее быстрым, превосходя скорость даже бинарного поиска за счет отсутствия ветвлений и постоянного времени выполнения^[6].

Задача подсчёта единичных бит (population count, функция населения) в двоичном числе является значительной вычислительной нагрузкой для многих компьютеров. Например, число 37 в двоичном виде — «00100101» — содержит три единичных бита^[7].^:{{{1}}}

Обычный код на языке C для подсчёта единичных бит в числе типа int может выглядеть так:^[7]:283

int count_ones(unsigned int x) {
  int result = 0;
  while (x != 0) {
    x = x & (x - 1);
    result++;
  }
  return result;
}

Данная реализация может потребовать до 32 операций для 32-битного значения, что увеличивает число тактовых циклов из-за ветвлений. Оптимизация через развёртывание цикла и использование таблицы поиска (с тривиальным хешированием) позволяет ускорить вычисление.^[7]:282-283

Массив bits_set (256 элементов) содержит число единичных бит для каждого возможного значения байта (например, 0х00 = 0, 0х01 = 1, и так далее). Такое решение предпочтително для производительности: во время выполнения берётся сумма значений для каждого байта целого числа через индексирование метода таблицы поиска, что устраняет ветвления и ускоряет выполнение.^[7]:284

int count_ones(int input_value) {
  union four_bytes {
    int big_int;
    char each_byte[4];
  } operand = input_value;
  const int bits_set[256] = {
      0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4,
      2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4,
      2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
      4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5,
      3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
      4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
      4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
  return (bits_set[operand.each_byte[0]] + bits_set[operand.each_byte[1]] +
          bits_set[operand.each_byte[2]] + bits_set[operand.each_byte[3]]);
}

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

В обработке изображений таблицы поиска часто называют LUT или 3DLUT, они обеспечивают выходное значение для каждого заданного диапазона индексов. Одна из наиболее частых форм — colormap (цветовая карта, палитра), определяющая цвета и интенсивности, используемые для отображения изображения. В компьютерной томографии похожим образом применяется понятие «окон» для отображения интенсивностей.

Классическим примером ускорения вычислений с помощью таблицы поиска служит определение значения тригонометрической функции, например, вычисления синуса числа^[9]. Вычисление тригонометрических функций затрудняет выполнение многих приложений, особенно если требуется высокая частота обращения к таким функциям. Программы часто предварительно рассчитывают значения синуса для каждого целого числа градусов (или другой сетки), после чего непосредственно обращаются к таблице поиска — при необходимости используя интерполяцию для промежуточных значений. Такой подход широко реализуется и на аппаратном уровне (например, в сопроцессорах). Классический пример ошибки в таблице поиска — известный баг Pentium FDIV от Intel.

Функции одной переменной (как синус или косинус) удобно реализуются обычным массивом, многомерные — с помощью многомерных массивов, индексируемых по всем аргументам (например, массив power[x][y] может заменить вычисление x^y в ограниченном диапазоне). Функции с несколькими результатами реализуются таблицей массивов структур.

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

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

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

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

${\displaystyle \operatorname {sin} (x)\approx x-{\frac {x^{3}}{6}}+{\frac {x^{5}}{120}}-{\frac {x^{7}}{5040}}}$ (для ${\displaystyle x}$ близких к 0)

^[10]:{{{1}}}

Однако для медленных процессоров или приложений, требующих вычисления тысяч значений синуса в секунду (традиционная компьютерная графика и др.), такой расчёт может оказаться недопустимо медленным. В таких случаях заранее рассчитываются значения синуса для определённых значений (например, равномерно по сетке). Для нахождения значения для довольного ${\displaystyle x}$ выбирается ближайшее значение в массиве; точность зависит от разреженности сетки^[11].^:{{{1}}}

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)]

Недостаток такого подхода — большой размер таблицы: для 2001 значения, если использовать double с плавающей точкой, потребуется более 16 КБ памяти. Сократив число элементов, приходится жертвовать точностью. Изящный выход — линейная интерполяция, когда искомое значение вычисляется по двум ближайшим отсчётам таблицы как точка на прямой. Такой способ быстро реализуется и хорошо подходит для гладких функций.

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)

Линейная интерполяция даёт непрерывную аппроксимирующую функцию, но её производная не будет непрерывна. Для получения более гладкой интерполяции — с непрерывной производной — используют кубический сплайн Эрмита.

Существенно уменьшить размер таблицы позволяет неравномерное квантование: в областях, где функция меняется мало, достаточно редких отсчётов; там, где частные изменения велики — применяется более плотная сетка. Подробнее — см. интерполяция.

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

• тэг (остаток адреса); если тэг совпадает — значение в этой ячейке соответствует запрашиваемому адресу;
• данные, ассоциированные с этим адресом.

При совпадении тэга внешний доступ не требуется, данные извлекаются из кэша — иначе ищутся во внешней памяти.

В цифровой логике таблица поиска реализуется, например, с помощью мультиплексора, на входы которого подаются значения переменных, а на адресные выводы — адреса. Эти значения могут быть жёстко сконфигурированы (БИС с логикой под конкретную операцию) или программно загружены через триггеры (ROM, EPROM, EEPROM, или RAM).

Таблица поиска на n бит позволяет реализовать любую n-входовую булеву функцию путём сохранения её таблицы истинности. Это ключевая компонента современных FPGA, где таблицы поиска размером 4–6 бит служат основой настраиваемой аппаратной логики.

В системах сбора данных и управления таблицы поиска применяются для:

• внесения поправок по калибровочным значениям;
• преобразования единиц измерения;
• выполнения произвольных, определяемых пользователем вычислений.

В некоторых системах для этих целей используют не только таблицы поиска, но и полиномы.