Поиск с интерполяцией - Interpolation search

Поиск с интерполяцией является алгоритм за поиск для ключа в массиве, который был упорядоченный числовыми значениями, присвоенными клавишам (ключевые ценности). Впервые он был описан В. В. Петерсоном в 1957 году.[1] Поиск с интерполяцией напоминает метод, с помощью которого люди ищут телефонный справочник для имени (значение ключа, по которому упорядочиваются записи в книге): на каждом шаге алгоритм вычисляет, где в оставшихся пространство поиска искомый элемент может быть основан на значениях ключа на границах области поиска и значении искомого ключа, обычно через линейная интерполяция. Значение ключа, фактически найденное в этой предполагаемой позиции, затем сравнивается с искомым значением ключа. Если оно не равно, то в зависимости от сравнения оставшееся пространство поиска сокращается до части до или после оценочной позиции. Этот метод будет работать только в том случае, если расчет размера различий между ключевыми значениями является разумным.

По сравнению, бинарный поиск всегда выбирает середину оставшегося пространства поиска, отбрасывая ту или иную половину, в зависимости от сравнения между ключом, найденным в предполагаемой позиции, и искомым ключом - для этого не требуются числовые значения для ключей, только их общий порядок . Оставшееся пространство поиска сокращается до части до или после оценочной позиции. В линейный поиск использует равенство только потому, что сравнивает элементы один за другим с самого начала, игнорируя любую сортировку.

В среднем поиск с интерполяцией составляет около log (log (п)) сравнения (если элементы распределены равномерно), где п это количество элементов для поиска. В худшем случае (например, когда числовые значения клавиш экспоненциально растут) он может составить до О (п) сравнения.

При последовательном поиске с интерполяцией интерполяция используется для поиска элемента рядом с искомым, затем линейный поиск используется для поиска точного объекта.

Спектакль

С помощью нотация big-O, производительность алгоритма интерполяции на наборе данных размером п является О(п); однако при условии равномерного распределения данных в линейной шкале, используемой для интерполяции, производительность может быть показана как О(журнал журнал п).[2][3][4] Однако поиск с динамической интерполяцией возможен в о(журнал журнал п) время с использованием новой структуры данных.[5]

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

Индексные структуры вроде B-деревья также сокращают количество обращений к диску и чаще используются для индексации данных на диске частично, потому что они могут индексировать многие типы данных и могут быть обновлены онлайн. Тем не менее, поиск с интерполяцией может быть полезен, когда кто-то вынужден искать определенные отсортированные, но неиндексированные наборы данных на диске.

Адаптация к разным наборам данных

Когда ключи сортировки для набора данных представляют собой равномерно распределенные числа, линейная интерполяция проста в реализации и найдет индекс, очень близкий к искомому значению.

С другой стороны, для телефонной книги, отсортированной по имени, простой подход к поиску с интерполяцией не применим. Тем не менее, те же самые высокоуровневые принципы все еще могут применяться: можно оценить положение имени в телефонной книге, используя относительную частоту букв в именах, и использовать это в качестве места проверки.

Некоторые реализации поиска с интерполяцией могут работать не так, как ожидалось, если существует серия с одинаковыми ключевыми значениями. Самая простая реализация поиска с интерполяцией не обязательно будет выбирать первый (или последний) элемент такого прогона.

Книжный поиск

Преобразование имен в телефонной книге в какой-то номер явно не даст номеров, имеющих равномерное распределение (за исключением огромных усилий, таких как сортировка имен и наименование их имя №1, имя №2 и т. Д.), И, кроме того, это Хорошо известно, что одни имена встречаются гораздо чаще, чем другие (Смит, Джонс). Точно так же и со словарями, где слов, начинающихся с одних букв, гораздо больше, чем с других. Некоторые издатели стараются подготовить аннотации на полях или даже вырезать края страниц, чтобы показать маркеры для каждой буквы, чтобы можно было сразу выполнить сегментированную интерполяцию.

Пример реализации

Следующее C ++ пример кода - простая реализация. На каждом этапе он вычисляет положение зонда, а затем, как и при двоичном поиске, перемещает либо верхнюю, либо нижнюю границу, чтобы определить меньший интервал, содержащий искомое значение. В отличие от двоичного поиска, который гарантирует уменьшение вдвое размера интервала на каждом этапе, ошибочная интерполяция может снизить / i-случайную эффективность O (п).

/*T должен реализовывать операторы -,! =, ==,> =, <= и <такие, что> =, <=,! =, == и <определяют общий порядок на T итакой, что(tm - tl) * k / (th - tl)является числом от 0 до k (включительно) для любых tl, tm, th в T с tl <= tm <= th, tl! = th.arr должны быть отсортированы в соответствии с этим порядком. возвращает индекс i такой, что arr [i] == key или -1, если нет i, удовлетворяющего этому требованию.*/шаблон <typename Т>int интерполяция_поиск(Т обр[], int размер, Т ключ){    int низкий = 0;    int высоко = размер - 1;    int середина;    пока ((обр[высоко] != обр[низкий]) && (ключ >= обр[низкий]) && (ключ <= обр[высоко])) {        середина = низкий + ((ключ - обр[низкий]) * (высоко - низкий) / (обр[высоко] - обр[низкий]));        если (обр[середина] < ключ)            низкий = середина + 1;        еще если (ключ < обр[середина])            высоко = середина - 1;        еще            возвращаться середина;    }    если (ключ == обр[низкий])        возвращаться низкий ;    еще        возвращаться -1;}

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

Каждая итерация приведенного выше кода требует от пяти до шести сравнений (дополнительные из-за повторений, необходимых для различения трех состояний <> и = посредством двоичных сравнений в отсутствие трехстороннее сравнение ) плюс некоторая беспорядочная арифметика, а алгоритм двоичного поиска может быть записан с одним сравнением на итерацию и использует только тривиальную целочисленную арифметику. Таким образом, он будет искать в массиве из миллиона элементов с не более чем двадцатью сравнениями (включая доступ к медленной памяти, где хранятся элементы массива); чтобы превзойти это, поиск с интерполяцией, как написано выше, допускал бы не более трех итераций.

Смотрите также

Рекомендации

  1. ^ В. В. Петерсон (1957). «Адресация для хранения с произвольным доступом». IBM J. Res. Dev. 1 (2): 130–146. Дои:10.1147 / от.12.0130.
  2. ^ Вайс, Марк Аллен (2006). Структуры данных и решение проблем с использованием Java, Пирсон Эддисон Уэсли
  3. ^ Арменакис, А. К., Гарей, Л. Е., Гупта, Р. Д., Адаптация метода поиска корня к поиску упорядоченных файлов на диске, BIT Numerical Mathematics, Volume 25, Number 4 / December, 1985.
  4. ^ Седжвик, Роберт (1990), Алгоритмы на C, Эддисон-Уэсли
  5. ^ Андерссон, Арне и Кристер Маттссон. ‘Динамический поиск интерполяции в о(журнал журнал п) Время'. В «Автоматы, языки и программирование», под редакцией Анджей Лингас, Рольф Карлссон и Сванте Карлссон, 700: 15–27. Конспект лекций по информатике. Springer Berlin / Heidelberg, 1993. Дои:10.1007/3-540-56939-1_58

внешняя ссылка