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

           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

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

Хеширование (hashing) использует аналогичный подход, отображая элементы в хеш‑таблице (hash table). Алгоритм хеширования использует некоторую функцию, которая определяет вероятное положение элемента в таблице на основе значения искомого элемента.

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

К сожалению, в реальных приложениях значения ключа не всегда находятся в небольшом диапазоне. Обычно диапазон возможных значений ключа достаточно велик. База данных сотрудников может использовать в качестве ключа идентификационный номер социального страхования. Теоретически можно было бы создать массив, каждая ячейка которого соответствовала одному из возможных девятизначных чисел; но на практике для этого не хватит памяти или дискового пространства. Если для хранения одной записи требуется 1 килобайт памяти, то такой массив занял бы 1 терабайт (миллион мегабайт) памяти. Даже если можно было бы выделить такой объем памяти, такая схема была бы очень неэкономной. Если штат вашей компании меньше 10 миллионов сотрудников, то более 99 процентов массива будут пусты.

=======281

Чтобы справиться с этой проблемой, схемы хеширования отображают потенциально большое число возможных ключей на достаточно компактную хеш‑таблицу. Если в вашей компании работает 700 сотрудников, вы можете создать хеш‑таблицу с 1000 ячеек. Схема хеширования устанавливает соответствие между 700 записями о сотрудниках и 1000 позициями в таблице. Например, можно располагать записи в таблице в соответствии с тремя первыми цифрами идентификационного номера в системе социального страхования. При этом запись о сотруднике с номером социального страхования 123‑45‑6789 будет находиться в 123 ячейке таблицы.

Очевидно, что поскольку существует больше возможных значений ключа, чем ячеек в таблице, то некоторые значения ключей могут соответствовать одним и тем же ячейкам таблицы. Например, оба значения 123‑45‑6789 и 123­99‑9999 отображаются на одну и ту же ячейку таблицы 123. Если существует миллиард возможных номеров системы социального страхования, и таблица имеет 1000 ячеек, то в среднем каждая ячейка будет соответствовать миллиону записей.

Чтобы избежать этой потенциальной проблемы, схема хеширования должна включать в себя алгоритм разрешения конфликтов (collision resolution policy), который определяет последовательность действий в случае, если ключ соответствует позиции в таблице, которая уже занята другой записью. В следующих разделах описываются несколько различных методов разрешения конфликтов.

Все обсуждаемые здесь методы используют для разрешения конфликтов примерно одинаковый подход. Они вначале устанавливают соответствие между ключом записи и положением в хеш‑таблице. Если эта ячейка уже занята, они отображают ключ на какую‑либо другую ячейку таблицы. Если она также уже занята, то процесс повторяется снова о тех пор, пока в конце концов алгоритм не найдет пустую ячейку в таблице. Последовательность проверяемых при поиске или вставке элемента в хеш‑таблицу позиций называется [RV16]  тестовой последовательностью (probe sequence).

В итоге, для реализации хеширования необходимы три вещи:

·         Структура данных (хеш‑таблица) для хранения данных;

·         Функция хеширования, устанавливающая соответствие между значением ключа и положением в таблице;

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

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

Связывание

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

На рис. 11.1 показан пример связывания хеш‑таблицы, которая содержит 10 ячеек. Функция хеширования отображает ключ K на ячейку K Mod 10 в массиве. Каждая ячейка массива содержит указатель на первый элемент связного списка. При вставке элемента в таблицу он помещается в соответствующий список.

======282

@Рис. 11.1. Связывание

Чтобы создать хеш‑таблицу в Visual Basic, используйте оператор ReDim для размещения сигнальных меток начала списков. Если вы хотите создать в хеш‑таблице NumLists связных списков, задайте размер массива ListTops при помощи оператора ReDim ListTops(0 To NumLists - 1). Первоначально все списки пусты, поэтому указатель NextCell каждой метки должен иметь значение Nothing. Если вы используете для изменения массива меток оператор ReDim, то Visual Basic автоматически инициализирует указатели NextCell значением Nothing.

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

Global Const HASH_FOUND = 0

Global Const HASH_NOT_FOUND = 1

Global Const HASH_INSERTED = 2

Private Function LocateItemUnsorted(Value As Long) As Integer

Dim cell As ChainCell

    ' Получить вершину связного списка.

    Set cell = m_ListTops(Value Mod NumLists).NextCell

    Do While Not (cell Is Nothing)

        If cell.Value = Value Then Exit Do

        Set cell = cell.NextCell

    Loop

    If cell Is Nothing Then

        LocateItemUnsorted = HASH_NOT_FOUND

    Else

        LocateItemUnsorted = HASH_FOUND

    End If

End Function

Функции для вставки и удаления элементов из связных списков аналогичны функциям, описанным во 2 главе.

========283

Преимущества и недостатки связывания

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

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

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

Можно немного ускорить поиск, если использовать упорядоченные списки. Тогда можно использовать для поиска элементов в упорядоченных связных списках методы, описанные в 10 главе. Это позволяет прекратить поиск, если во время его выполнения встретится элемент со значением, большим искомого. В среднем потребуется проверить только половину связного списка, чтобы найти элемент или определить, что его нет в списке.

Private Function LocateItemSorted(Value As Long) As Integer

Dim cell As ChainCell

    ' Получить вершину связного списка.

    Set cell = m_ListTops(Value Mod NumLists).NextCell

    Do While Not (cell Is Nothing)

        If cell.Value >= Value Then Exit Do

        Set cell = cell.NextCell

    Loop

    If cell Is Nothing Then

        LocateItemSorted = HASH_NOT_FOUND

    ElseIf cell.Value = Value Then

        LocateItemSorted = HASH_FOUND

    Else

        LocateItemSorted = HASH_NOT_FOUND

    End If

End Function

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

========284

В программе Chain реализована хеш‑таблица со связыванием. Введите число списков в поле области Table Creation (Создание таблицы) на форме и установите флажок Sort Lists (Упорядоченные списки), если вы хотите, чтобы программа использовала упорядоченные списки. Затем нажмите на кнопку Create Table (Создать таблицу). Затем вы можете ввести новые значения и снова нажать на кнопку Create Table, чтобы создать новую хеш‑таблицу.

Так как интересно изучать хеш‑таблицы, содержащие большое число значений, то программа Chain позволяет заполнять таблицу случайными элементами. Введите число элементов, которые вы хотите создать и максимальное значение элементов в области Random Items (Случайные элементы), затем нажмите на кнопку Create Items (Создать элементы), и программа добавит в хеш‑таблицу случайно созданные элементы.

Страницы: 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