30 423
редагування
Відмінності між версіями «Таблиця пошуку»
Перейти до навігації
Перейти до пошуку
нема опису редагування
|
'''Таблиця пошуку''' ({{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">
| |||