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

нема опису редагування
'''Таблиця пошуку''' ( {{lang-en|lookup table}} - — це [[структура даних]], зазвичай [[Масив (структура даних)|масив]] або [[асоціативний масив]], використовувана з метою замінити обчислення на операцію простого пошуку . Збільшення швидкості може бути значним, оскільки отримати дані з пам'яті часто швидше, ніж виконати трудомісткі обчислення.
 
== Історія ==
До появи комп'ютерів таблиці значень використовувались для прискорення обчислень складних функцій, таких як [[тригонометрія]], [[Десятковий логарифм|логарифми]] та функції статистичної щільності. <ref>{{Cite book|url=|title=The History of Mathematical Tables From Sumer to Spreadsheets|date=October 2, 2003|editor-last=Campbell-Kelly|editor-first=Martin|editor2-last=Croarken|editor2-first=Mary|editor3-last=Robson|editor3-first=Eleanor|edition=1st|location=New York, USA|bibcode=|doi=|isbn=978-0-19-850841-0|oclc=}}
</ref>
 
У стародавній (499 &nbsp;р. н. &nbsp;е.) Індії [[Аріабхата I|Аріябхата]] створив одну з перших {{Нп|Таблиця синусів Аріябхати|таблиць синусів|en|Āryabhaṭa's sine table}}, яку він закодував у системі числення на основі санскриту. У 493 році нашої ери {{Нп|Вікторій Аквітанський||ru|Викторий Аквитанский}} написав таблицю множення на 98 стовпців, яка давала ([[Римська система числення|римськими числами]] ) добуток кожного числа на числа від 2 до 50, а рядки були "«списком чисел, починаючи з однієї тисячі, зменшуючись на сотню до однієї сотні, потім зменшуючись на десять до десяти, потім на одиницю до одиниці, а потім дроби до 1/144"»<ref>Maher, David. W. J. and John F. Makowski. "«[https://ecommons.luc.edu/cgi/viewcontent.cgi?article=1024&context=classicalstudies_facpubs Literary Evidence for Roman Arithmetic With Fractions]"», 'Classical Philology' (2001) Vol. 96 No. 4 (2001) pp. 376–399376—399. (See page p.383.)</ref>. Сучасних школярів часто навчають запам'ятовувати "«[[Таблиця множення|таблицю множення]]"», щоб уникнути обчислень найчастіше використовуваних чисел (до 9х9 або 12х12).
 
На початку історії комп'ютерів операції з [[Ввід/вивід|введення/виведення]] були особливо повільними -&nbsp;— навіть порівняно зі швидкістю процесора того часу. Мало сенс зменшити дорогі операції зчитування за допомогою ручного [[Кеш|кешування]], створивши або статичні таблиці пошуку (вбудовані в програму), або динамічні попередньо налаштовані масиви, що містять лише елементи даних, які зустрічаються найчастіше. Незважаючи на впровадження загальносистемного кешування, яке тепер автоматизує цей процес, таблиці пошуку на рівні застосунків все ще можуть підвищити продуктивність для елементів даних, які змінюються рідко, або зовсім не змінюються.
 
Таблиці пошуку були однією з найбільш ранніх функцій, реалізованих у комп’ютернихкомп'ютерних [[Електронний аркуш|електронних таблицях.]] Первісна версія [[VisiCalc]] (1979) серед первинних 20 функцій мала функцію <code>LOOKUP</code>. <ref>[https://vlookupweek.wordpress.com/2012/03/31/bill-jelen-from-1979-visicalc-and-lookup/ Bill Jelen: "«From 1979&nbsp;— VisiCalc and LOOKUP"»!], by MrExcel East, March 31, 2012</ref> Це було продовжено в наступних поколіннях електронних таблиць, таких як [[Microsoft Excel]], і доповнено спеціалізованими функціями <code>VLOOKUP</code> та <code>HLOOKUP</code> для спрощення пошуку у вертикальній чи горизонтальній таблиці.
 
== Особливості використання ==
Класичний приклад використання таблиць пошуку -&nbsp;— обчислення значень [[Тригонометричні функції|тригонометричних функцій]], наприклад, [[Тригонометричні функції|синуса]]. Його безпосереднє обчислення може дуже уповільнити роботу [[Застосунок|застосунку]]. Щоб цього уникнути, застосунок при першому запуску заздалегідь обчислює певну кількість значень синуса, наприклад, для всіх цілих градусів. Потім, коли програмі знадобиться значення синуса, вона використовує таблицю пошуку, щоб отримати приблизне значення синуса з пам'яті, замість того щоб обчислювати його значення (наприклад, за допомогою [[Ряд (математика)|рядів]]). Таблиці пошуку також використовуються в математичних [[Співпроцесор|співпроцесорах]]; помилка в таблиці пошуку в процесорах [[Pentium]] фірми [[Intel]] призвела до сумнозвісної [[Помилка Pentium FDIV|помилки]], яка зменшує точність операції ділення.
 
Задовго до того, як таблиці пошуку з'явилися в програмуванні, вони вже [[Математичні таблиці|використовувалися]] людьми для полегшення ручних обчислень. Особливо були поширені [[Логарифм|таблиці логарифмів]], а також тригонометричних і статистичних функцій.
 
Існує проміжне рішення, коли використовують таблицю пошуку в поєднанні з простими обчисленнями -&nbsp;— [[Інтерполяція|інтерполяцією]] . Це дозволяє знаходити точніше значення між двома обчисленими заздалегідь точками. Витрати часу трохи зростуть, але натомість буде забезпечена більша точність обчислень. Також цю техніку можна застосовувати для зменшення розмірів таблиці пошуку без втрат точності.
 
Таблиці пошуку широко використовуються також у комп'ютерній обробці зображень (в цій галузі відповідні таблиці зазвичай називають «палітрами»).
 
Важливо зазначити, що використання таблиць пошуку в тих завданнях, в яких вони неефективні, призводить до зниження швидкості роботи. Це відбувається не тільки тому, що отримання даних з пам'яті виявляється повільнішим, ніж їх обчислення, але й тому, що таблиця пошуку може зайняти всю [[Оперативна пам'ять|пам'ять]] і переповнити [[кеш]]. Якщо таблиця велика, кожне звернення до неї, швидше за все, буде призводити до [[Кеш процесора|промаху кешу]]. В деяких мовах програмування (наприклад, в [[Java]]) звернення до таблиці пошуку може бути навіть більш «дорогим» через обов'язковість перевірки меж, що включає додаткові порівняння і розгалуження для кожної операції пошуку.
 
Є два фундаментальних обмеження на створення таблиць пошуку. Перше -&nbsp;— це загальна кількість доступної пам'яті: таблиця повинна вміщатися в наявний обсяг, хоча можна зробити таблицю пошуку і на диску, збільшивши тим самим час операції пошуку. Інше обмеження -&nbsp;— це час, необхідний для створення таблиці пошуку при першому запуску -&nbsp;— хоча зазвичай ця операція потрібна тільки один раз, вона може забирати занадто багато часу, що робить використання таблиць пошуку непідхожим рішенням.
 
== Приклади застосування ==
 
==Приклади застосування==
=== Обчислення синуса ===
Більшість комп'ютерів підтримують тільки основні [[Операція (математика)|арифметичні операції]] і не можуть обчислити значення синуса безпосередньо. Замість цього для обчислення значення синуса з високим ступенем точності вони використовують метод [[CORDIC]] або [[ряд Тейлора]]:
 
: <math>\sin x = x - \frac{x^3}{6} + \frac{x^5}{120} - \frac{x^7}{5040}+\ldots</math>
 
Однак таке обчислення може зайняти багато часу, особливо на повільному процесорі, і існує безліч напрямків, наприклад, [[комп'ютерна графіка]], в яких щосекунди необхідно обчислювати значення тисяч синусів. Поширене рішення -&nbsp;— заздалегідь обчислити таблицю значень синуса, і потім знаходження синуса числа зведеться до вибору найближчого до цього числа аргументу з таблиці (відповідне значення функції буде близьким до правильного значенням, тому що синус -&nbsp;— [[Неперервна функція|неперервна]] і обмежена функція). Наприклад:
''real array'' sine_table[-1000..1000]
'''for''' x '''from''' -1000 '''to''' 1000
'''return''' sine_table[round(1000 * x / pi)]
[[Файл:Interpolation_example_linear.svg|праворуч|міні| Лінійна інтерполяція функції синуса на деякому діапазоні. ]]
Таблиця вимагає багато пам'яті -&nbsp;— наприклад, якщо використовуються [[Число з рухомою комою|числа з рухомою комою]] подвійної точності, то знадобиться {{Unité|16000|байт}}. Можна використати меншу кількість точок, але тоді точність впаде. Доброю практикою в такому випадку є [[лінійне наближення]] .
 
Ось приклад лінійної апроксимації:
'''function''' lookup_sine(x)
x1 := floor(x*1000/pi)
y2 := sine_table[x1+1]
'''return''' y1 + (y2-y1)*(x/1000/pi-x1)
При використанні інтерполяції часто вигідно використовувати нерівномірний розподіл даних: в тих місцях, де функція найближча до прямої, брати мало точок для обчислення функції, якщо ж [[Кривина (математика)|кривина]] функції велика -&nbsp;— брати більше точок з цього діапазону, щоб апроксимація була ближча до реальної кривої (див . також статтю [[Інтерполяція]] ).
 
Приклад таблиці синусів ([[C (мова програмування)|мовою програмування {{nbsp}} C]] ): <source lang="c">
// 8-бітна таблиця синусяв
// 8-битная таблица синусов
const unsigned char sinetable[256] = {
128,131,134,137,140,143,146,149,152,156,159,162,165,168,171,174,
};
</source> При цьому значення синуса з [-1; 1] відображені в цілочисельний діапазон від мінімального 0 до максимального 255, нулю відповідає 128. У переважній більшості процесорів операції з цілими числами відбуваються значно швидше, ніж з рухомою комою.
 
==Примітки==
{{примітки}}
 
==Див. також==
* [[Райдужна таблиця]]
[[Категорія:Структури даних]]
[[Категорія:Оптимізація програмного забезпечення]]