Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

История [ править ]

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

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

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

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

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

Примеры [ править ]

Простой поиск в массиве, ассоциативном массиве или связанном списке (несортированный список) [ править ]

Это называется линейным поиском или перебором , при этом каждый элемент по очереди проверяется на равенство, а соответствующее значение, если оно есть, используется в результате поиска. Часто это самый медленный метод поиска, если часто встречающиеся значения не появляются в начале списка. Для одномерного массива или связанного списка поиск обычно должен определить, есть ли совпадение с «входным» значением данных.

Двоичный поиск в массиве или ассоциативном массиве (отсортированный список) [ править ]

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

Тривиальная хеш-функция [ править ]

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

Подсчет битов в серии байтов [ править ]

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

Простой пример кода C , предназначенного для подсчета 1 бит в int , может выглядеть так:

int  count_ones ( беззнаковый  int  x ) {  int  result  =  0 ;  в то время как  ( x  ! =  0 )  {  x  =  x  &  ( x  -  1 );  результат ++ ;  }  вернуть  результат ; }

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

Просто создайте статическую таблицу bits_set с 256 записями , задающими количество битов, установленных в каждом возможном байтовом значении (например, 0x00 = 0, 0x01 = 1, 0x02 = 1 и т. Д.). Затем используйте эту таблицу, чтобы найти количество единиц в каждом байте целого числа, используя тривиальный поиск хеш-функции для каждого байта по очереди, и просуммируйте их. Для этого не требуются ветки и требуется всего четыре доступа к индексированной памяти, что значительно быстрее, чем в предыдущем коде.

/ * Псевдокод таблицы поиска 'uint32_t bits_set [256]' * / / * 0b00, 0b01, 0b10, 0b11, 0b100, 0b101, ... * / int  bits_set [ 256 ]  =  {  0 ,  1 ,  1 ,  2 ,  1 ,  2 ,  // еще 200+ записей/ * (этот код предполагает, что 'int' является 32- битным целым числом без знака) * / int  count_ones ( unsigned  int  x ) {  return  bits_set [  x  &  255 ]  +  bits_set [( x  >>  8 )  &  255 ]  +  bits_set [( x  >>  16 )  &  255 ]  +  бит_набор [( x  >>  24 )  &  255 ]; }

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

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

Красный (A), зеленый (B), синий (C) образец файла 16-битной таблицы поиска. (Строки с 14 по 65524 не показаны)

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

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

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

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

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

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

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

Вычисление синусов [ править ]

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

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

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

вещественный  массив  sine_table [ - 1000 .. 1000 ] для  x  от  - 1000  до  1000  sine_table [ x ]  =  sine ( pi  *  x  /  1000 )функция  lookup_sine ( x )  return  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 )

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

Другое решение, которое использует четверть пространства, но требует немного больше времени для вычисления, - это учет отношений между синусом и косинусом вместе с их правилами симметрии. В этом случае таблица поиска рассчитывается с использованием функции синуса для первого квадранта (т.е. sin (0..pi / 2)). Когда нам нужно значение, мы назначаем переменной угол, привязанный к первому квадранту. Затем мы переносим угол в четыре квадранта (не требуется, если значения всегда находятся в диапазоне от 0 до 2 * пи) и возвращаем правильное значение (т.е. первый квадрант является прямым возвратом, второй квадрант считывается из пи / 2-х, третий и четвертый - негативы первого и второго соответственно). Для косинуса нам нужно только вернуть угол, сдвинутый на pi / 2 (т.е. x + pi / 2). По касательной

Функция  init_sine ()  для  й  от  0  до  ( 360 / 4 ) + 1  sine_table [ х ]  =  грех ( 2 * пи  *  х  /  360 )функция  lookup_sine ( x )  x  =  обернуть  x  от  0  до  360  y  =  mod  ( x ,  90 )  if  ( x  <  90 )  return  sine_table [  y ]  if  ( x  <  180 )  return  sine_table [ 90 - y ]  if  ( x  <  270 )  return  - sine_table [ y ]  return  - sine_table [ 90 - y ]функция  lookup_cosine ( x )  возвращает  lookup_sine ( x  +  90 )функция  lookup_tan ( x )  возвращает  lookup_sine ( x )  /  lookup_cosine ( x )

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

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

Кеши [ править ]

Основная статья: Кэш (вычисления)

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

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

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

Аппаратные LUT [ править ]

В цифровой логике справочная таблица может быть реализована с помощью мультиплексора , строки выбора которого управляются адресным сигналом и чьи входы являются значениями элементов, содержащихся в массиве. Эти значения могут быть либо жестко зашитыми, как в ASIC , предназначение которого зависит от функции, либо предоставлены D-защелками, которые позволяют настраивать значения. ( ROM , EPROM , EEPROM или RAM .)

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

Системы сбора и контроля данных [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ McNamee, Пол (21 августа 1998). «Автоматизированная мемоизация в C ++» . Архивировано 16 апреля 2019 года.CS1 maint: неподходящий URL ( ссылка )
  2. ^ Кэмпбелл-Келли, Мартин; Кроаркен, Мэри; Робсон, Элеонора, ред. (2003). История математических таблиц: от Шумера до электронных таблиц . Издательство Оксфордского университета.
  3. ^ Махер, Дэвид. WJ и Джон Ф. Маковски. « Литературные доказательства римской арифметики с дробями », «Классическая филология» (2001), т. 96 № 4 (2001) стр. 376–399. (См. Стр. 383.)
  4. ↑ Билл Джелен: «С 1979 года - VisiCalc и LOOKUP»! , MrExcel East, 31 марта 2012 г.

Внешние ссылки [ править ]

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