Відмінності між версіями «Таблиця пошуку»

Перейти до навігації Перейти до пошуку
[перевірена версія][перевірена версія]
'''Таблиця пошуку''' ({{lang-en|lookup table}} — це [[структура даних]], зазвичай [[Масив (структура даних)|масив]] або [[асоціативний масив]], використовувана з метою замінити обчислення на операцію простого пошуку . Збільшення швидкості може бути значним, оскільки отримати дані з пам'яті часто швидше, ніж виконати трудомісткі обчислення.
 
== Історія ==
Задовго до того, як таблиці пошуку з'явилися в програмуванні, вони вже [[Математичні таблиці|використовувалися]] людьми для полегшення ручних обчислень. Особливо були поширені [[Логарифм|таблиці логарифмів]], а також тригонометричних і статистичних функцій.
 
Існує проміжне рішення, коли використовують таблицю пошуку в поєднанні з простими обчисленнями — [[Інтерполяція|інтерполяцією]] . Це дозволяє знаходити точніше значення між двома обчисленими заздалегідь точками. Витрати часу трохи зростуть, але натомість буде забезпечена більша точність обчислень. Також цю техніку можна застосовувати для зменшення розмірів таблиці пошуку без втрат точності.
 
Таблиці пошуку широко використовуються також у комп'ютерній обробці зображень (в цій галузі відповідні таблиці зазвичай називають «палітрами»).
'''return''' sine_table[round(1000 * x / pi)]
[[Файл:Interpolation_example_linear.svg|праворуч|міні| Лінійна інтерполяція функції синуса на деякому діапазоні. ]]
Таблиця вимагає багато пам'яті — наприклад, якщо використовуються [[Число з рухомою комою|числа з рухомою комою]] подвійної точності, то знадобиться {{Unité|16000|байт}}. Можна використати меншу кількість точок, але тоді точність впаде. Доброю практикою в такому випадку є [[лінійне наближення]] .
 
Ось приклад лінійної апроксимації:
y2 := sine_table[x1+1]
'''return''' y1 + (y2-y1)*(x/1000/pi-x1)
При використанні інтерполяції часто вигідно використовувати нерівномірний розподіл даних: в тих місцях, де функція найближча до прямої, брати мало точок для обчислення функції, якщо ж [[Кривина (математика)|кривина]] функції велика — брати більше точок з цього діапазону, щоб апроксимація була ближча до реальної кривої (див . також статтю [[Інтерполяція]]).
 
Приклад таблиці синусів ([[C (мова програмування)|мовою програмування {{nbsp}} C]]): <source lang="c">