Интерполяционный поиск
 | Эта статья нуждается в дополнительных цитатах для проверки . ( сентябрь 2017 г. ) |
Интерполяционный поиск — алгоритм поиска по ключа в массиве, упорядоченном числовым значениям, присвоенным ключам ( значениям ключей ). Впервые он был описан У.В. Петерсоном в 1957 году. [1] Интерполяционный поиск напоминает метод, с помощью которого люди ищут в телефонном справочнике имя (значение ключа, по которому упорядочиваются записи в книге): на каждом этапе алгоритм вычисляет, где в оставшемся пространстве поиска может находиться искомый элемент, на основе ключа значения на границах пространства поиска и значение искомого ключа, обычно посредством линейной интерполяции . Значение ключа, фактически найденное в этой расчетной позиции, затем сравнивается с искомым значением ключа. Если оно не равно, то в зависимости от сравнения оставшееся пространство поиска сокращается до части до или после предполагаемой позиции. Этот метод будет работать только в том случае, если расчеты размера различий между значениями ключей разумны.
 Визуализация алгоритма поиска интерполяции, в котором 24 является целевым значением. | |
| Сорт | Алгоритм поиска |
|---|---|
| Структура данных | Множество |
| Худшая производительность | На ) |
| Лучшая производительность | О (1) |
| Средняя производительность | O (журнал(журнал( n ))) [2] |
| Наихудшая пространственная сложность | О (1) |
| Оптимальный | Да |
Для сравнения, бинарный поиск всегда выбирает середину оставшегося пространства поиска, отбрасывая одну или другую половину, в зависимости от сравнения ключа, найденного в предполагаемой позиции, и искомого ключа — он не требует числовых значений ключей, просто с ними полный порядок. Оставшееся пространство поиска сокращается до части до или после предполагаемой позиции. Линейный поиск использует равенство только при сравнении элементов один за другим с самого начала, игнорируя любую сортировку.
В среднем интерполяционный поиск состоит из сравнений log(log( n )) (если элементы распределены равномерно), где n — количество элементов, подлежащих поиску. В худшем случае (например, когда числовые значения ключей увеличиваются в геометрической прогрессии) количество сравнений может достигать O ( n ).
При интерполяционно-последовательном поиске интерполяция используется для поиска элемента рядом с искомым, затем линейный поиск используется для поиска точного элемента.
Производительность
[ редактировать ]Используя обозначение big-O , производительность алгоритма интерполяции на наборе данных размера n равна O ( n ); однако в предположении равномерного распределения данных в линейном масштабе, используемом для интерполяции, можно показать, что производительность равна O (log log n ). [3] [4] [5] Однако динамический интерполяционный поиск возможен за время o (log log n ) с использованием новой структуры данных. [6]
Практическая эффективность интерполяционного поиска зависит от того, перевешивается ли уменьшенное количество зондов более сложными вычислениями, необходимыми для каждого зонда. Это может быть полезно для поиска записи в большом отсортированном файле на диске, где каждая проверка включает в себя поиск по диску и выполняется намного медленнее, чем арифметика интерполяции.
Структуры индексов, такие как B-деревья, также сокращают количество обращений к диску и чаще используются для индексации данных на диске, отчасти потому, что они могут индексировать многие типы данных и могут обновляться в Интернете . Тем не менее, интерполяционный поиск может быть полезен, когда приходится искать определенные отсортированные, но неиндексированные наборы данных на диске.
Адаптация к различным наборам данных
[ редактировать ]Когда ключи сортировки набора данных представляют собой равномерно распределенные числа, линейную интерполяцию реализовать несложно, и она найдет индекс, очень близкий к искомому значению.
С другой стороны, для телефонной книги, отсортированной по имени, простой подход к интерполяционному поиску неприменим. Однако те же принципы высокого уровня все еще применимы: можно оценить положение имени в телефонной книге, используя относительную частоту букв в именах, и использовать это в качестве зондирующего местоположения.
Некоторые реализации интерполяционного поиска могут работать не так, как ожидалось, если существует ряд одинаковых значений ключей. Самая простая реализация интерполяционного поиска не обязательно будет выбирать первый (или последний) элемент такого прогона.
Поиск по книгам
[ редактировать ]Преобразование имен в телефонной книге в какой-либо номер явно не обеспечит равномерное распределение номеров (за исключением огромных усилий, таких как сортировка имен и присвоение им имени № 1, имени № 2 и т. д.), и, кроме того, Хорошо известно, что некоторые имена встречаются гораздо чаще, чем другие (Смит, Джонс). То же самое и со словарями, где слов, начинающихся на одни буквы, гораздо больше, чем на другие. Некоторые издатели стараются подготовить аннотации на полях или даже вырезают боковые части страниц, чтобы показать маркеры для каждой буквы, чтобы можно было сразу выполнить сегментированную интерполяцию.
Пример реализации
[ редактировать ]Следующий пример кода C++ представляет собой простую реализацию. На каждом этапе он вычисляет положение зонда, а затем, как и при двоичном поиске, перемещает либо верхнюю, либо нижнюю границу, чтобы определить меньший интервал, содержащий искомое значение. В отличие от бинарного поиска, который гарантирует уменьшение вдвое размера интервала на каждом этапе, ошибочная интерполяция может снизить эффективность O( n ).
#include <cassert>/*arr[low, high) is sorted, search the data "key" in this array,if "key" is found, return the corresponding index (NOT necessarily the highest possible index);if "key" is not found, just return low - 1How to verify that the algorithm is correct?Proof:(finiteness: after one loop, the width of [low, high] decreases strictly )Fist, high <--- high - 1scenario 1. when low = highscenario 2. when low < high, arr[low] = arr[high]scenario 3. when low < high, arr[low] < arr[high], key < arr[low] or key > arr[high]scenario 4. when low < high, arr[low] < arr[high], arr[low] <= key <= arr[high]Now let's analyze scenario 4:Once entering the "while" loop, low <= middle <= high let's analyse after one loop(if we don't return), whether "low > high" will occur After one loop: case a1: "low" branch has been executed in this loop arr[middle] < key <= arr[high] so we have middle < high so after this loop, we have low <= high case a2: "high" branch has been executed in this loop arr[low] <= key < arr[middle] so we have low < middle so after this loop, we have low <= high so after one loop(if we don't return), we have "low <= high" when we exit the "while" loop: case b1: arr[low] >= arr[high] In the last loop, if "low" branch is executed, we know arr[low - 1] < k <= arr[high] arr[low] >= arr[high] low <= high so we have arr[low - 1] < k <= arr[low] = arr[high] In the last loop, if "high" branch is executed, we know arr[low] <= key < arr[high + 1] arr[low] >= arr[high] low <= high so we have arr[low] = arr[high] <= key < arr[high + 1] case b2: (arr[low] < arr[high]) && (arr[low] > key): In the last loop, "low" must have been changed so we have arr[low - 1] < key so we have arr[low - 1] < key < arr[low] case b3: (arr[low] < arr[high]) && (key > arr[high]) In the last loop, "high" must have been changed so we have key < arr[high + 1] so we have arr[low] < arr[high] < key < arr[high + 1]*/template <typename T>static Rank interpolation_search_v001(T* arr, const T& key, Rank low, Rank high){ high -= 1; int middle; int initial_low = low; while ((arr[low] < arr[high]) && (arr[low] <= key) && (key <= arr[high])) { middle = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low]); assert((low <= middle) && (middle <= high)); if (arr[middle] < key) low = middle + 1; else if (key < arr[middle]) high = middle - 1; else return middle; } if (key == arr[low]) return low; else return initial_low - 1;}/*search "key" in the sorted array arr[low, high),return: the highest index i such that arr[i] <= keyHow to verify that the algorithm is correct?Proof:finiteness: after one loop, the width of [low, high] decreases strictly Fist, high <---- high - 1scenario 1. when low = highscenario 2. when low < high, key < arr[low] or arr[high] <= keyscenario 3. when low < high, arr[low] <= key < arr[high]Now let's analyze scenario 3:Once entering the "while" loop, low <= middle < highwhen we exit the "while" loop: case a1: key < arr[low] so "low" is changed in the last loop, we know arr[low - 1] <= key < arr[low] case a2: arr[high] <= key so "high" is changed in the last loop, we know key < arr[high], impossibleconclusion: we should return "low - 1"*/template <typename T> static Rank interpolation_search_v002(T* arr, const T& key, Rank low, Rank high) { high -= 1; assert(low <= high); Rank middle; if(key < arr[low]) { return low - 1; } if(arr[high] <= key) { return high; } // now low < high , arr[low] <= key < arr[high] while ((arr[low] <= key) && (key < arr[high])) { middle = low + ((high - low) * (key - arr[low])) / (arr[high] - arr[low]); assert((low <= middle) && (middle < high)); if(key < arr[middle]) { high = middle; } else { low = middle + 1; } } return low - 1;}Обратите внимание, что после проверки списка по индексу Mid в целях администрирования управления циклом этот код устанавливает либо высокий , либо низкий уровень не в середине , а в соседнем индексе, местоположение которого затем проверяется во время следующей итерации. Поскольку значение соседней записи не будет сильно отличаться, вычисление интерполяции не сильно улучшится за счет этой одношаговой настройки за счет дополнительной ссылки на удаленную память, например диск.
Каждая итерация приведенного выше кода требует от пяти до шести сравнений (дополнительное количество связано с повторениями, необходимыми для различения трех состояний < > и = посредством двоичных сравнений в отсутствие трехстороннего сравнения ) плюс некоторая запутанная арифметика, в то время как Алгоритм двоичного поиска может быть написан с одним сравнением на итерацию и использует только тривиальную целочисленную арифметику. Таким образом, он будет искать массив из миллиона элементов с не более чем двадцатью сравнениями (включая доступ к медленной памяти, где хранятся элементы массива); Чтобы обойти это, интерполяционный поиск, как написано выше, будет разрешено не более трех итераций.
См. также
[ редактировать ]- Линейный поиск
- Бинарный поиск
- Интерполированный бинарный поиск , [7] гибрид интерполированного поиска и бинарного поиска
- Экспоненциальный поиск
- Троичный поиск
- Хэш-таблица
- метод Ньютона
- Flashsort , использующий распределение значений для сортировки, а не для поиска.
Ссылки
[ редактировать ]- ^ В. В. Петерсон (1957). «Адресация запоминающих устройств с произвольным доступом». IBM J. Res. Дев . 1 (2): 130–146. дои : 10.1147/рд.12.0130 .
- ^ Саймон Юань. «Понимание сложности интерполяционного поиска, семинар по расширенным алгоритмам и структурам данных» (PDF) .
- ^ Вайс, Марк Аллен (2006). Структуры данных и решение проблем с использованием Java , Пирсон Аддисон Уэсли
- ^ Арменакис, AC, Гари, LE, Гупта, RD, Адаптация метода поиска корня для поиска упорядоченных дисковых файлов, BIT Numerical Mathematics, Том 25, номер 4 / Декабрь 1985.
- ^ Седжвик, Роберт (1990), Алгоритмы на C , Аддисон-Уэсли
- ^ Андерссон, Арне и Кристер Маттссон. «Динамический интерполяционный поиск за o (log log n ) время». В книге «Автоматы, языки и программирование» под редакцией Анджея Лингаса, Рольфа Карлссона и Сванте Карлссона, 700:15–27. Конспекты лекций по информатике. Шпрингер Берлин/Гейдельберг, 1993. дои : 10.1007/3-540-56939-1_58
- ^ Мохаммед, Аднан Сахер; Амрахов, Шахин Эмра; Челеби, Фатих В. (1 октября 2021 г.). «Интерполированный двоичный поиск: эффективный алгоритм гибридного поиска в упорядоченных наборах данных» . Инженерные науки и технологии . 24 (5): 1072–1079. дои : 10.1016/j.jestch.2021.02.009 . ISSN 2215-0986 .