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

В информатике таблица поиска ( LUT ) — это массив , который заменяет вычисления во время выполнения более простой операцией индексации массива в процессе, называемом прямой адресацией . Экономия времени обработки может быть значительной, поскольку извлечение значения из памяти часто происходит быстрее, чем выполнение «дорогих» вычислений или операций ввода/вывода . ^[1] Таблицы могут быть предварительно рассчитаны и сохранены в статической памяти программы, рассчитаны (или «предварительно выбраны» ) как часть фазы инициализации программы ( мемоизация ) или даже сохранены в аппаратном обеспечении на платформах для конкретных приложений. Таблицы поиска также широко используются для проверки входных значений путем сопоставления со списком допустимых (или недопустимых) элементов в массиве и в некоторых языках программирования могут включать функции указателя (или смещения меток) для обработки совпадающих входных данных. В ПЛИС также широко используются реконфигурируемые аппаратно реализуемые справочные таблицы для обеспечения программируемых аппаратных функций. LUT отличаются от хеш-таблиц тем, что для получения значения $v$ с ключом $k$ , хеш-таблица будет хранить значение $v$ в слоте $h(k)$ где $h$ это хеш-функция , т.е. $k$ используется для расчета слота, а в случае LUT значение $v$ хранится в слоте $k$ , таким образом, адресован напрямую. ^[2]^: 466

История

Часть таблицы десятичных логарифмов 20-го века в справочнике Абрамовица и Стегуна .

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

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

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

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

Ограничения

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

Примеры

Тривиальная хэш-функция

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

Подсчет битов в последовательности байтов

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

Простой пример кода C , предназначенного для подсчета 1 бит в 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 записями создается путем указания количества единичных битов, установленных в каждом возможном значении байта (например, 0x00 = 0, 0x01 = 1, 0x02 = 1 и т. д.). Хотя времени выполнения можно использовать алгоритм для создания массива bits_set , это неэффективное использование тактовых циклов, когда принимается во внимание размер, поэтому используется предварительно вычисленная таблица, хотя времени компиляции для динамического создания и добавления таблицы можно использовать сценарий . в исходный файл . Сумма единиц в каждом байте целого числа может быть вычислена с помощью тривиального поиска хеш-функции для каждого байта; таким образом, эффективное избегание ветвей приводит к значительному повышению производительности. ^[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) являются отличным методом оптимизации оценки функций, которые дорого вычислить и недорого кэшировать. ... Для запросов данных, которые попадают между выборками таблицы, алгоритм интерполяции может генерировать разумные аппроксимации, усредняя близлежащие выборки. ." ^[8]

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

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

Обсуждение

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

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

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

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

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

Вычисление синусов

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

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

(для x близкого к 0)

Однако вычисление этого может оказаться дорогостоящим, особенно на медленных процессорах, и существует множество приложений, особенно в традиционной компьютерной графике , которым необходимо вычислять многие тысячи значений синуса каждую секунду. Обычное решение состоит в том, чтобы сначала вычислить синус многих равномерно распределенных значений, а затем, чтобы найти синус x, мы выбираем синус значения, ближайшего к x, с помощью операции индексации массива. Это будет близко к правильному значению, поскольку синус — непрерывная функция с ограниченной скоростью изменения. ^[10]^: 6 Например: ^[11]^{: 545–548}

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

К сожалению, таблица требует довольно много места: если использовать числа с плавающей запятой двойной точности IEEE, потребуется более 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)

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

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

Другие варианты использования справочных таблиц

Тайники

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

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

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

Аппаратные LUT

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

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

Системы сбора и управления данными

В сбора данных и системах управления справочные таблицы обычно используются для выполнения следующих операций:

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

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

См. также

Ассоциативный массив
Таблица филиалов
Точные таблицы Гала
Мемоизация
Функция с привязкой к памяти
Таблица поиска сдвигового регистра
Палитра , также известная как таблица поиска цветов или CLUT — для использования в компьютерной графике.
Таблица поиска 3D - использование в киноиндустрии

Ссылки

