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

Чтобы выполнить интерполяционный следящий поиск (interpolar hunt search), вы можете воспользоваться методами, описанными в предыдущем разделе. Начните со сравнения искомого значения из предыдущего поиска с новым искомым значением. Если новое искомое значение меньше, начните отслеживание слева, если больше - справа.

Для слежения слева используйте интерполяцию, чтобы предположить, где может находиться значение в диапазоне между предыдущим значением и значением элемента list^[ 1 ]. Но это обычный интерполяционный поиск, в котором значение min = 1 и max равно индексу из предыдущего поиска. После первого шага фаза отслеживания заканчивается, и можно продолжать обычный интерполяционный поиск.

Слежение справа выполняется аналогично. Установите max = Numltems и min равным индексу из предыдущего поиска. Затем продолжайте обычный интерполяционный поиск.

На рисунке 5 изображен процесс интерполяционного поиска элемента со

значением 17, начинающийся с предыдущего искомого значения 44.

Рисунок 5 – Интерполяционный поиск значения 17из значения 44

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

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

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

6. Резюме

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

Если требуется время от времени проводить поиск в списке, содержащем десятки элементов, также используйте полный перебор. Данный алгоритм проще отлаживать и поддерживать, чем более сложные алгоритмы поиска, и его применение дает достаточно хорошие результаты.

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

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

В таблице 1 приведены преимущества и недостатки каждого из методов поиска.

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

Таким большим списком сложно управлять, если необходимо вносить в него какие-либо изменения. Добавление или удаление элемента из сортированного списка занимает O(N) шагов. Если элемент находится в начале списка, это отнимет достаточно много времени, особенно если список хранится на медленном устройстве.

Таблица 1 – Преимущества и недостатки различных методов поиска

Метод	Преимущества	Недостатки
Полный перебор	Прост Высокая скорость для небольших списков	Низкая скорость для больших списков
Двоичный поиск	Высокая скорость для больших списков Не зависит от распределения данных Просто обрабатывает строковые данные	Более сложен, чем полный перебор
Интерполяционный поиск	Очень высокая скорость для больших списков	Очень сложен Данные должны быть распределены равномерно Сложно работать со строковыми данными

Если нужно вставлять и удалять элементы из большого списка, следует рас- рассмотреть использование других структур данных. В главе 7 описаны структуры данных, которые позволяют добавлять и удалять элементы всего за O(logN) шагов.

В главе 11 обсуждаются методы, позволяющие выполнять вставку и удаление элементов еще быстрее. Такая скорость достигается использованием дополнительных объемов памяти. Кроме того, хеш-таблицы не дают информации о порядке расположения данных. Можно добавлять, находить и удалять элементы из хеш-таблицы, но нельзя легко вывести элементы в сортированном порядке.

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

ЗАКЛЮЧЕНИЕ

Список использованной литературы

ПРИЛОЖЕНИЕ