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

Перейти до навігації Перейти до пошуку
[перевірена версія][перевірена версія]
м (стиль, правопис)
Важливо зазначити, що використання таблиць пошуку в тих завданнях, в яких вони неефективні, призводить до зниження швидкості роботи. Це відбувається не тільки тому, що отримання даних з пам'яті виявляється повільнішим, ніж їх обчислення, але й тому, що таблиця пошуку може зайняти всю [[Оперативна пам'ять|пам'ять]] і переповнити [[кеш]]. Якщо таблиця велика, кожне звернення до неї, швидше за все, буде призводити до [[Кеш процесора|промаху кешу]]. В деяких мовах програмування (наприклад, в [[Java]]) звернення до таблиці пошуку може бути навіть більш «дорогим» через обов'язковість перевірки меж, що включає додаткові порівняння і розгалуження для кожної операції пошуку.
 
Є два фундаментальних обмеження на створення таблиць пошуку. Перше — це загальна кількість доступної пам'яті: таблиця повинна вміщатися в наявний обсяг, хоча можна зробити таблицю пошуку і на диску, збільшивши тим самим час операції пошуку. ІншеДруге обмеження — це час, необхідний для створення таблиці пошуку при першому запуску — хоча зазвичай ця операція потрібна тільки один раз, вона може забирати занадто багато часу, що робить використання таблиць пошуку непідхожим рішенням.
 
== Приклади застосування ==
'''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">
// 8-бітна таблиця синусявсинусів
const unsigned char sinetable[256] = {
128,131,134,137,140,143,146,149,152,156,159,162,165,168,171,174,
Отримано з https://uk.wikipedia.org/wiki/Таблиця_пошуку