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

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

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

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

=======297

@Таблица 11.1. Длина успешной и безуспешной тестовых последовательностей

Первичная кластеризация

Линейная проверка имеет одно неприятное свойство, которое называется первичной кластеризацией (primary clustering). После добавления большого числа элементов в таблицу, возникает конфликт между новыми элементами и уже имеющимися кластерами, при этом для вставки нового элемента нужно обойти кластер, чтобы найти пустую ячейку.

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

При вставке второго случайно выбранного элемента, он может отобразиться на ту же позицию с вероятностью 1/N. Из‑за конфликта в этом случае он помещается в позицию P + 1. Также существует вероятность 1/N, что элемент и должен располагаться в позиции P + 1, и вероятность 1/N, что он должен находиться в позиции P - 1. Во всех этих трех случаях новый элемент располагается рядом с предыдущим. Таким образом, в целом существует вероятность 3/N того, что 2 элемента окажутся расположенными вблизи друг от друга, образуя небольшой кластер.

По мере роста кластера вероятность того, что следующие элементы будут располагаться вблизи кластера, возрастает. Если в кластере находится два элемента, то вероятность того, что очередной элемент присоединится к кластеру, равна 4/N, если в кластере четыре элемента, то эта вероятность равна 6/N, и так далее.

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

======298

В идеальном случае хеш‑таблица должна быть наполовину пуста, и элементы в ней должны чередоваться с пустыми ячейками. Тогда с вероятностью 50 процентов алгоритм сразу же найдет пустую ячейку для нового добавляемого элемента. Также существует 50‑процентная вероятность того, что он найдет пустую ячейку после проверки всего лишь двух позиций в таблице. Средняя длина тестовой последовательности равна 0,5 * 1 + 0,5 * 2 = 1,5.

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

На практике, степень кластеризации будет находиться между этими двумя крайними случаями. Вы можете использовать программу Linear для исследования эффекта кластеризации. Запустите программу и создайте хеш‑таблицу со 100 ячейками, а затем добавьте 50 случайных элементов со значениями до 999. Вы обнаружите, что образовалось несколько кластеров. В одном из тестов 38 из 50 элементов стали частью кластеров. Если добавить еще 25 элементов к таблице, то большинство элементов будут входить в кластеры. В другом тесте 70 из 75 элементов были сгруппированы в кластеры.

Упорядоченная линейная проверка

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

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

Public Function LocateItem(Value As Long, pos As Integer, _

    probes As Integer) As Integer

Dim new_value As Long

    probes = 1

    pos = (Value Mod m_NumEntries)

    Do

        new_value = m_HashTable(pos)

       

        ' Элемента в таблице нет.

        If new_value = UNUSED Or probes > NumEntries Then

           LocateItem = HASH_NOT_FOUND

           pos = -1

           Exit Function

        End If

       

        ' Элемент найден или его нет в таблице.

        If new_value >= Value Then Exit Do

       

        pos = (pos + 1) Mod NumEntries

        probes = probes + 1

    Loop

    If Value = new_value Then

        LocateItem = HASH_FOUND

    Else

        LocateItem = HASH_NOT_FOUND

    End If

End Function

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

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

========299-300

Public Function InsertItem(ByVal Value As Long, pos As Integer,_     probes As Integer) As Integer

Dim new_value As Long

Dim status As Integer

    ' Проверить, заполнена ли таблица.

    If m_NumUnused < 1 Then

        ' Поиск элемента.

        status = LocateItem(Value, pos, probes)

        If status = HASH_FOUND Then

           InsertItem = HASH_FOUND

        Else

           InsertItem = HASH_TABLE_FULL

           pos = -1

        End If

        Exit Function

    End If

    probes = 1

    pos = (Value Mod m_NumEntries)

    Do

        new_value = m_HashTable(pos)

        ' Если значение найдено, поиск завершен.

        If new_value = Value Then

           InsertItem = HASH_FOUND

           Exit Function

        End If

        ' Если ячейка свободна, элемент должен находиться в ней.

        If new_value = UNUSED Then

           m_HashTable(pos) = Value

           HashForm.TableControl(pos).Caption = Format$(Value)

           InsertItem = HASH_INSERTED

           m_NumUnused = m_NumUnused - 1

           Exit Function

        End If

       

        ' Если значение в ячейке таблицы больше значения

        ' элемента, поменять их местами и продолжить.

        If new_value > Value Then

           m_HashTable(pos) = Value

           Value = new_value

        End If

       

        pos = (pos + 1) Mod NumEntries

        probes = probes + 1

    Loop

End Function

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

В табл. 11.2 приведена средняя длина успешной и безуспешной тестовых последовательностей при использовании линейной и упорядоченной линейной проверок. Средняя длина успешной проверки для обоих методов почти одинакова, но в случае неуспеха упорядоченная линейная проверка выполняется намного быстрее. Разница в особенности заметна, если хеш‑таблица заполнена более, чем на 70 процентов.

Страницы: 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, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82