VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

Set LListSearch = cell ' Элемент найден.

End If

End If

End Function

Программа Search использует этот алгоритм для поиска элементов в связном

списке. Этот алгоритм выполняется немного медленнее, чем алгоритм полного

перебора в массиве из-за дополнительных накладных расходов, которые связаны

с управлением указателями на объекты. Заметьте, что программа Search строит

связные списки, только если список содержит не более 10.000 элементов.

Чтобы алгоритм выполнялся немного быстрее, в него можно внести еще одно

изменение. Если хранить указатель на конец списка, то можно добавить в

конец списка ячейку, которая будет содержать искомый элемент. Этот элемент

называется сигнальной меткой (sentinel), и служит для тех же целей, что и

сигнальные метки, описанные во 2 главе. Это позволяет обрабатывать особый

случай конца списка так же, как и все остальные.

В этом случае, добавление метки в конец списка гарантирует, что в конце

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

конец списка, и нет необходимости проверять условие Not (cell Is Nothing) в

каждом цикле While.

Public Function SentinelSearch(target As Long) As SearchCell

Dim cell As SearchCell

Dim sentinel As New SearchCell

NumSearches = 0

' Установить сигнальную метку.

sentinel.Value = target

Set ListBottom.NextCell = sentinel

' Найти искомый элемент.

Set cell = ListTop.NextCell

Do While cell.Value < target

NumSearches = NumSearches + 1

Set cell = cell.NextCell

Loop

' Определить найден ли искомый элемент.

If Not ((cell Is sentinel) Or _

(cell.Value <> target)) _

Then

Set SentinelSearch = cell ' Элемент найден.

End If

' Удалить сигнальную метку.

Set ListBottom.NextCell = Nothing

End Function

Хотя может показаться, что это изменение незначительно, проверка Not (cell

Is Nothing) выполняется в цикле, который вызывается очень часто. Для

больших списков этот цикл вызывается множество раз, и выигрыш времени

суммируется. В Visual Basic, этот версия алгоритма поиска в связных списках

выполняется на 20 процентов быстрее, чем предыдущая версия. В программе

Search приведены обе версии этого алгоритма, и вы можете сравнить их.

Некоторые алгоритмы используют потоки для ускорения поиска в связных

списках. Например, при помощи указателей в ячейках списка можно

организовать список в виде двоичного дерева. Поиск элемента с

использованием этого дерева займет время порядка O(log(N)), если дерево

сбалансировано. Такие структуры данных уже не являются просто списками,

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

обратитесь к 6 и 7 главам

Двоичный поиск

Как уже упоминалось в предыдущих разделах, поиск полным перебором

выполняется очень быстро для небольших списков, но для больших списков

намного быстрее выполняется двоичный поиск. Алгоритм двоичного поиска

(binary search) сравнивает элемент в середине списка с искомым. Если

искомый элемент меньше, чем найденный, то алгоритм продолжает поиск в

первой половине списка, если больше — в правой половине. На рис. 10.2 этот

процесс изображен графически.

Хотя по своей природе этот алгоритм является рекурсивным, его достаточно

просто записать и без применения рекурсии. Так как этот алгоритм прост для

понимания в любом варианте (с рекурсией или без), то мы приводим здесь его

нерекурсивную версию, которая содержит меньше вызовов функций.

Основная заключенная в этом алгоритме идея проста, но детали ее реализации

достаточно сложны. Программе приходится аккуратно отслеживать часть

массива, которая может содержать искомый элемент, иначе она может его

пропустить.

Алгоритм использует две переменные, min и max, в которых находятся

минимальный и максимальный индексы ячеек массива, которые могут содержать

искомый элемент. Во время выполнения алгоритма, индекс искомой ячейки

всегда будет лежать между min и max. Другими словами, min = min, то разность (max – min) должна быть больше нуля. Так

как List(max) >= List(min), то разность (List(max) – List(min)) также

должна быть больше нуля. Тогда все значение может быть меньше нуля, только

если (target – List(min)) меньше нуля. Это означает, что искомое значение

