Интерполяционный поиск

Интерполяционный поиск
	Визуализация алгоритма поиска интерполяции, в котором 24 является целевым значением.
Сорт	Алгоритм поиска
Структура данных	Множество
Худшая производительность	На )
Лучшая производительность	О (1)
Средняя производительность	O (журнал(журнал( n )))
Наихудшая пространственная сложность	О (1)
Оптимальный	Да

Интерполяционный поиск — алгоритм поиска по ключа в массиве, упорядоченном числовым значениям, присвоенным ключам ( значениям ключей ). Впервые он был описан У.В. Петерсоном в 1957 году. ^[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 - 1

How to verify that the algorithm is correct?
Proof:
(finiteness: after one loop, the width of [low, high] decreases strictly )

Fist, high <--- high - 1
scenario 1. when low = high
scenario 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] <= key

How to verify that the algorithm is correct?
Proof:
finiteness: after one loop, the width of [low, high] decreases strictly 

Fist, high <---- high - 1
scenario 1. when low = high
scenario 2. when low < high, key < arr[low] or arr[high] <= key
scenario 3. when low < high, arr[low] <= key < arr[high]

Now let's analyze scenario 3:
Once entering the "while" loop,  low <= middle < high

when 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], impossible

conclusion: 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 .

Внешние ссылки

[1] В. В. Петерсон (1957). «Адресация запоминающих устройств с произвольным доступом». IBM J. Res. Дев . 1 (2): 130–146. дои : 10.1147/рд.12.0130 .

[2] Саймон Юань. «Понимание сложности интерполяционного поиска, семинар по расширенным алгоритмам и структурам данных» (PDF) .

[3] Вайс, Марк Аллен (2006). Структуры данных и решение проблем с использованием Java , Пирсон Аддисон Уэсли

[4] Арменакис, AC, Гари, LE, Гупта, RD, Адаптация метода поиска корня для поиска упорядоченных дисковых файлов, BIT Numerical Mathematics, Том 25, номер 4 / Декабрь 1985.

[5] Седжвик, Роберт (1990), Алгоритмы на C , Аддисон-Уэсли

[6] Андерссон, Арне и Кристер Маттссон. «Динамический интерполяционный поиск за o (log log n ) время». В книге «Автоматы, языки и программирование» под редакцией Анджея Лингаса, Рольфа Карлссона и Сванте Карлссона, 700:15–27. Конспекты лекций по информатике. Шпрингер Берлин/Гейдельберг, 1993. дои : 10.1007/3-540-56939-1_58

[7] Мохаммед, Аднан Сахер; Амрахов, Шахин Эмра; Челеби, Фатих В. (1 октября 2021 г.). «Интерполированный двоичный поиск: эффективный алгоритм гибридного поиска в упорядоченных наборах данных» . Инженерные науки и технологии . 24 (5): 1072–1079. дои : 10.1016/j.jestch.2021.02.009 . ISSN 2215-0986 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]