Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Інтерполяційний алгоритм пошуку — алгоритм для пошуку за заданим ключем в індексованому масиві, який впорядкований за значенням ключів. Це схоже до того, як люди шукають певне ім'я в телефонній книзі. На кожному кроці обчислюється, в якому полі пошуку може бути елемент, базуючись на граничних значеннях цього поля і ключі шуканого елемента, зазвичай за допомогою лінійної інтерполяції. Ключ на вибраній позиції порівнюється з шуканим ключем і, якщо вони не рівні, то залежно від результату порівняння, простір пошуку зводиться до частини до або після даного ключа. Цей метод працюватиме тільки в тому випадку, коли порівняння між ключами є розумним.
До прикладу, двійковий пошук завжди вибирає середину в даному полі пошуку і відкидає одну з половин, порівнюючи значення середини з шуканим. А лінійний пошук порівнює всі елементи один за одним, ігноруючи впорядкованість.
В середньому інтерполяційний пошук робить log(log(n)) порівнянь(якщо елементи є рівномірно розприділеними), де n- кількість елементів. В найгіршому випадку їх кількість може виростати до O(n).
Продуктивність
Використовуючи нотацію Ландау, продуктивність алгоритму інтерполяції на наборі даних розміру N рівна O(N). Однак, припускаючи рівномірний розподіл даних по шкалі інтерполяції, можна показати, що показник будеO(log log N).. Проте, пошук динамічною інтерполяцією можливий в час o(log log n), використовуючи нову структуру даних.
Практичне виконання інтерполяції пошуку залежить від того, чи зменшена кількість кроків не буде вимагати складних обчислень, необхідних для кожного кроку. Таке може бути корисним для пошуку у великих відсортованих файлах на диску, де кожен крок включає пошук у диску, що є набагато повільнішим, від арифметичної інтерполяції.
Індексовані структури даних, такі як Б-дерево, також зменшують кількість звернень до диска і частіше використовуються для індексації даних на диску, бо вони можуть індексувати багато типів даних і можуть бути оновленими онлайн. Тим не менше інтерполяційний пошук може використовуватись для пошуку у відсортованому але не індексованому наборі даних.
Робота з різними наборами даних
Коли відсортовані ключі у наборі даних є рівномірно розподіленими номерами, лінійна інтерполяція є простою в реалізації та можна знайти індекс дуже близько до шуканої величини З іншого боку, для телефонної книги, відсортованої за іменами, прямий підхід до інтерполяційного пошуку не може бути застосований. Але тут можна застосувати схожий високорівневий принцип: можна визначити позицію ім'я в телефонній книзі використовуючи залежні набори букв в іменах для визначення положення наступного кроку. Деякі реалізації інтерполяційного пошуку можуть не працювати, якщо в наборі є однакові значення ключів. Найпростіша реалізація інтерполяційного пошуку необов'язково вибере потрібний елемент в такому наборі.
Пошук на основі книг
Перетворення імен у телефонній книзі не зможе добитися того, щоб кожне ім'я надавало доступ до одного номера і імена мали рівномірний розподіл (крім як сортувати імена і називати їх name #1, name #2, і т. д.), також відомо, що деякі імена зустрічаються набагато частіше, ніж інші. Така ж ситуація зі словниками, де є багато наборів букв, з яких починається набагато більше слів, ніж з інших. Багато видавців ідуть на значні зусилля, навіть на розрізання одного краю, щоб була можливою усна інтерполяція з першого погляду.
Приклад реалізації
Найпростіша реалізація на . На кожній стадії, тут вираховується позиція і потім, як і в двійковому пошуку, рухається або вище, або нижче цієї позиції. На відміну від двійкового пошуку, гарантій щодо розміру інтервалу на кожному кроці немає ніяких, тому в найгіршому випадку виходить O(n). Варто відмітити, що ця реалізація передбачає, що масив відсортований у зростанні. Якщо навпаки, в цій реалізації виникнуть помилки.
template <typename T> int interpolation_search (T * arr, int size, T key) { if ( size < 0 || ! arr ) // not the best way to handle this case, but it return -1 ; // serves to draw attention to it possibly happening. unsigned long long low = 0 ; unsigned long long high = size - 1 ; unsigned long long mid ; while ( ! (arr [high] == arr [low] || key < arr [low] || arr [high] < key) ) { mid = low + (key - arr [low]) * ((high - low) / ( arr [high] - arr [low])) ; if ( arr [mid] < key ) low = mid + 1 ; else if ( key < arr [mid] ) high = mid - 1 ; else return mid ; } if ( key == arr [low] ) return low ; else return -1 ; } Кожна ітерація в коді вимагає від 5 до 6 порівнянь(додаткове для розрізняння трьох станів < > і =), плюс деяку «брудну» арифметику, коли двійковий пошук можна написати з одним порівнянням і цілочисельною арифметикою на ітерації. Бінарний пошук дозволи би знайти елемент у масиві з мільйона елементів не більше, ніж за двадцять порівнянь, проте інтерполяційний пошук, такий як реалізовано вище дозволить зробити це максимум в три ітерації.
Див. також
Посилання
- Weiss, Mark Allen (2006). Data structures and problem solving using Java, Pearson Addison Wesley
- Armenakis, A. C., Garey, L. E., Gupta, R. D., An adaptation of a root finding method to searching ordered disk files, BIT Numerical Mathematics, Volume 25, Number 4 / December, 1985.
- Sedgewick, Robert (1990), Algorithms in C, Addison-Wesley
- Andersson, Arne, and Christer Mattsson. ‘Dynamic Interpolation Search in o(log log n) Time’. In Automata, Languages and Programming, edited by Andrzej Lingas, Rolf Karlsson, and Svante Carlsson, 700:15-27. Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 1993. http://dx.doi.org/10.1007/3-540-56939-1_58.
Додаткові посилання
- Interpolation search [ 4 лютого 2012 у Wayback Machine.]
- National Institute of Standards and Technology [ 22 січня 2009 у Wayback Machine.]
- Interpolation Search — A Log LogN Search [ 1 липня 2015 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Interpolyacijnij algoritm poshuku algoritm dlya poshuku za zadanim klyuchem v indeksovanomu masivi yakij vporyadkovanij za znachennyam klyuchiv Ce shozhe do togo yak lyudi shukayut pevne im ya v telefonnij knizi Na kozhnomu kroci obchislyuyetsya v yakomu poli poshuku mozhe buti element bazuyuchis na granichnih znachennyah cogo polya i klyuchi shukanogo elementa zazvichaj za dopomogoyu linijnoyi interpolyaciyi Klyuch na vibranij poziciyi porivnyuyetsya z shukanim klyuchem i yaksho voni ne rivni to zalezhno vid rezultatu porivnyannya prostir poshuku zvoditsya do chastini do abo pislya danogo klyucha Cej metod pracyuvatime tilki v tomu vipadku koli porivnyannya mizh klyuchami ye rozumnim Vizualizaciya interpolyacijnogo algoritm poshuku Do prikladu dvijkovij poshuk zavzhdi vibiraye seredinu v danomu poli poshuku i vidkidaye odnu z polovin porivnyuyuchi znachennya seredini z shukanim A linijnij poshuk porivnyuye vsi elementi odin za odnim ignoruyuchi vporyadkovanist V serednomu interpolyacijnij poshuk robit log log n porivnyan yaksho elementi ye rivnomirno rozpridilenimi de n kilkist elementiv V najgirshomu vipadku yih kilkist mozhe virostati do O n ProduktivnistVikoristovuyuchi notaciyu Landau produktivnist algoritmu interpolyaciyi na nabori danih rozmiru N rivna O N Odnak pripuskayuchi rivnomirnij rozpodil danih po shkali interpolyaciyi mozhna pokazati sho pokaznik budeO log log N Prote poshuk dinamichnoyu interpolyaciyeyu mozhlivij v chas o log log n vikoristovuyuchi novu strukturu danih Praktichne vikonannya interpolyaciyi poshuku zalezhit vid togo chi zmenshena kilkist krokiv ne bude vimagati skladnih obchislen neobhidnih dlya kozhnogo kroku Take mozhe buti korisnim dlya poshuku u velikih vidsortovanih fajlah na disku de kozhen krok vklyuchaye poshuk u disku sho ye nabagato povilnishim vid arifmetichnoyi interpolyaciyi Indeksovani strukturi danih taki yak B derevo takozh zmenshuyut kilkist zvernen do diska i chastishe vikoristovuyutsya dlya indeksaciyi danih na disku bo voni mozhut indeksuvati bagato tipiv danih i mozhut buti onovlenimi onlajn Tim ne menshe interpolyacijnij poshuk mozhe vikoristovuvatis dlya poshuku u vidsortovanomu ale ne indeksovanomu nabori danih Robota z riznimi naborami danihKoli vidsortovani klyuchi u nabori danih ye rivnomirno rozpodilenimi nomerami linijna interpolyaciya ye prostoyu v realizaciyi ta mozhna znajti indeks duzhe blizko do shukanoyi velichini Z inshogo boku dlya telefonnoyi knigi vidsortovanoyi za imenami pryamij pidhid do interpolyacijnogo poshuku ne mozhe buti zastosovanij Ale tut mozhna zastosuvati shozhij visokorivnevij princip mozhna viznachiti poziciyu im ya v telefonnij knizi vikoristovuyuchi zalezhni nabori bukv v imenah dlya viznachennya polozhennya nastupnogo kroku Deyaki realizaciyi interpolyacijnogo poshuku mozhut ne pracyuvati yaksho v nabori ye odnakovi znachennya klyuchiv Najprostisha realizaciya interpolyacijnogo poshuku neobov yazkovo vibere potribnij element v takomu nabori Poshuk na osnovi knigPeretvorennya imen u telefonnij knizi ne zmozhe dobitisya togo shob kozhne im ya nadavalo dostup do odnogo nomera i imena mali rivnomirnij rozpodil krim yak sortuvati imena i nazivati yih name 1 name 2 i t d takozh vidomo sho deyaki imena zustrichayutsya nabagato chastishe nizh inshi Taka zh situaciya zi slovnikami de ye bagato naboriv bukv z yakih pochinayetsya nabagato bilshe sliv nizh z inshih Bagato vidavciv idut na znachni zusillya navit na rozrizannya odnogo krayu shob bula mozhlivoyu usna interpolyaciya z pershogo poglyadu Priklad realizaciyiNajprostisha realizaciya na S Na kozhnij stadiyi tut virahovuyetsya poziciya i potim yak i v dvijkovomu poshuku ruhayetsya abo vishe abo nizhche ciyeyi poziciyi Na vidminu vid dvijkovogo poshuku garantij shodo rozmiru intervalu na kozhnomu kroci nemaye niyakih tomu v najgirshomu vipadku vihodit O n Varto vidmititi sho cya realizaciya peredbachaye sho masiv vidsortovanij u zrostanni Yaksho navpaki v cij realizaciyi viniknut pomilki template lt typename T gt int interpolation search T arr int size T key if size lt 0 arr not the best way to handle this case but it return 1 serves to draw attention to it possibly happening unsigned long long low 0 unsigned long long high size 1 unsigned long long mid while arr high arr low key lt arr low arr high lt key mid low key arr low high low arr high arr low if arr mid lt key low mid 1 else if key lt arr mid high mid 1 else return mid if key arr low return low else return 1 Kozhna iteraciya v kodi vimagaye vid 5 do 6 porivnyan dodatkove dlya rozriznyannya troh staniv lt gt i plyus deyaku brudnu arifmetiku koli dvijkovij poshuk mozhna napisati z odnim porivnyannyam i cilochiselnoyu arifmetikoyu na iteraciyi Binarnij poshuk dozvoli bi znajti element u masivi z miljona elementiv ne bilshe nizh za dvadcyat porivnyan prote interpolyacijnij poshuk takij yak realizovano vishe dozvolit zrobiti ce maksimum v tri iteraciyi Div takozhDvijkovij poshuk Hesh tablicyaPosilannyaWeiss Mark Allen 2006 Data structures and problem solving using Java Pearson Addison Wesley Armenakis A C Garey L E Gupta R D An adaptation of a root finding method to searching ordered disk files BIT Numerical Mathematics Volume 25 Number 4 December 1985 Sedgewick Robert 1990 Algorithms in C Addison Wesley Andersson Arne and Christer Mattsson Dynamic Interpolation Search in o log log n Time In Automata Languages and Programming edited by Andrzej Lingas Rolf Karlsson and Svante Carlsson 700 15 27 Lecture Notes in Computer Science Springer Berlin Heidelberg 1993 http dx doi org 10 1007 3 540 56939 1 58 Dodatkovi posilannyaInterpolation search 4 lyutogo 2012 u Wayback Machine National Institute of Standards and Technology 22 sichnya 2009 u Wayback Machine Interpolation Search A Log LogN Search 1 lipnya 2015 u Wayback Machine