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

Перейти до навігації Перейти до пошуку
нема опису редагування
(Створено шляхом перекладу сторінки «Таблица поиска»)
 
'''Таблиця пошуку''' ( {{lang-en|lookup table}} - це [[структура даних]], зазвичай [[Масив (структура даних)|масив]] або [[асоціативний масив]], використовувана з метою замінити обчислення на операцію простого пошуку . Збільшення швидкості може бути значним, оскільки отримати дані з пам'яті часто швидше, ніж виконати трудомісткі обчислення.
 
== Історія ==
Класичний приклад використання таблиць пошуку - обчислення значень [[Тригонометричні функції|тригонометричних функцій]], наприклад, [[Тригонометричні функції|синуса]]. Його безпосереднє обчислення може дуже уповільнити роботу [[Застосунок|застосунка]]. Щоб цього уникнути, застосунок при першому запуску заздалегідь обчислює певну кількість значень синуса, наприклад, для всіх цілих градусів. Потім, коли програмі знадобиться значення синуса, вона використовує таблицю пошуку, щоб отримати приблизне значення синуса з пам'яті, замість того щоб обчислювати його значення (наприклад, за допомогою [[Ряд (математика)|рядів]]). Таблиці пошуку також використовуються в математичних [[Співпроцесор|співпроцесорах]]; помилка в таблиці пошуку в процесорах [[Pentium]] фірми [[Intel]] призвела до сумнозвісної [[Помилка Pentium FDIV|помилки]], яка зменшує точність операції ділення.
До появи комп'ютерів таблиці значень використовувались для прискорення обчислень складних функцій, таких як [[тригонометрія]], [[Десятковий логарифм|логарифми]] та функції статистичної щільності. <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 р. н. е.) Індії [[Аріабхата 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–399. (See page p.383.)</ref>. Сучасних школярів часто навчають запам'ятовувати "[[Таблиця множення|таблицю множення]]", щоб уникнути обчислень найчастіше використовуваних чисел (до 9х9 або 12х12).
 
На початку історії комп'ютерів операції з [[Ввід/вивід|введення/виведення]] були особливо повільними - навіть порівняно зі швидкістю процесора того часу. Мало сенс зменшити дорогі операції зчитування за допомогою ручного [[Кеш|кешування]], створивши або статичні таблиці пошуку (вбудовані в програму), або динамічні попередньо налаштовані масиви, що містять лише елементи даних, які зустрічаються найчастіше. Незважаючи на впровадження загальносистемного кешування, яке тепер автоматизує цей процес, таблиці пошуку на рівні застосунків все ще можуть підвищити продуктивність для елементів даних, які змінюються рідко, або зовсім не змінюються.
 
Таблиці пошуку були однією з найбільш ранніх функцій, реалізованих у комп’ютерних [[Електронний аркуш|електронних таблицях.]] Первісна версія [[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 – VisiCalc and LOOKUP"!], by MrExcel East, March 31, 2012</ref> Це було продовжено в наступних поколіннях електронних таблиць, таких як [[Microsoft Excel]], і доповнено спеціалізованими функціями <code>VLOOKUP</code> та <code>HLOOKUP</code> для спрощення пошуку у вертикальній чи горизонтальній таблиці.
 
==Особливості використання==
Класичний приклад використання таблиць пошуку - обчислення значень [[Тригонометричні функції|тригонометричних функцій]], наприклад, [[Тригонометричні функції|синуса]]. Його безпосереднє обчислення може дуже уповільнити роботу [[Застосунок|застосунказастосунку]]. Щоб цього уникнути, застосунок при першому запуску заздалегідь обчислює певну кількість значень синуса, наприклад, для всіх цілих градусів. Потім, коли програмі знадобиться значення синуса, вона використовує таблицю пошуку, щоб отримати приблизне значення синуса з пам'яті, замість того щоб обчислювати його значення (наприклад, за допомогою [[Ряд (математика)|рядів]]). Таблиці пошуку також використовуються в математичних [[Співпроцесор|співпроцесорах]]; помилка в таблиці пошуку в процесорах [[Pentium]] фірми [[Intel]] призвела до сумнозвісної [[Помилка Pentium FDIV|помилки]], яка зменшує точність операції ділення.
 
Задовго до того, як таблиці пошуку з'явилися в програмуванні, вони вже [[Математичні таблиці|використовувалися]] людьми для полегшення ручних обчислень. Особливо були поширені [[Логарифм|таблиці логарифмів]], а також тригонометричних і статистичних функцій.
Є два фундаментальних обмеження на створення таблиць пошуку. Перше - це загальна кількість доступної пам'яті: таблиця повинна вміщатися в наявний обсяг, хоча можна зробити таблицю пошуку і на диску, збільшивши тим самим час операції пошуку. Інше обмеження - це час, необхідний для створення таблиці пошуку при першому запуску - хоча зазвичай ця операція потрібна тільки один раз, вона може забирати занадто багато часу, що робить використання таблиць пошуку непідхожим рішенням.
 
== Приклади застосування==
=== Обчислення синуса ===
Більшість комп'ютерів підтримують тільки основні [[Операція (математика)|арифметичні операції]] і не можуть обчислити значення синуса безпосередньо. Замість цього для обчислення значення синуса з високим ступенем точності вони використовують метод [[CORDIC]] або [[ряд Тейлора]]:
 
При використанні інтерполяції часто вигідно використовувати нерівномірний розподіл даних: в тих місцях, де функція найближча до прямої, брати мало точок для обчислення функції, якщо ж [[Кривина (математика)|кривина]] функції велика - брати більше точок з цього діапазону, щоб апроксимація була ближча до реальної кривої (див . також статтю [[Інтерполяція]] ).
 
== Приклади ==
Приклад таблиці синусів ([[C (мова програмування)|мовою програмування {{nbsp}} C]] ): <source lang="c">
// 8-битная таблица синусов
79, 81, 84, 87, 90, 93, 96, 99, 103,106,109,112,115,118,121,124
};
</source> При цьому значення синуса з [-1; 1] відображені в цілочисельний діапазон від мінімального 0 до максимального 255, нулю відповідає 128. У переважній більшості процесорів операції з цілими числами відбуваються значно швидше, ніж з рухомою комою.
[[Категорія:Структури даних]]
[[Категорія:СторінкиОптимізація ізпрограмного неперевіреними перекладамизабезпечення]]

Навігаційне меню