меньше, чем значение элемента List(min). В этом случае, искомый элемент не

может находиться в списке, так как все элементы списка со значением

меньшим, чем List(min) уже были исключены.

Теперь предположим, что middle больше, чем max.

min + (target - List(min)) * ((max - min) / (List(max) - List(min))) > max

После вычитания min из обеих частей уравнения, получим:

(target - List(min)) * ((max - min) / (List(max) - List(min))) > 0

Умножение обеих частей на (List(max) – List(min)) / (max – min) приводит

соотношение к виду:

target – List(min) > List(max) – List(min)

И, наконец, прибавив к обеим частям List(min), получим:

target > List(max)

Это означает, что искомое значение больше, чем значение элемента List(max).

В этом случае, искомое значение не может находиться в списке, так как все

элементы списка со значениями большими, чем List(max) уже были исключены.

==========273

Учитывая все эти результаты, получаем, что новое значение переменной middle

может выйти из диапазона между min и max только в том случае, если искомое

значение выходит за пределы диапазона от List(min) до List(max). Алгоритм

может использовать этот факт при вычислении нового значения переменной

middle. Он вначале проверяет, находится ли новое значение между min и max.

Если нет, то искомого элемента нет в списке и работа алгоритма завершена.

Следующий код демонстрирует реализацию интерполяционного поиска в программе

Search:

Public Function InterpSearch(target As Long) As Long

Dim min As Long

Dim max As Long

Dim middle As Long

min = 1

max = NumItems

Do While min max Then

' Искомого элемента нет в списке.

InterpSearch = 0

Exit Function

End If

NumSearches = NumSearches + 1

If target = List(middle) Then ' Искомый элемент найден.

InterpSearch = middle

Exit Function

ElseIf target < List(middle) Then ' Поиск в левой части.

max = middle - 1

Else ' Поиск в правой части.

min = middle + 1

End If

Loop

' Если мы дошли до этой точки, то элемента нет в списке.

InterpSearch = 0

End Function

Двоичный поиск выполняется очень быстро, а интерполяционный еще быстрее. В

одном из тестов, двоичный поиск потребовал в 7 раз больше времени для

поиска значений в списке из 100.000 элементов. Эта разница могла бы быть

еще больше, если бы данные находились на диске или каком-либо другом

медленном устройстве. Хотя при интерполяционном поиске на вычисления уходит

больше времени, чем в случае двоичного поиска, за счет меньшего числа

обращений к диску мы сэкономили бы гораздо больше времени.

Строковые данные

Если данные в списке представляют собой строки, можно применить два

различных подхода. Более простой состоит в применении двоичного поиска. При

двоичном поиске значения элементов сравниваются непосредственно, поэтому

этот метод может легко работать со строковыми данными.

С другой стороны, интерполяционный поиск использует численные значения

элементов данных для вычисления возможного положения искомого элемента в

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

непосредственно использовать значения данных для вычисления предполагаемого

положения искомого элемента.

Если строки достаточно короткие, то можно закодировать их при помощи целых

чисел или чисел формата long или double, используя методы, которые были

описаны в 9 главе. После этого можно использовать для нахождения элементов

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

Если строки слишком длинные, и их нельзя закодировать даже числами в

формате double, то все еще можно использовать для интерполяции значения

строк. Вначале найдем первый отличающийся символ для строк List(min) и

List(max). Затем закодируем его и следующие два символа в каждой строке при

помощи методов из 9 главы. Затем можно использовать эти значения для

выполнения интерполяционного поиска.

Например, предположим, что мы ищем строку TARGET в списке TABULATE,

TANTRUM, TARGET, TATTERED, TAXATION. Если min = 1 и max = 5, то проверяются

значения TABULATE и THEATER. Эти строки отличаются во втором символе,

поэтому нужно рассматривать три символа, начинающиеся со второго. Это будут

символы ABU для List(1), AXA для List(5) и ARG для искомой строки.

Эти значения кодируются числами 804, 1378 и 1222 соответственно. Подставляя

эти значения в формулу для переменной middle, получим:

middle = min + (target - List(min)) * ((max - min) / (List(max) -

List(min)))

