Таблиця пошуку
Таблиця пошуку (англ. lookup table) — це структура даних, зазвичай масив або асоціативний масив, використовувана з метою замінити обчислення на операцію простого пошуку. Збільшення швидкості може бути значним, оскільки отримати дані з пам'яті часто швидше, ніж виконати трудомісткі обчислення.
До появи комп'ютерів таблиці значень використовувались для прискорення обчислень складних функцій, таких як тригонометрія, логарифми та функції статистичної щільності.[1]
У стародавній (499 р. н. е.) Індії Аріябхата створив одну з перших таблиць синусів[en], яку він закодував у системі числення на основі санскриту. У 493 році нашої ери Вікторій Аквітанський[ru] написав таблицю множення на 98 стовпців, яка давала (римськими числами) добуток кожного числа на числа від 2 до 50, а рядки були «списком чисел, починаючи з однієї тисячі, зменшуючись на сотню до однієї сотні, потім зменшуючись на десять до десяти, потім на одиницю до одиниці, а потім дроби до 1/144»[2]. Сучасних школярів часто навчають запам'ятовувати «таблицю множення», щоб уникнути обчислень найчастіше використовуваних чисел (до 9х9 або 12х12).
На початку історії комп'ютерів операції з введення/виведення були особливо повільними — навіть порівняно зі швидкістю процесора того часу. Мало сенс зменшити дорогі операції зчитування за допомогою ручного кешування, створивши або статичні таблиці пошуку (вбудовані в програму), або динамічні попередньо налаштовані масиви, що містять лише елементи даних, які зустрічаються найчастіше. Незважаючи на впровадження загальносистемного кешування, яке тепер автоматизує цей процес, таблиці пошуку на рівні застосунків все ще можуть підвищити продуктивність для елементів даних, які змінюються рідко, або зовсім не змінюються.
Таблиці пошуку були однією з найбільш ранніх функцій, реалізованих у комп'ютерних електронних таблицях. Первісна версія VisiCalc (1979) серед первинних 20 функцій мала функцію LOOKUP.[3] Це було продовжено в наступних поколіннях електронних таблиць, таких як Microsoft Excel, і доповнено спеціалізованими функціями VLOOKUP та HLOOKUP для спрощення пошуку у вертикальній чи горизонтальній таблиці.
Класичний приклад використання таблиць пошуку — обчислення значень тригонометричних функцій, наприклад, синуса. Його безпосереднє обчислення може дуже уповільнити роботу застосунку. Щоб цього уникнути, застосунок при першому запуску заздалегідь обчислює певну кількість значень синуса, наприклад, для всіх цілих градусів. Потім, коли програмі знадобиться значення синуса, вона використовує таблицю пошуку, щоб отримати приблизне значення синуса з пам'яті, замість того щоб обчислювати його значення (наприклад, за допомогою рядів). Таблиці пошуку також використовуються в математичних співпроцесорах; помилка в таблиці пошуку в процесорах Pentium фірми Intel призвела до сумнозвісної помилки, яка зменшує точність операції ділення.
Задовго до того, як таблиці пошуку з'явилися в програмуванні, вони вже використовувалися людьми для полегшення ручних обчислень. Особливо були поширені таблиці логарифмів, а також тригонометричних і статистичних функцій.
Існує проміжне рішення, коли використовують таблицю пошуку в поєднанні з простими обчисленнями — інтерполяцією. Це дозволяє знаходити точніше значення між двома обчисленими заздалегідь точками. Витрати часу трохи зростуть, але натомість буде забезпечена більша точність обчислень. Також цю техніку можна застосовувати для зменшення розмірів таблиці пошуку без втрат точності.
Таблиці пошуку широко використовуються також у комп'ютерній обробці зображень (в цій галузі відповідні таблиці зазвичай називають «палітрами»).
Важливо зазначити, що використання таблиць пошуку в тих завданнях, в яких вони неефективні, призводить до зниження швидкості роботи. Це відбувається не тільки тому, що отримання даних з пам'яті виявляється повільнішим, ніж їх обчислення, але й тому, що таблиця пошуку може зайняти всю пам'ять і переповнити кеш. Якщо таблиця велика, кожне звернення до неї, швидше за все, буде призводити до промаху кешу. В деяких мовах програмування (наприклад, в Java) звернення до таблиці пошуку може бути навіть більш «дорогим» через обов'язковість перевірки меж, що включає додаткові порівняння і розгалуження для кожної операції пошуку.
Є два фундаментальних обмеження на створення таблиць пошуку. Перше — це загальна кількість доступної пам'яті: таблиця повинна вміщатися в наявний обсяг, хоча можна зробити таблицю пошуку і на диску, збільшивши тим самим час операції пошуку. Друге обмеження — це час, необхідний для створення таблиці пошуку при першому запуску — хоча зазвичай ця операція потрібна тільки один раз, вона може забирати занадто багато часу, що робить використання таблиць пошуку непідхожим рішенням.
Більшість комп'ютерів підтримують тільки основні арифметичні операції і не можуть обчислити значення синуса безпосередньо. Замість цього для обчислення значення синуса з високим ступенем точності вони використовують метод 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-бітна таблиця синусів
const unsigned char sinetable[256] = {
128,131,134,137,140,143,146,149,152,156,159,162,165,168,171,174,
176,179,182,185,188,191,193,196,199,201,204,206,209,211,213,216,
218,220,222,224,226,228,230,232,234,236,237,239,240,242,243,245,
246,247,248,249,250,251,252,252,253,254,254,255,255,255,255,255,
255,255,255,255,255,255,254,254,253,252,252,251,250,249,248,247,
246,245,243,242,240,239,237,236,234,232,230,228,226,224,222,220,
218,216,213,211,209,206,204,201,199,196,193,191,188,185,182,179,
176,174,171,168,165,162,159,156,152,149,146,143,140,137,134,131,
128,124,121,118,115,112,109,106,103,99, 96, 93, 90, 87, 84, 81,
79, 76, 73, 70, 67, 64, 62, 59, 56, 54, 51, 49, 46, 44, 42, 39,
37, 35, 33, 31, 29, 27, 25, 23, 21, 19, 18, 16, 15, 13, 12, 10,
9, 8, 7, 6, 5, 4, 3, 3, 2, 1, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 3, 4, 5, 6, 7, 8,
9, 10, 12, 13, 15, 16, 18, 19, 21, 23, 25, 27, 29, 31, 33, 35,
37, 39, 42, 44, 46, 49, 51, 54, 56, 59, 62, 64, 67, 70, 73, 76,
79, 81, 84, 87, 90, 93, 96, 99, 103,106,109,112,115,118,121,124
};
При цьому значення синуса з [-1; 1] відображені в цілочисельний діапазон від мінімального 0 до максимального 255, нулю відповідає 128. У переважній більшості процесорів операції з цілими числами відбуваються значно швидше, ніж з рухомою комою.
- ↑ Campbell-Kelly, Martin; Croarken, Mary; Robson, Eleanor, ред. (2 жовтня 2003). The History of Mathematical Tables From Sumer to Spreadsheets (вид. 1st). New York, USA. ISBN 978-0-19-850841-0.
- ↑ Maher, David. W. J. and John F. Makowski. «Literary Evidence for Roman Arithmetic With Fractions», 'Classical Philology' (2001) Vol. 96 No. 4 (2001) pp. 376—399. (See page p.383.)
- ↑ Bill Jelen: «From 1979 — VisiCalc and LOOKUP»!, by MrExcel East, March 31, 2012