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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

В середньому інтерполяційний пошук робить 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.

Додаткові посилання[ред.ред. код]