Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
===========272
Похожая проблема возникает, если значения элементов распределены между min и max очень неравномерно. Предположим, что мы хотим найти значение 100 в списке 0, 1, 2, 199, 200. При первом вычислении значения переменной middle, мы получим в программе middle = 1 + (100 – 0) * (5 – 1) / (200 – 0) = 3. Затем программа сравнивает значение элемента List(3) с искомым значением 100. Так как List(3) = 2, что меньше 100, она задает min = middle + 1, то есть min = 4.
При следующем вычисления значения переменной middle, программа находит middle = 4 + (100 – 199) * (5 – 4) / (200 – 199) = -98. Значение –98 не попадает в диапазон min <= target index <= max и также далеко выходит за границы массива.
Если рассмотреть процесс вычисления переменной middle, то можно увидеть, что существуют два варианта, при которых новое значение может оказаться меньше, чем min или больше, чем max. Вначале предположим, что middle меньше, чем min.
min + (target - List(min)) * ((max - min) / (List(max) - List(min))) < min
После вычитания min из обеих частей уравнения, получим:
(target - List(min)) * ((max - min) / (List(max) - List(min))) < 0
Так как max >= 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
' Избегаем деления на ноль.
If List(min) = List(max) Then
' Это искомый элемент (если он есть в списке).
If List(min) = target Then
InterpSearch = min
Else
InterpSearch = 0
End If
Exit Function
End If
' Найти точку разбиения списка.
middle = min + (target - List(min)) * _
((max - min) / (List(max) - List(min)))
' Проверить, не вышли ли мы за границы.
If middle < min Or middle > 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 главе обсуждаются методы, позволяющие выполнять вставку и удаление элементов еще быстрее. Для достижения такой высокой скорости, в этих методах используется дополнительное пространство для хранения промежуточных данных. Хеш‑таблицы не хранят информацию о порядке расположения данных. В хеш‑таблицу можно вставлять, удалять, и находить элементы, но сложно вывести элементы из таблицы по порядку.
Если список будет неизменным, то применение упорядоченного списка и использование метода интерполяционного поиска даст прекрасные результаты. Если требуется часто вставлять и удалять элементы из списка, то стоит рассмотреть возможность применения хеш‑таблицы. Если при этом также нужно выводить элементы по порядку или перемещаться по списку в прямом или обратном направлении, то оптимальную скорость и гибкость может обеспечить применение сбалансированных деревьев. Решив, какие типа операций вам понадобятся, вы можете выбрать алгоритм, который вам лучше всего подходит.
=============279
Глава 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, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48
