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

Используя методы из предыдущих разделов можно выполнить следящий интерполяционный поиск (interpolative hunt and search). Вначале, как и раньше, сравним искомое значение из предыдущего поиска с новым. Если новое искомое значение меньше, начнем слежение влево, если больше — вправо.

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

Аналогично выполняется слежение вправо. Просто приравниваем max = Numitems и устанавливаем min равным индексу, полученному во время предыдущего поиска. Затем продолжаем обычный интерполяционный поиск.

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

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

@Рис. 10.5. Интерполяционный поиск значения 17 из значения 44

=============277

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

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

Резюме

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

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

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

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

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

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

===========278

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

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

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

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

=============279