Справочная таблица
В информатике справочная таблица (LUT) представляет собой массив , который заменяет вычисления во время выполнения более простой операцией индексации массива. Этот процесс называется «прямая адресация», и LUT отличаются от хэш-таблиц тем, что для извлечения значения с помощью ключа хеш-таблица будет хранить значение в слоте, где хеш -функция , т.е. используется для вычисления слота, в то время как в случае LUT значение сохраняется в слоте , поэтому к нему можно обращаться напрямую. [1] : 466 Экономия времени обработки может быть значительной, поскольку извлечение значения из памяти часто выполняется быстрее, чем выполнение «дорогих» вычислений или операций ввода/вывода . [2] Таблицы могут быть предварительно рассчитаны и сохранены в статическом хранилище программ, рассчитаны (или «предварительно выбраны» ) как часть фазы инициализации программы ( запоминание ) или даже сохранены в аппаратном обеспечении на платформах для конкретных приложений. Таблицы поиска также широко используются для проверки входных значений путем сопоставления со списком допустимых (или недопустимых) элементов в массиве и в некоторых языках программирования могут включать функции указателей (или смещения меток) для обработки совпадающих входных данных. ПЛИСтакже широко использовать реконфигурируемые аппаратно реализованные таблицы поиска для обеспечения программируемых аппаратных функций.
До появления компьютеров справочные таблицы значений использовались для ускорения ручных вычислений сложных функций, таких как тригонометрия , логарифмы и функции статистической плотности. [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 года.
