Інтерполяційний алгоритм пошуку

Інтерполяційний алгоритм пошуку — алгоритм для пошуку за заданим ключем в індексованому масиві, який впорядкований за значенням ключів. Це схоже до того, як люди шукають певне ім'я в телефонній книзі. На кожному кроці обчислюється, в якому полі пошуку може бути елемент, базуючись на граничних значеннях цього поля і ключі шуканого елемента, зазвичай за допомогою лінійної інтерполяції. Ключ на вибраній позиції порівнюється з шуканим ключем і, якщо вони не рівні, то залежно від результату порівняння, простір пошуку зводиться до частини до або після даного ключа. Цей метод працюватиме тільки в тому випадку, коли порівняння між ключами є розумним.

До прикладу, двійковий пошук завжди вибирає середину в даному полі пошуку і відкидає одну з половин, порівнюючи значення середини з шуканим. А лінійний пошук порівнює всі елементи один за одним, ігноруючи впорядкованість.

В середньому інтерполяційний пошук робить log(log(n)) порівнянь(якщо елементи є рівномірно розприділеними), де n- кількість елементів. В найгіршому випадку їх кількість може виростати до O(n).


Продуктивність

Використовуючи нотацію Ландау, продуктивність алгоритму інтерполяції на наборі даних розміру N рівна O(N). Однак, припускаючи рівномірний розподіл даних по шкалі інтерполяції, можна показати, що показник будеO(log log N).[1][2][3]. Проте, пошук динамічною інтерполяцією можливий в час o(log log n), використовуючи нову структуру даних.[4]

Практичне виконання інтерполяції пошуку залежить від того, чи зменшена кількість кроків не буде вимагати складних обчислень, необхідних для кожного кроку. Таке може бути корисним для пошуку у великих відсортованих файлах на диску, де кожен крок включає пошук у диску, що є набагато повільнішим, від арифметичної інтерполяції.

Індексовані структури даних, такі як Б-дерево, також зменшують кількість звернень до диска і частіше використовуються для індексації даних на диску, бо вони можуть індексувати багато типів даних і можуть бути оновленими онлайн. Тим не менше інтерполяційний пошук може використовуватись для пошуку у відсортованому але не індексованому наборі даних.


Робота з різними наборами даних

Коли відсортовані ключі у наборі даних є рівномірно розподіленими номерами, лінійна інтерполяція є простою в реалізації та можна знайти індекс дуже близько до шуканої величини З іншого боку, для телефонної книги, відсортованої за іменами, прямий підхід до інтерполяційного пошуку не може бути застосований. Але тут можна застосувати схожий високорівневий принцип: можна визначити позицію ім'я в телефонній книзі використовуючи залежні набори букв в іменах для визначення положення наступного кроку. Деякі реалізації інтерполяційного пошуку можуть не працювати, якщо в наборі є однакові значення ключів. Найпростіша реалізація інтерполяційного пошуку необов'язково вибере потрібний елемент в такому наборі.


Пошук на основі книг

Перетворення імен у телефонній книзі не зможе добитися того, щоб кожне ім'я надавало доступ до одного номера і імена мали рівномірний розподіл (крім як сортувати імена і називати їх 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 порівнянь(додаткове для розрізняння трьох станів < > і =), плюс деяку «брудну» арифметику, коли двійковий пошук можна написати з одним порівнянням і цілочисельною арифметикою на ітерації. Бінарний пошук дозволи би знайти елемент у масиві з мільйона елементів не більше, ніж за двадцять порівнянь, проте інтерполяційний пошук, такий як реалізовано вище дозволить зробити це максимум в три ітерації.


Див. також


Посилання
  1. Weiss, Mark Allen (2006). Data structures and problem solving using Java, Pearson Addison Wesley
  2. 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.
  3. Sedgewick, Robert (1990), Algorithms in C, Addison-Wesley
  4. 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.

Додаткові посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.