^ МакНэми, Пол (21 августа 1998 г.). «Автоматическая мемоизация в C++» . Архивировано из оригинала 16 апреля 2019 года. {{cite web}}: CS1 maint: неподходящий URL ( ссылка )
^ Jump up to: ^а ^б Квок, В.; Хагиги, К.; Канг, Э. (1995). «Эффективная структура данных для метода создания треугольной сетки с наступающим фронтом» . Коммуникации в численных методах в технике . 11 (5). Уайли и сыновья: 465–473. дои : 10.1002/cnm.1640110511 .
^ Кэмпбелл-Келли, Мартин ; Кроаркен, Мэри ; Робсон, Элеонора , ред. (2003). История математических таблиц: от Шумера к электронным таблицам . Издательство Оксфордского университета.
^ Махер, Дэвид. WJ и Джон Ф. Маковски. « Литературные доказательства римской арифметики с дробями », «Классическая филология» (2001), Vol. 96 № 4 (2001), стр. 376–399. (См. стр. 383.)
^ Билл Джелен: «С 1979 года – VisiCalc и ПРОСМОТР»! , автор MrExcel East, 31 марта 2012 г.
^ Кормен, Томас Х. (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс: MIT Press. стр. 253–255. ISBN 9780262033848 . Проверено 26 ноября 2015 г.
^ Jump up to: ^а ^б ^с ^д Юнгк П.; Денкан Р.; Малкахи Д. (2011). Разработка ради производительности. В: Программирование packageC . Апресс. дои : 10.1007/978-1-4302-4159-1_26 . ISBN 978-1-4302-4159-1 .
^ nvidia gpu gems2: использование справочных таблиц-ускорение-цвета
^ Сасао, Т.; Батлер, Джей Ти; Ридель, доктор медицинских наук «Применение LUT-каскадов к числовым генераторам функций» . Центр оборонной технической информации . Военно-морская школа последипломного образования в Монтерее, Калифорния, кафедра электротехники и компьютерной техники . Проверено 17 мая 2024 г. {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Jump up to: ^а ^б Шариф, Хайдар (2014). «Высокопроизводительные математические функции для одноядерных архитектур» . Журнал схем, систем и компьютеров . 23 (4). Всемирная научная. дои : 10.1142/S0218126614500510 .
^ Рэндалл Хайд (1 марта 2010 г.). Искусство языка ассемблера, 2-е издание (PDF) . Нет крахмального пресса. ISBN 978-1593272074 – через Институт вычислительной техники Университета Кампинаса.

Внешние ссылки

Быстрый поиск в таблице с использованием входного символа в качестве индекса для таблицы ветвления
Искусство сборки: расчет с помощью поиска в таблице
«Bit Twiddling Hacks» (включая таблицы поиска), Шон Эрон Андерсон из Стэнфордского университета.
Мемоизация на C++ , Пол МакНэми, Университет Джонса Хопкинса, демонстрирует экономию
«В поисках ускоренного подсчета населения» Генри С. Уоррена-младшего.

[1] МакНэми, Пол (21 августа 1998 г.). «Автоматическая мемоизация в C++» . Архивировано из оригинала 16 апреля 2019 года. {{cite web}}: CS1 maint: неподходящий URL ( ссылка )

[Kwok95-2] Jump up to: ^а ^б Квок, В.; Хагиги, К.; Канг, Э. (1995). «Эффективная структура данных для метода создания треугольной сетки с наступающим фронтом» . Коммуникации в численных методах в технике . 11 (5). Уайли и сыновья: 465–473. дои : 10.1002/cnm.1640110511 .

[3] Кэмпбелл-Келли, Мартин ; Кроаркен, Мэри ; Робсон, Элеонора , ред. (2003). История математических таблиц: от Шумера к электронным таблицам . Издательство Оксфордского университета.

[4] Махер, Дэвид. WJ и Джон Ф. Маковски. « Литературные доказательства римской арифметики с дробями », «Классическая филология» (2001), Vol. 96 № 4 (2001), стр. 376–399. (См. стр. 383.)

[5] Билл Джелен: «С 1979 года – VisiCalc и ПРОСМОТР»! , автор MrExcel East, 31 марта 2012 г.

[6] Кормен, Томас Х. (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс: MIT Press. стр. 253–255. ISBN 9780262033848 . Проверено 26 ноября 2015 г.

[apress11-7] Jump up to: ^а ^б ^с ^д Юнгк П.; Денкан Р.; Малкахи Д. (2011). Разработка ради производительности. В: Программирование packageC . Апресс. дои : 10.1007/978-1-4302-4159-1_26 . ISBN 978-1-4302-4159-1 .

[8] vidia gpu gems2: использование справочных таблиц-ускорение-цвета

[9] Сасао, Т.; Батлер, Джей Ти; Ридель, доктор медицинских наук «Применение LUT-каскадов к числовым генераторам функций» . Центр оборонной технической информации . Военно-морская школа последипломного образования в Монтерее, Калифорния, кафедра электротехники и компьютерной техники . Проверено 17 мая 2024 г. {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )

[sharif14-10] Jump up to: ^а ^б Шариф, Хайдар (2014). «Высокопроизводительные математические функции для одноядерных архитектур» . Журнал схем, систем и компьютеров . 23 (4). Всемирная научная. дои : 10.1142/S0218126614500510 .

[11] Рэндалл Хайд (1 марта 2010 г.). Искусство языка ассемблера, 2-е издание (PDF) . Нет крахмального пресса. ISBN 978-1593272074 – через Институт вычислительной техники Университета Кампинаса.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]