Таблиця пошуку

Таблиця пошуку ( англ. lookup table - це структура даних, зазвичай масив або асоціативний масив, використовувана з метою замінити обчислення на операцію простого пошуку . Збільшення швидкості може бути значним, оскільки отримати дані з пам'яті часто швидше, ніж виконати трудомісткі обчислення.

Класичний приклад використання таблиць пошуку - обчислення значень тригонометричних функцій, наприклад, синуса. Його безпосереднє обчислення може дуже уповільнити роботу застосунка. Щоб цього уникнути, застосунок при першому запуску заздалегідь обчислює певну кількість значень синуса, наприклад, для всіх цілих градусів. Потім, коли програмі знадобиться значення синуса, вона використовує таблицю пошуку, щоб отримати приблизне значення синуса з пам'яті, замість того щоб обчислювати його значення (наприклад, за допомогою рядів). Таблиці пошуку також використовуються в математичних співпроцесорах; помилка в таблиці пошуку в процесорах Pentium фірми Intel призвела до сумнозвісної помилки, яка зменшує точність операції ділення.

Задовго до того, як таблиці пошуку з'явилися в програмуванні, вони вже використовувалися людьми для полегшення ручних обчислень. Особливо були поширені таблиці логарифмів, а також тригонометричних і статистичних функцій.

Існує проміжне рішення, коли використовують таблицю пошуку в поєднанні з простими обчисленнями - інтерполяцією . Це дозволяє знаходити точніше значення між двома обчисленими заздалегідь точками. Витрати часу трохи зростуть, але натомість буде забезпечена більша точність обчислень. Також цю техніку можна застосовувати для зменшення розмірів таблиці пошуку без втрат точності.

Таблиці пошуку широко використовуються також у комп'ютерній обробці зображень (в цій галузі відповідні таблиці зазвичай називають «палітрами»).

Важливо зазначити, що використання таблиць пошуку в тих завданнях, в яких вони неефективні, призводить до зниження швидкості роботи. Це відбувається не тільки тому, що отримання даних з пам'яті виявляється повільнішим, ніж їх обчислення, але й тому, що таблиця пошуку може зайняти всю пам'ять і переповнити кеш. Якщо таблиця велика, кожне звернення до неї, швидше за все, буде призводити до промаху кешу. В деяких мовах програмування (наприклад, в Java) звернення до таблиці пошуку може бути навіть більш «дорогим» через обов'язковість перевірки меж, що включає додаткові порівняння і розгалуження для кожної операції пошуку.

Є два фундаментальних обмеження на створення таблиць пошуку. Перше - це загальна кількість доступної пам'яті: таблиця повинна вміщатися в наявний обсяг, хоча можна зробити таблицю пошуку і на диску, збільшивши тим самим час операції пошуку. Інше обмеження - це час, необхідний для створення таблиці пошуку при першому запуску - хоча зазвичай ця операція потрібна тільки один раз, вона може забирати занадто багато часу, що робить використання таблиць пошуку непідхожим рішенням.

Обчислення синуса

Більшість комп'ютерів підтримують тільки основні арифметичні операції і не можуть обчислити значення синуса безпосередньо. Замість цього для обчислення значення синуса з високим ступенем точності вони використовують метод CORDIC або ряд Тейлора:

$\sin x=x-{\frac {x^{3}}{6}}+{\frac {x^{5}}{120}}-{\frac {x^{7}}{5040}}+\ldots$

Однак таке обчислення може зайняти багато часу, особливо на повільному процесорі, і існує безліч напрямків, наприклад, комп'ютерна графіка, в яких щосекунди необхідно обчислювати значення тисяч синусів. Поширене рішення - заздалегідь обчислити таблицю значень синуса, і потім знаходження синуса числа зведеться до вибору найближчого до цього числа аргументу з таблиці (відповідне значення функції буде близьким до правильного значенням, тому що синус - неперервна і обмежена функція). Наприклад:

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. У переважній більшості процесорів операції з цілими числами відбуваються значно швидше, ніж з рухомою комою.