Интерполяционный поиск — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация)
м (rollbackEdits.php mass rollback)
 
(не показано 14 промежуточных версий 4 участников)
Строка 1: Строка 1:
=== Идея ===
+
== Идея ==
Рассмотрим задачу: найти слово в словаре. Если оно начинается на букву "А", то никто не будет искать его в середине, а откроет словарь ближе к началу. В чем разница между алгоритмом человека и другими? Отличие заключается в том, что алгоритмы вроде двоичного не делают различий между "немного больше" и "существенно больше".
+
Рассмотрим задачу: найти слово в словаре. Если оно начинается на букву "А", то никто не будет искать его в середине, а откроет словарь ближе к началу. В чём разница между алгоритмом человека и другими? Отличие заключается в том, что алгоритмы вроде двоичного поиска не делают различий между "немного больше" и "существенно больше".
  
=== Алгоритм ===
+
== Алгоритм ==
[[Файл:Search.jpg|thumb|300px|Нахождение медианы]]
+
Пусть <tex> a </tex> {{---}} отсортированный массив из <tex> n </tex> чисел, <tex> x </tex> {{---}} значение, которое нужно найти. Поиск происходит подобно [[Целочисленный двоичный поиск|двоичному поиску]], но вместо деления области поиска на две примерно равные части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Если известно, что <tex> x </tex> лежит между <tex> a_l </tex> и <tex> a_r </tex>, то следующая проверка выполняется примерно на расстоянии <tex dpi = "170"> \frac{x - a_l}{a_r - a_l} \cdot</tex> <tex> (r - l) </tex> от <tex> l </tex>.
Пусть <tex> a </tex> - отсортированный массив чисел из <tex> n </tex> чисел, <tex> x </tex> - значение, которое нужно найти.
 
