Войти
Поиск с интерполяцией - алгоритм ithm для поиска ключа в массиве, который был упорядочен по числовым значениям, присвоенным ключам (значениям ключей). Впервые он был описан У. В. Петерсоном в 1957 году. Поиск с интерполяцией напоминает метод, с помощью которого люди ищут имя в телефонном справочнике (значение ключа, по которому упорядочиваются записи в книге): на каждом шаге алгоритм вычисляет где в оставшемся пространстве поиска может быть искомый элемент на основе значений ключа на границах пространства поиска и значения искомого ключа, обычно посредством линейной интерполяции. Значение ключа, фактически найденное в этой предполагаемой позиции, затем сравнивается с искомым значением ключа. Если оно не равно, то в зависимости от сравнения оставшееся пространство поиска сокращается до части до или после оценочной позиции. Этот метод будет работать только в том случае, если расчет размера различий между ключевыми значениями является разумным.
Для сравнения, двоичный поиск всегда выбирает середину оставшегося пространства поиска, отбрасывая одну или другую половину, в зависимости от сравнения между ключом, найденным в предполагаемой позиции, и искомым ключом - не требует числовых значений для ключей, только их общий порядок. Оставшееся пространство поиска сокращается до части до или после оценочной позиции. Линейный поиск использует равенство только в том случае, когда он сравнивает элементы один за другим с самого начала, игнорируя любую сортировку.
В среднем поиск с интерполяцией выполняет примерно log (log (n)) сравнений (если элементы распределены равномерно), где n - количество элементов для поиска. В худшем случае (например, когда числовые значения ключей увеличиваются экспоненциально) может быть выполнено до O (n) сравнений.
При последовательном поиске с интерполяцией интерполяция используется для поиска элемента рядом с искомым, затем линейный поиск используется для поиска точного элемента.
При использовании нотации большого O производительность алгоритма интерполяции для набора данных размера n равна O (n); однако при условии равномерного распределения данных в линейном масштабе, используемом для интерполяции, производительность может быть показана как O (log log n). Тем не менее, поиск с динамической интерполяцией возможен за время o (log log n), используя новую структуру данных.
Практическая эффективность поиска с интерполяцией зависит от того, перевешивается ли уменьшенное количество зондов более сложными вычислениями, необходимыми для каждого зонд. Это может быть полезно для поиска записи в большом отсортированном файле на диске, где каждый зонд включает поиск по диску и выполняется намного медленнее, чем арифметика интерполяции.
Индексные структуры, такие как B-деревья, также сокращают количество обращений к диску и чаще используются для индексации данных на диске частично, поскольку они могут индексировать многие типы данных и могут быть обновлено онлайн. Тем не менее, поиск с интерполяцией может быть полезен, когда кто-то вынужден искать определенные отсортированные, но неиндексированные наборы данных на диске.
Когда ключи сортировки для набора данных представляют собой равномерно распределенные числа, линейная интерполяция проста в реализации и найдет индекс, очень близкий к искомому значению.
С другой стороны, для телефонной книги, отсортированной по имени, прямой подход к поиску с интерполяцией не применим. Тем не менее, те же самые высокоуровневые принципы все еще могут применяться: можно оценить положение имени в телефонной книге, используя относительную частоту букв в именах, и использовать это в качестве места проверки.
Некоторые реализации поиска с интерполяцией могут не работать должным образом, если существует серия с одинаковыми ключевыми значениями. Самая простая реализация поиска с интерполяцией не обязательно будет выбирать первый (или последний) элемент такого прогона.
Преобразование имен в телефонной книге в какой-то номер явно не даст номеров, имеющих равномерное распределение (за исключением огромных усилий, таких как сортировка имен и вызов их имя # 1, имя # 2 и т. д.), и, кроме того, хорошо известно, что некоторые имена гораздо более распространены, чем другие (Смит, Джонс,). Точно так же со словарями, где есть намного больше слов, начинающихся с одних букв, чем других. Некоторые издатели стараются подготовить аннотации на полях или даже вырезать края страниц, чтобы показать маркеры для каждой буквы, чтобы можно было сразу выполнить сегментированную интерполяцию.
Следующий пример кода C ++ представляет собой простую реализацию. На каждом этапе он вычисляет положение зонда, а затем, как и в случае двоичного поиска, перемещает либо верхнюю, либо нижнюю границу, чтобы определить меньший интервал, содержащий искомое значение. В отличие от двоичного поиска, который гарантирует уменьшение вдвое размера интервала на каждом этапе, ошибочная интерполяция может снизить эффективность O (n) в 1-м случае.
/ * T должен реализовывать операторы -,! =, ==,>=, <= and < such that>=, <=, !=, == and < define a total order on T and such that (tm - tl) * k / (th - tl) is an int between 0 and k (inclusive) for any tl, tm, th in T with tl <= tm <= th, tl != th. arr must be sorted according to this ordering. \returns An index i such that arr[i] == key or -1 if there is no i that satisfies this. */ templateint interpolation_search (T arr, int size, T key) {int low = 0; int high = size - 1; int mid; while ((arr [high]! = arr [low]) (key>= arr [low]) (key <= arr[high])) { 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; }
Обратите внимание на то, что при проверке списка в середине индекса по причинам администрирования управления циклом этот код устанавливает либо высокий, либо низкий, чтобы быть не средним, а смежным индексом, местоположение которого затем проверяется во время следующей итерации.Поскольку значение соседней записи не будет сильно отличаться, расчет интерполяции не сильно улучшится этой одноступенчатой корректировкой за счет дополнительной ссылки на удаленную память, такую как диск.
Каждая итерация приведенного выше кода требует от пяти до шести сравнений (дополнительное количество связано с повторениями, необходимыми для различения трех состояний <>и = через бинарные сравнения в отсутствие трехстороннего сравнения ) плюс некоторая беспорядочная арифметика, в то время как алгоритм двоичного поиска может быть записан с одним сравнением на итерацию и использует только тривиальную целочисленную арифметику. таким образом будет искать массив из миллиона элементов с не более чем двадцатью сравнениями (включая ving обращается к медленной памяти, где хранятся элементы массива); чтобы превзойти это, поиск с интерполяцией, как написано выше, допускал бы не более трех итераций.
