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

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

История

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

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

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

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

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

Ограничения

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

Примеры

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

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

Подсчет битов в серии байтов

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

Простой пример кода на языке 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 записями создается путем указания количества единичных наборов битов в каждом возможном значении байта (например, 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 ]; } операнд = 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 [ операнд . each_byte [ 0 ]] + bits_set [ операнд . each_byte [ 1 ]] + bits_set [ операнд . each_byte [ 2 ]] + bits_set [ операнд . each_byte [ 3 ]]); }}

Таблицы поиска в обработке изображений

«Таблицы поиска (LUT) являются прекрасным методом оптимизации оценки функций, которые требуют больших затрат на вычисление и не требуют больших затрат на кэширование. ... Для запросов данных, которые попадают между образцами таблицы, алгоритм интерполяции может генерировать разумные приближения путем усреднения соседних образцов». ^[8]

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

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

Обсуждение

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

Функции одной переменной (например, синуса и косинуса) могут быть реализованы с помощью простого массива. Функции, включающие две или более переменных, требуют многомерных методов индексации массива. В последнем случае может использоваться двумерный массив power[x][y] для замены функции для вычисления x ^y для ограниченного диапазона значений 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}

действительный массив sine_table [ - 1000 .. 1000 ] для x от - 1000 до 1000 sine_table [ x ] = синус ( пи * x / 1000 )              функция lookup_sine ( x ) возвращает sine_table [ round ( 1000 * x / pi )]

К сожалению, таблица требует довольно много места: если использовать числа с плавающей точкой двойной точности IEEE, потребуется более 16 000 байт. Мы можем использовать меньше образцов, но тогда наша точность значительно ухудшится. Одним из хороших решений является линейная интерполяция , которая рисует линию между двумя точками в таблице по обе стороны от значения и находит ответ на этой линии. Это все еще быстро вычисляется и гораздо точнее для гладких функций, таких как функция синуса. Вот пример использования линейной интерполяции:

функция 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-защелками , которые допускают настраиваемые значения. ( ROM , EPROM , EEPROM или RAM .)

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

Системы сбора и контроля данных

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

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

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

Смотрите также

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

Ссылки

^ Макнами, Пол (21 августа 1998 г.). "Автоматизированная мемоизация в C++". Архивировано из оригинала 16 апреля 2019 г.{{cite web}}: CS1 maint: unfit URL (link)
^ ab Kwok, W.; Haghighi, K.; Kang, E. (1995). «Эффективная структура данных для метода генерации треугольной сетки с продвигающимся фронтом». Communications in Numerical Methods in Engineering . 11 (5). Wiley & Sons: 465–473. doi :10.1002/cnm.1640110511.
^ Кэмпбелл-Келли, Мартин ; Кроаркен, Мэри ; Робсон, Элеанор , ред. (2003). История математических таблиц: от Шумера до электронных таблиц . Oxford University Press.
^ Махер, Дэвид. WJ и Джон Ф. Маковски. «Литературные свидетельства римской арифметики с дробями», «Классическая филология» (2001) Том 96 № 4 (2001) стр. 376–399. (См. стр. 383.)
^ Билл Джелен: «С 1979 года – VisiCalc и LOOKUP»!, MrExcel East, 31 марта 2012 г.
^ Кормен, Томас Х. (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс: MIT Press. С. 253–255. ISBN 9780262033848. Получено 26 ноября 2015 г.
^ abcd Jungck P.; Dencan R.; Mulcahy D. (2011). Разработка для производительности. В: packetC Programming. Apress. doi :10.1007/978-1-4302-4159-1_26. ISBN 978-1-4302-4159-1.
^ nvidia gpu gems2 : использование-таблиц-подстановки-ускорение-цвета
^ Сасао, Т.; Батлер, Дж. Т.; Ридель, М. Д. «Применение каскадов LUT в генераторах числовых функций». Центр технической информации Министерства обороны . ВОЕННО-МОРСКАЯ АСПИРАНТУРА МОНТЕРЕЙ, КАЛИФОРНИЯ, КАФЕДРА ЭЛЕКТРОТЕХНИКИ И КОМПЬЮТЕРНОЙ ИНЖЕНЕРИИ . Получено 17 мая 2024 г.{{cite web}}: CS1 maint: multiple names: authors list (link)
^ ab Шариф, Хайдар (2014). «Высокопроизводительные математические функции для одноядерных архитектур». Журнал схем, систем и компьютеров . 23 (4). World Scientific. doi :10.1142/S0218126614500510.
^ Рэндалл Хайд (1 марта 2010 г.). Искусство языка ассемблера, 2-е издание (PDF) . No Starch Press. ISBN 978-1593272074– через Институт вычислительной техники Университета Кампинаса.

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

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