Если известно, что <tex> x </tex> лежит между <tex> a_l </tex> и <tex> a_r </tex>, то следующая проверка выполняется примерно на расстоянии <tex dpi = "180"> \frac{x - a_l}{a_r - a_l} </tex> от <tex> l </tex>.
 
  
=== Время работы ===
+
Формула для разделительного элемента <tex> m </tex> получается из следующего уравнения: <tex dpi = "170"> \frac{x - a_l}{m - l} = \frac{a_r - a_l}{r - l} </tex> {{---}}
При условии, что значения элементов близки к арифметической прогрессии, за один шаг алгоритм уменьшает количество проверяемых элементов с <tex> n </tex> до <tex> \sqrt n </tex>. <br/>
+
откуда следует, что <tex> m = l + </tex> <tex dpi = "170"> \frac{x - a_l}{a_r - a_l} \cdot</tex> <tex> (r - l) </tex>. На рисунке внизу показано, из каких соображений берется такая оценка. Интерполяционный поиск основывается на том, что наш массив представляет из себя что-то наподобии арифметической прогрессии.
Поэтому среднее время работы алгоритма: <tex> O(\log \log n) </tex>. <br/>
+
[[Файл:interpolation_search_from_gshark.png|500px|center|Размещение разделительного элемента]]
При "плохих" исходных данных (например, при экспоненциальном возрастании элементов) время работы может ухудшиться до <tex> O(n) </tex>.
 
  
=== Реализация ===
+
== Псевдокод ==
Приведем код функции <tex> \mathrm{interpolation\_search(a, n, x)} </tex> на языке C++.
+
<code>
<code>
+
'''int''' interpolationSearch(a : '''int[]''', key : '''int''') <font color=green> // a должен быть отсортирован </font>
int interpolation_search(double* a, int n, double x)
+
  left = 0 <font color=green> // левая граница поиска (будем считать, что элементы массива нумеруются с нуля) </font>
{
+
   right = a.length - 1 <font color=green> // правая граница поиска </font>
   int l = 0;
 
  int r = n - 1;
 
  int m;
 
 
   
 
   
   while (a[l] <= x && x <= a[r])
+
   '''while''' a[left] < key '''and''' key < a[right]
  {
+
     mid = left + (key - a[left]) * (right - left) / (a[right] - a[left]) <font color=green> // индекс элемента, с которым будем проводить сравнение </font>
     m = l + (x - a[l]) / (a[r] - a[l]) * (r - l);
+
    '''if''' a[mid] < key
 +
      left = mid + 1
 +
    '''else if''' a[mid] > key
 +
      right = mid - 1
 +
    '''else'''
 +
      '''return''' mid
 
   
 
   
    if (a[m] == x)
+
  '''if''' a[left] == key
      return m;
+
    '''return''' left
    if (a[m] < x)
+
  '''else if''' a[right] == key
      l = m + 1;
+
     '''return''' right
     else
+
  '''else'''
      r = m - 1;
+
    '''return''' -1 <font color=green>// если такого элемента в массиве нет </font>
  }
+
</code>
+
 
  if (a[l] == x)
+
== Время работы ==
    return l;
+
Асимптотически интерполяционный поиск превосходит по своим характеристикам бинарный. Если ключи распределены случайным образом, то за один шаг алгоритм уменьшает количество проверяемых элементов с <tex> n </tex> до <tex> \sqrt n </tex>
  else
+
<ref>[http://www.cs.technion.ac.il/~itai/publications/Algorithms/p550-perl.pdf Interpolation Search {{---}} A LogLogN Search]</ref>. То есть, после <tex>k</tex>-ого шага количество проверяемых элементов уменьшается до <tex dpi = 170>n^{\frac{1}{2^k}}</tex>. Значит, остаётся проверить только 2 элемента (и закончить на этом поиск), когда <tex dpi = 150>\frac{1}{2^k} = \log_{n}2 = \frac{1}{\log_{2}n} </tex>. Из этого вытекает, что количество шагов, а значит, и время работы составляет <tex>O(\log \log n)</tex>.
    return -1; // not found
+
 
}
+
При "плохих" исходных данных (например, при экспоненциальном возрастании элементов) время работы может ухудшиться до <tex> O(n) </tex>.
</code>
+
 
 +
Эксперименты показали, что интерполяционный поиск не настолько снижает количество выполняемых сравнений, чтобы компенсировать требуемое для дополнительных вычислений время (пока таблица не очень велика). Кроме того, типичные таблицы недостаточно случайны, да и разница между значениями <tex>\log \log n</tex> и <tex>\log n</tex> становится значительной только при очень больших <tex>n</tex>. На практике при поиске в больших файлах оказывается выгодным на ранних стадиях применять интерполяционный поиск, а затем, когда диапазон существенно уменьшится, переходить к двоичному.
 +
 
 +
===Пример работы вместе с сравнением с бинарным поиском===
 +
[[Файл:ip_vs_bin_from_gshark.png|700px|center|Сравнение бинарного и интерполирующего поисков]]
 +
 
 +
==Примечания==
 +
<references/>
 +
 
 +
==Источники информации==
 +
* Дональд Кнут {{---}} Искусство программирования. Том 3. Сортировка и поиск. / Knuth D.E. {{---}} The Art of Computer Programming. Vol. 3. Sorting and Searching.
 +
*[http://en.wikipedia.org/wiki/Interpolation_search Wikipedia {{---}} Interpolation search]
 +
*[http://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D0%BE%D0%BB%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B8%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA Википедия {{---}} Интерполирующий поиск]
  
=== Полезные ссылки ===
+
[[Категория: Дискретная математика и алгоритмы]]
Д.Э. Кнут: [http://books.google.com/books?id=92rW-nktlbgC&pg=PA452&lpg=PA453&ots=jChsP2sutg&dq=%D0%BA%D0%BD%D1%83%D1%82+%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D0%BE%D0%BB%D1%8F%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9+%D0%BF%D0%BE%D0%B8%D1%81%D0%BA&hl=ru&ie=windows-1251&output=html Искусство программирования (том 3)] <br/>
+
[[Категория: Алгоритмы поиска]]
Wikipedia: [http://en.wikipedia.org/wiki/Interpolation_search Interpolation search]
 

Текущая версия на 19:41, 4 сентября 2022

Идея

Рассмотрим задачу: найти слово в словаре. Если оно начинается на букву "А", то никто не будет искать его в середине, а откроет словарь ближе к началу. В чём разница между алгоритмом человека и другими? Отличие заключается в том, что алгоритмы вроде двоичного поиска не делают различий между "немного больше" и "существенно больше".

Алгоритм

Пусть [math] a [/math] — отсортированный массив из [math] n [/math] чисел, [math] x [/math] — значение, которое нужно найти. Поиск происходит подобно двоичному поиску, но вместо деления области поиска на две примерно равные части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Если известно, что [math] x [/math] лежит между [math] a_l [/math] и [math] a_r [/math], то следующая проверка выполняется примерно на расстоянии [math] \frac{x - a_l}{a_r - a_l} \cdot[/math] [math] (r - l) [/math] от [math] l [/math].

Формула для разделительного элемента [math] m [/math] получается из следующего уравнения: [math] \frac{x - a_l}{m - l} = \frac{a_r - a_l}{r - l} [/math] — откуда следует, что [math] m = l + [/math] [math] \frac{x - a_l}{a_r - a_l} \cdot[/math] [math] (r - l) [/math]. На рисунке внизу показано, из каких соображений берется такая оценка. Интерполяционный поиск основывается на том, что наш массив представляет из себя что-то наподобии арифметической прогрессии.

Размещение разделительного элемента

Псевдокод

int interpolationSearch(a : int[], key : int)  // a должен быть отсортирован 
  left = 0  // левая граница поиска (будем считать, что элементы массива нумеруются с нуля) 
  right = a.length - 1  // правая граница поиска 

  while a[left] < key and key < a[right]
    mid = left + (key - a[left]) * (right - left) / (a[right] - a[left])  // индекс элемента, с которым будем проводить сравнение 
    if a[mid] < key
      left = mid + 1
    else if a[mid] > key
      right = mid - 1
    else
      return mid

  if a[left] == key
    return left
  else if a[right] == key
    return right
  else
    return -1 // если такого элемента в массиве нет 

Время работы

Асимптотически интерполяционный поиск превосходит по своим характеристикам бинарный. Если ключи распределены случайным образом, то за один шаг алгоритм уменьшает количество проверяемых элементов с [math] n [/math] до [math] \sqrt n [/math] [1]. То есть, после [math]k[/math]-ого шага количество проверяемых элементов уменьшается до [math]n^{\frac{1}{2^k}}[/math]. Значит, остаётся проверить только 2 элемента (и закончить на этом поиск), когда [math]\frac{1}{2^k} = \log_{n}2 = \frac{1}{\log_{2}n} [/math]. Из этого вытекает, что количество шагов, а значит, и время работы составляет [math]O(\log \log n)[/math].

При "плохих" исходных данных (например, при экспоненциальном возрастании элементов) время работы может ухудшиться до [math] O(n) [/math].

Эксперименты показали, что интерполяционный поиск не настолько снижает количество выполняемых сравнений, чтобы компенсировать требуемое для дополнительных вычислений время (пока таблица не очень велика). Кроме того, типичные таблицы недостаточно случайны, да и разница между значениями [math]\log \log n[/math] и [math]\log n[/math] становится значительной только при очень больших [math]n[/math]. На практике при поиске в больших файлах оказывается выгодным на ранних стадиях применять интерполяционный поиск, а затем, когда диапазон существенно уменьшится, переходить к двоичному.

Пример работы вместе с сравнением с бинарным поиском

Сравнение бинарного и интерполирующего поисков

Примечания

Источники информации