В информатике таблица поиска ( LUT ) — это массив , который заменяет вычисления во время выполнения более простой операцией индексации массива в процессе, называемом прямой адресацией . Экономия времени обработки может быть значительной, поскольку извлечение значения из памяти часто происходит быстрее, чем выполнение «дорогих» вычислений или операций ввода/вывода . [1] Таблицы могут быть предварительно рассчитаны и сохранены в статической памяти программы, рассчитаны (или «предварительно выбраны» ) как часть фазы инициализации программы ( мемоизация ) или даже сохранены в аппаратном обеспечении на платформах для конкретных приложений. Таблицы поиска также широко используются для проверки входных значений путем сопоставления со списком допустимых (или недопустимых) элементов в массиве и в некоторых языках программирования могут включать функции указателя (или смещения меток) для обработки совпадающих входных данных. В ПЛИС также широко используются реконфигурируемые аппаратно реализуемые справочные таблицы для обеспечения программируемых аппаратных функций. LUT отличаются от хеш-таблиц тем, что для получения значения с помощью ключа хеш-таблица сохраняет значение в слоте , где находится хеш-функция , т. е . используется для вычисления слота, тогда как в случае LUT значение хранится в слоте , поэтому адресуется напрямую. [2] : 466
До появления компьютеров таблицы поиска значений использовались для ускорения ручных вычислений сложных функций, таких как тригонометрия , логарифмы и функции статистической плотности. [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 гарантируется для операции поиска, никакие два объекта или значения не могут иметь один и тот же ключ . Когда размер юниверса , в котором нарисованы ключи, велик, хранить его в памяти может оказаться непрактичным или невозможным . Следовательно, в этом случае хеш-таблица будет предпочтительной альтернативой. [2] : 468
Для тривиального поиска хеш-функции значение необработанных данных без знака используется непосредственно как индекс одномерной таблицы для извлечения результата. Для небольших диапазонов это может быть один из самых быстрых поисков, даже превышающих скорость двоичного поиска с нулевыми ветвями и выполняемых за постоянное время . [6]
Одна дискретная проблема, решение которой на многих компьютерах обходится дорого, — это подсчет количества битов, которым присвоено значение 1 в (двоичном) числе, иногда называемом функцией населения . Например, десятичное число «37» в двоичном формате равно «00100101», поэтому оно содержит три бита, которым присвоено двоичное значение «1». [7] : 282
Простой пример кода C , предназначенного для подсчета 1 бит в int , может выглядеть так: [7] : 283
int count_ones ( unsigned int x ) { int result = 0 ; в то время как ( Икс != 0 ) { Икс знак равно Икс & ( Икс - 1 ); результат ++ ; } вернуть результат ; } Приведенная выше реализация требует 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 ; символ каждого_байта [ 4 ]; } операнд = входное_значение ; 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 ( набор_битов [ операнд . каждый_байт [ 0 ]] + набор_битов [ операнд . каждый_байт [ 1 ]] + набор_битов [ операнд . каждый_байт [ 2 ]] + набор_битов [ операнд . каждый_байт [ 3 ]]); }} 
«Таблицы поиска (LUT) являются отличным методом оптимизации оценки функций, которые дорого вычислить и недорого кэшировать. ... Для запросов данных, которые попадают между выборками таблицы, алгоритм интерполяции может генерировать разумные аппроксимации, усредняя близлежащие выборки. ." [8]
В приложениях анализа данных, таких как обработка изображений , таблица поиска (LUT) используется для преобразования входных данных в более желательный выходной формат. Например, изображение планеты Сатурн в оттенках серого будет преобразовано в цветное изображение, чтобы подчеркнуть различия в ее кольцах.
При обработке изображений таблицы поиска часто называются LUT (или 3DLUT) и выдают выходное значение для каждого диапазона значений индекса. Один общий LUT, называемый цветовой картой или палитрой , используется для определения цветов и значений интенсивности, с которыми будет отображаться конкретное изображение. В компьютерной томографии «окно» относится к связанной концепции определения того, как отображать интенсивность измеренного излучения.
Классическим примером сокращения вычислений во время выполнения с помощью справочных таблиц является получение результата тригонометрического вычисления, например синуса значения. Вычисление тригонометрических функций может существенно замедлить работу вычислительного приложения. Одно и то же приложение может завершиться гораздо быстрее, если оно сначала предварительно вычисляет синус ряда значений, например, для каждого целого числа градусов (таблицу можно определить как статические переменные во время компиляции, что снижает затраты на повторное выполнение). Когда программе требуется синус значения, она может использовать таблицу поиска для получения ближайшего значения синуса из адреса памяти, а также может интерполировать синус желаемого значения вместо вычисления по математической формуле. Таким образом, таблицы поиска используются математическими сопроцессорами в компьютерных системах. Ошибка в справочной таблице стала причиной печально известной ошибки деления чисел с плавающей запятой в Intel .
Функции одной переменной (например, синуса и косинуса) можно реализовать с помощью простого массива. Функции, включающие две или более переменных, требуют методов индексации многомерных массивов. Таким образом, в последнем случае можно использовать двумерный массив power[x][y] для замены функции для вычисления x y для ограниченного диапазона значений x и y. Функции, имеющие более одного результата, могут быть реализованы с помощью справочных таблиц, которые представляют собой массивы структур.
Как уже упоминалось, существуют промежуточные решения, в которых используются таблицы в сочетании с небольшим объемом вычислений, часто с использованием интерполяции . Предварительный расчет в сочетании с интерполяцией может обеспечить более высокую точность значений, которые находятся между двумя предварительно вычисленными значениями. Этот метод требует немного больше времени для выполнения, но может значительно повысить точность в приложениях, требующих более высокой точности. В зависимости от предварительно вычисляемых значений, предварительные вычисления с интерполяцией также могут использоваться для уменьшения размера таблицы поиска при сохранении точности.
Хотя использование таблицы поиска зачастую эффективно, оно, тем не менее, может привести к серьезным штрафам, если вычисления, которые заменяет LUT, относительно просты. Время извлечения данных из памяти и сложность требований к памяти могут увеличить время работы приложения и сложность системы по сравнению с тем, что потребовалось бы при прямом вычислении формулы. Проблемой также может стать возможность загрязнения кэша . Доступ к большим таблицам почти наверняка приведет к промаху в кэше . Это явление становится все более серьезной проблемой, поскольку процессоры опережают память. Аналогичная проблема возникает при рематериализации , оптимизации компилятора . В некоторых средах, таких как язык программирования Java , поиск по таблицам может быть даже более затратным из-за обязательной проверки границ, включающей дополнительное сравнение и ветвление для каждого поиска.
Существует два фундаментальных ограничения на возможность создания таблицы поиска для требуемой операции. Одним из них является объем доступной памяти: невозможно создать таблицу поиска размером больше, чем пространство, доступное для таблицы, хотя можно создать таблицы поиска на диске за счет времени поиска. Другой — это время, необходимое для вычисления значений таблицы в первом экземпляре; хотя обычно это необходимо сделать только один раз, но если это занимает слишком много времени, использование таблицы поиска может оказаться неподходящим решением. Однако, как говорилось ранее, во многих случаях таблицы могут быть определены статически.
Большинство компьютеров выполняют только основные арифметические операции и не могут напрямую вычислить синус заданного значения. Вместо этого они используют алгоритм CORDIC или сложную формулу, такую как следующий ряд Тейлора , для вычисления значения синуса с высокой степенью точности: [9] : 5
Однако вычисление этого может оказаться дорогостоящим, особенно на медленных процессорах, и существует множество приложений, особенно в традиционной компьютерной графике , которым необходимо вычислять многие тысячи значений синуса каждую секунду. Обычное решение состоит в том, чтобы сначала вычислить синус многих равномерно распределенных значений, а затем, чтобы найти синус x , мы выбираем синус значения, ближайшего к x , с помощью операции индексации массива. Это будет близко к правильному значению, поскольку синус — непрерывная функция с ограниченной скоростью изменения. [9] : 6 Например: [10] : 545–548
действительный массив sine_table [ - 1000 .. 1000 ] для x от - 1000 до 1000 sine_table [ x ] = синус ( pi * 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 ) Линейная интерполяция обеспечивает интерполируемую функцию, которая является непрерывной, но, как правило, не имеет непрерывных производных . Для более плавной интерполяции поиска в таблице, которая является непрерывной и имеет непрерывную первую производную , следует использовать кубический сплайн Эрмита .
При использовании интерполяции размер таблицы поиска можно уменьшить за счет использования неравномерной выборки . Это означает, что там, где функция близка к прямой, мы используем несколько точек выборки, а там, где она быстро меняет значение, мы используем больше точек выборки, чтобы сохранить аппроксимацию. близко к реальной кривой. Для получения дополнительной информации см. интерполяцию .
Кэши хранилища (включая дисковые кэши для файлов или кэши процессора для кода или данных) также работают как таблица поиска. Таблица построена с использованием очень быстрой памяти, а не хранится в более медленной внешней памяти, и содержит два фрагмента данных для поддиапазона битов, составляющих адрес внешней памяти (или диска) (особенно младшие биты любого возможного внешнего адреса). :
Одиночный (быстрый) поиск выполняется для чтения тега в справочной таблице по индексу, указанному младшими битами желаемого адреса внешнего хранилища, и для определения того, попал ли адрес памяти в кеш. При обнаружении попадания доступ к внешней памяти не требуется (за исключением операций записи, когда кэшированное значение через некоторое время может потребоваться асинхронно обновить в более медленную память или если позиция в кэше должна быть заменена для кэширования другого значения). адрес).
В цифровой логике таблица поиска может быть реализована с помощью мультиплексора , строки выбора которого управляются адресным сигналом, а входные данные представляют собой значения элементов, содержащихся в массиве. Эти значения могут быть либо жестко заданы, как в ASIC , назначение которых зависит от функции, либо предоставляться с помощью D-защелок , которые позволяют настраивать значения. ( ПЗУ , СППЗУ , ЭСППЗУ или ОЗУ .)
n - битный LUT может кодировать любую логическую функцию с n -входами , сохраняя таблицу истинности функции в LUT. Это эффективный способ кодирования функций булевой логики , а LUT с 4–6 битами на входе фактически являются ключевым компонентом современных программируемых пользователем вентильных матриц (FPGA), которые обеспечивают реконфигурируемые аппаратные логические возможности.
В системах сбора данных и управления справочные таблицы обычно используются для выполнения следующих операций:
В некоторых системах вместо справочных таблиц для этих вычислений также могут быть определены полиномы .
{{cite web}}: CS1 maint: неподходящий URL ( ссылка )