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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 +
|+
 +
|-align="center"
 +
|'''НЕТ ВОЙНЕ'''
 +
|-style="font-size: 16px;"
 +
|
 +
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 +
 +
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 +
 +
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 +
 +
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 +
 +
''Антивоенный комитет России''
 +
|-style="font-size: 16px;"
 +
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 +
|-style="font-size: 16px;"
 +
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 +
|}
 +
 
== Идея ==
 
== Идея ==
 
Рассмотрим задачу: найти слово в словаре. Если оно начинается на букву "А", то никто не будет искать его в середине, а откроет словарь ближе к началу. В чём разница между алгоритмом человека и другими? Отличие заключается в том, что алгоритмы вроде двоичного поиска не делают различий между "немного больше" и "существенно больше".
 
Рассмотрим задачу: найти слово в словаре. Если оно начинается на букву "А", то никто не будет искать его в середине, а откроет словарь ближе к началу. В чём разница между алгоритмом человека и другими? Отличие заключается в том, что алгоритмы вроде двоичного поиска не делают различий между "немного больше" и "существенно больше".

Версия 06:30, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Идея

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

Алгоритм

Пусть [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]. На практике при поиске в больших файлах оказывается выгодным на ранних стадиях применять интерполяционный поиск, а затем, когда диапазон существенно уменьшится, переходить к двоичному.

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

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

Примечания

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