= 1 + (1222 – 804) * ((5 – 1) / (1378 – 804))

= 2,91

=========275

Это примерно равно 3, поэтому следующее значение переменной middle равно 3.

Это положение строки TARGET в списке, поэтому поиск при этом заканчивается.

Следящий поиск

Чтобы начать двоичный следящий поиск (binary hunt and search), сравним

искомое значение из предыдущего поиска с новым искомым значением. Если

новое значение меньше, начнем слежение влево, если больше — вправо.

Для выполнения слежения влево, установим значения переменных min и max

равными индексу, полученному во время предыдущего поиска. Затем уменьшим

значение min на единицу и сравним искомое значение со значением элемента

List(min). Если искомое значение меньше, чем значение List(min), установим

max = min и min = min –2, и сделаем еще одну проверку. Если искомое

значение все еще меньше, установим max = min и min = min –4, если это не

поможет, установим max = min и min = min –8 и так далее. Продолжим

устанавливать значение переменной max равным значению переменной min и

вычитать очередные степени двойки из значения переменной min до тех пор,

пока не найдется значение min, для которого значение элемента List(min)

будем меньше искомого значения.

Необходимо следить за тем, чтобы не выйти за границы массива, если min

меньше, чем нижняя граница массива. Если в какой-то момент это окажется

так, то min нужно присвоить значение нижней границы массива. Если при этом

значение элемента List(min) все еще больше искомого, значит искомого

элемента нет в списке. На рис. 10.4 показан следящий поиск элемента со

значением 17 влево от предыдущего искомого элемента со значением 44.

Слежение вправо выполняется аналогично. Вначале значения переменных min и

max устанавливаются равными значению индекса, полученного во время

предыдущего поиска. Затем последовательно устанавливается min = max и max =

max + 1, min = max и max = max + 2, min = max и max = max + 4, и так далее

до тех пор, пока в какой-то точке значение элемента массива List(max) не

станет больше искомого. И снова необходимо следить за тем, чтобы не выйти

за границу массива.

После завершения фазы слежения известно, что индекс искомого элемента

находится между min и max. После этого можно использовать обычный двоичный

поиск для нахождения точного положения искомого элемента.

@Рис. 10.4. Следящий поиск значения 17 из значения 44

===============276

Если новый искомый элемент находится недалеко от предыдущего, то алгоритм

следящего поиска очень быстро найдет значения max и min. Если новый и

старый искомые элементы отстоят друг от друга на P позиций, то потребуется

порядка log(P) шагов для следящего поиска новых значений переменных min и

max.

Предположим, что мы начали обычный двоичный поиск без фазы слежения. Тогда

потребуется порядка log(NumItems) – log(P) шагов для того, чтобы значения

min и max были на расстоянии не больше, чем P позиций друг от друга. Это

означает, что следящий поиск будет быстрее обычного двоичного поиска, если

log(P) < log(NumItems) – log(P). Прибавив к обеим частям уравнения log(P),

получим 2 * log(P) > log(NumItems). Если возвести обе части уравнения в

степень двойки, получим 22*log(P) < 2log(NumItems) или (2log(P))2 <

NumItems, или после упрощения P2 < NumItems.

Из этого соотношения видно, что следящий поиск будет выполняться быстрее,

если расстояние между последовательными искомыми элементами будет меньше,

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

другом искомые элементы расположены далеко друг от друга, то лучше

использовать обычный двоичный поиск.

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

Используя методы из предыдущих разделов можно выполнить следящий

интерполяционный поиск (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 главе обсуждаются методы, позволяющие выполнять вставку и удаление

элементов еще быстрее. Для достижения такой высокой скорости, в этих

методах используется дополнительное пространство для хранения промежуточных

данных. Хеш-таблицы не хранят информацию о порядке расположения данных. В

хеш-таблицу можно вставлять, удалять, и находить элементы, но сложно

вывести элементы из таблицы по порядку.

Если список будет неизменным, то применение упорядоченного списка и

использование метода интерполяционного поиска даст прекрасные результаты.

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31