Лекция
Привет, Вы узнаете о том , что такое Таблица поиска как структура данных, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое Таблица поиска как структура данных , настоятельно рекомендую прочитать все из категории Структуры данных.
Таблица поиска (англ. lookup table) (LUT) — это структура данных, в которой хранятся результаты интерполяции функции. Обычно это массив или ассоциативный массив, используемый с целью заменить вычисления на операцию простого поиска. Увеличение скорости может быть значительным, так как получить данные из памяти зачастую быстрее, чем выполнить трудоемкие вычисления.
Классический пример использования таблиц поиска — вычисление значений тригонометрических функций, например, синуса. Его непосредственное вычисление может сильно замедлить работу приложения. Чтобы этого избежать, приложение при первом запуске заранее рассчитывает определенное количество значений синуса, например, для всех целых градусов. Потом, когда программе понадобится значение синуса, она использует таблицу поиска, чтобы получить приблизительное значение синуса из памяти, вместо того чтобы вычислять его значение (например, с помощью рядов). Таблицы поиска также используются в математических сопроцессорах; ошибка в таблице поиска в процессорах Pentium фирмы Intel привела к печально известной ошибке, уменьшавшей точность операции деления.
Задолго до того, как таблицы поиска появились в программировании, они уже использовались людьми для облегчения ручных вычислений. Особенно были распространены таблицы логарифмов, а также тригонометрических и статистических функций.
Существует промежуточное решение, когда используют таблицу поиска в сочетании с простыми вычислениями — интерполяцией. Это позволяет более точно находить значения между двумя вычисленными заранее точками. Затраты времени немного возрастут, но взамен будет обеспечена бо́льшая точность вычислений. Также эту технику можно применять для уменьшения размеров таблицы поиска без потерь точности.
Таблицы поиска широко используются также в компьютерной обработке изображений (в этой области соответствующие таблицы обычно называют «палитрами»).
Важно отметить, что использование таблиц поиска в тех задачах, в которых они неэффективны, приводит к понижению скорости работы. Это происходит не только потому, что извлечение из памяти данных оказывается медленнее, чем их вычисление, но и потому, что таблица поиска может занять всю память и переполнить кэш. Если таблица велика, каждое обращение к ней, скорее всего, будет приводить к промаху кэша. В некоторых языках программирования (например, в Java) обращение к таблице поиска может быть даже более «дорогим» из-за обязательной проверки границ, включающей в себя дополнительные сравнения и ветвления для каждой операции поиска.
Есть два фундаментальных ограничения на создание таблиц поиска. Первое — это общее количество доступной памяти: таблица должна умещаться в имеющийся объем, хотя можно сделать таблицу поиска и на диске, увеличив тем самым время операции поиска. Другое ограничение — это время, необходимое для создания таблицы поиска при первом запуске — хотя обычно эта операция нужна только один раз, она может отнимать слишком много времени, что делает использование таблиц поиска неподходящим решением.
До появления компьютеров справочные таблицы значений использовались для ускорения ручных вычислений сложных функций, таких как тригонометрия , логарифмы и функции статистической плотности.
В древней (499 г. н.э.) Индии Арьябхата создал одну из первых таблиц синусов , которую он закодировал в санскритской буквенной системе счисления. В 493 году нашей эры Викторий Аквитанский написал таблицу умножения из 98 столбцов, которая давала ( римскими цифрами ) произведение каждого числа от 2 до 50 раз, а строки представляли собой «список чисел, начинающихся с одной тысячи и убывающих по сотням до одного». сотен, затем в порядке убывания по десяткам до десяти, затем по убыванию по единицам до 1, а затем по дробям до 1/144" . Современных школьников часто учат запоминать " таблицы умножения ", чтобы избежать вычисления наиболее часто используемых чисел ( до 9 х 9 или 12 х 12).
В начале истории компьютеров операции ввода-вывода были особенно медленными — даже по сравнению со скоростями процессоров того времени. Имеет смысл сократить дорогостоящие операции чтения с помощью ручного кэширования путем создания либо статических таблиц поиска (встроенных в программу), либо динамических предварительно выбранных массивов, содержащих только наиболее часто встречающиеся элементы данных. Несмотря на введение общесистемного кэширования, которое теперь автоматизирует этот процесс, таблицы поиска на уровне приложений могут по-прежнему повышать производительность для элементов данных, которые редко изменяются, если вообще изменяются.
Таблицы поиска были одной из первых функций, реализованных в компьютерных электронных таблицах , причем первоначальная версия VisiCalc (1979 г.) включала LOOKUP функцию среди первоначальных 20 функций. За этим последовали последующие электронные таблицы, такие как Microsoft Excel , и дополненные специализированными функциями VLOOKUPи HLOOKUPдля упрощения поиска в вертикальной или горизонтальной таблице. В Microsoft Excel XLOOKUP функция развернута с 28 августа 2019 года.
ОграниченияРедактировать
Хотя производительность LUT гарантированаО(1) 
для операции поиска никакие две сущности или значения не могут иметь один и тот же ключк 
. Об этом говорит сайт https://intellect.icu . Когда размер вселенной ∪
— где нарисованы ключи — большой, хранить его в памяти может быть нецелесообразно или невозможно . Следовательно, в этом случае хэш-таблица будет предпочтительной альтернативой. [
Большинство компьютеров поддерживают только основные арифметические операции и не могут вычислить значение синуса напрямую. Вместо этого для вычисления значения синуса с высокой степенью точности они используют метод CORDIC или ряд Тейлора:
Однако такое вычисление может занять много времени, особенно на медленном процессоре, и существует множество приложений, например, компьютерная графика, которым необходимо вычислять значение тысяч синусов каждую секунду. Распространенное решение — заранее вычислить таблицу значений синуса, и затем нахождение синуса числа сведется к выбору ближайшего к этому числу аргумента из таблицы (соответствующее значение функции будет близко к правильному значению, потому что синус — непрерывная и ограниченная функция). Например:
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)]
Линейная интерполяция функции синуса на некотором диапазоне.
Таблица требует много памяти — например, если используются числа с плавающей запятой двойной точности, то понадобится 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)
При использовании интерполяции зачастую выгодно использовать неравномерное распределение данных: в тех местах, где функция ближе всего к прямой, брать мало точек для вычисления функции, если же кривизна функции велика — брать больше точек из этого диапазона, чтобы аппроксимация больше походила на реальную кривую (см. также Интерполяция ).
Пример таблицы синусов (на языке программирования C):
// 8-битная таблица синусов
При этом значения синуса из [-1;1] отражены в целочисленый диапазон от минимального 0 до максимального 255, нулю соответствует 128. В подавляющем большинстве CPU операции с целыми числами происходят значительно быстрее, чем с плавающей запятой.
Для тривиального поиска хэш-функции необработанное значение данных без знака используется непосредственно в качестве индекса к одномерной таблице для извлечения результата. Для небольших диапазонов это может быть одним из самых быстрых поисков, даже превышающим скорость бинарного поиска с нулевыми переходами и выполнением за постоянное время
«Таблицы поиска (LUT) — отличный метод оптимизации оценки функций, которые требуют больших затрат на вычисление и недорогих в кэшировании. ... Для запросов данных, которые попадают между выборками таблицы, алгоритм интерполяции может генерировать разумные приближения, усредняя соседние выборки. ."
В приложениях для анализа данных , таких как обработка изображений , справочная таблица (LUT) используется для преобразования входных данных в более желательный выходной формат. Например, изображение планеты Сатурн в градациях серого будет преобразовано в цветное изображение, чтобы подчеркнуть различия в его кольцах.
Классический пример сокращения вычислений во время выполнения с помощью интерполяционных таблиц — получение результата тригонометрического вычисления, такого как синус значения. Вычисление тригонометрических функций может существенно замедлить работу вычислительного приложения. Одно и то же приложение может завершиться намного раньше, если оно предварительно вычислит синус ряда значений, например, для каждого целого числа градусов (таблица может быть определена как статические переменные во время компиляции, что снижает повторяющиеся затраты времени выполнения). Когда программе требуется синус значения, она может использовать справочную таблицу для извлечения ближайшего значения синуса из адреса памяти, а также может выполнять интерполяцию до синуса желаемого значения вместо вычисления по математической формуле. Таким образом, таблицы поиска используются математическими сопроцессорами .в компьютерных системах. Ошибка в таблице поиска была причиной печально известной ошибки деления Intel с плавающей запятой .
Функции одной переменной (такие как синус и косинус ) могут быть реализованы простым массивом. Функции, включающие две или более переменных, требуют методов индексации многомерных массивов . Таким образом, в последнем случае можно использовать двумерный массив степени [x][y] для замены функции вычисления x y для ограниченного диапазона значений x и y. Функции, которые имеют более одного результата, могут быть реализованы с помощью таблиц поиска, которые представляют собой массивы структур.
Как уже упоминалось, существуют промежуточные решения, которые используют таблицы в сочетании с небольшим объемом вычислений, часто с использованием интерполяции . Предварительное вычисление в сочетании с интерполяцией может обеспечить более высокую точность для значений, попадающих между двумя предварительно вычисленными значениями. Этот метод требует немного больше времени для выполнения, но может значительно повысить точность в приложениях, требующих более высокой точности. В зависимости от предварительно вычисляемых значений предварительное вычисление с интерполяцией также можно использовать для уменьшения размера таблицы поиска при сохранении точности.
В обработке изображений справочные таблицы часто называют LUT (или 3DLUT) и дают выходное значение для каждого диапазона значений индекса. Одна общая LUT, называемая цветовой картой или палитрой , используется для определения цветов и значений интенсивности, с которыми будет отображаться конкретное изображение. В компьютерной томографии «окно» относится к связанной концепции для определения того, как отображать интенсивность измеренного излучения.
Несмотря на то, что использование справочной таблицы часто бывает эффективным, тем не менее, оно может привести к серьезному штрафу, если вычисление, которое заменяет LUT, относительно простое. Время извлечения из памяти и сложность требований к памяти могут увеличить время работы приложения и сложность системы по сравнению с тем, что потребовалось бы для прямого вычисления формулы. Возможность загрязнения кеша также может стать проблемой. Обращения к большим таблицам почти наверняка приведут к промаху кэша . Это явление становится все более серьезной проблемой, поскольку процессоры опережают память. Аналогичная проблема возникает при рематериализации , оптимизации компилятора . В некоторых средах, таких как язык программирования Java, поиск в таблице может быть еще более затратным из-за обязательной проверки границ, включающей дополнительное сравнение и переход для каждого поиска.
Есть два фундаментальных ограничения на то, когда можно создать таблицу поиска для требуемой операции. Одним из них является объем доступной памяти: невозможно создать таблицу поиска, превышающую пространство , доступное для таблицы, хотя можно создать таблицы поиска на диске за счет времени поиска. Другой — это время, необходимое для вычисления значений таблицы в первом экземпляре; хотя это обычно нужно сделать только один раз, если это занимает слишком много времени, это может сделать использование таблицы поиска неподходящим решением. Однако, как указывалось ранее, во многих случаях таблицы могут быть определены статически.
Кэши хранилища (включая дисковые кеши для файлов или кеши процессора для кода или данных) также работают как таблица поиска. Таблица построена с использованием очень быстрой памяти вместо того, чтобы храниться в более медленной внешней памяти, и поддерживает две части данных для поддиапазона битов, составляющих адрес внешней памяти (или диска) (в частности, самые младшие биты любого возможного внешнего адреса) :
Одиночный (быстрый) поиск выполняется для чтения тега в таблице поиска по индексу, указанному младшими битами желаемого адреса внешней памяти, и для определения того, попал ли адрес памяти в кэш. Когда попадание найдено, доступ к внешней памяти не требуется (за исключением операций записи, когда может потребоваться асинхронное обновление кэшированного значения в более медленную память через некоторое время или если позиция в кэше должна быть заменена для кэширования другой). адрес).
В цифровой логике интерполяционная таблица может быть реализована с помощью мультиплексора , строки выбора которого управляются сигналом адреса, а входы которого являются значениями элементов, содержащихся в массиве. Эти значения могут быть либо жестко заданы, как в ASIC , предназначение которых зависит от функции, либо предоставлены D-защелками , которые позволяют настраивать значения. ( ПЗУ , СППЗУ , ЭСППЗУ или ОЗУ .)
n - битная LUT может кодировать любую n -входную логическую функцию , сохраняя таблицу истинности функции в LUT. Это эффективный способ кодирования функций булевой логики , а LUT с 4-6 битами на входе фактически являются ключевым компонентом современных программируемых вентильных матриц (FPGA), которые обеспечивают реконфигурируемые аппаратные логические возможности .
В системах сбора данных и управления справочные таблицы обычно используются для выполнения следующих операций:
В некоторых системах полиномы также могут быть определены вместо таблиц поиска для этих вычислений.
Исследование, описанное в статье про Таблица поиска как структура данных, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое Таблица поиска как структура данных и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных
Комментарии
Оставить комментарий
Структуры данных
Термины: Структуры данных