Фундаментальные алгоритмы и структуры данных в Delphi

Бакнелл Джулиан М.

end;

end;

class procedure TtdSkipList.slGetNodeManagers;

var

i : integer;

begin

{если диспетчеры узлов еще не созданы, создать их}

if (SLNodeManager[0] =nil) then

for i := 0 to pred(tdcMaxSkipLevels) do SLNodeManager[i] := TtdNodeManager.Create(NodeSize[i]);

end;

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

Остальные методы класса списка с пропусками еще проще - все они содержат всего несколько строк кода.

Листинг 6.22. Остальные методы класса списка с пропусками

procedure TtdSkipList.Delete

begin

{начальный

и конечный узлы удалять нельзя}

if (FCursor = FHead) or (FCursor = FTail) then

slError(tdeListCannotDelete, 'Delete');

{удалить узел в позиции курсора}

Remove(FCursor^.sknData);

end;

function TtdSkipList.Examine : pointer;

begin

Result := FCursor^.sknData;

end;

function TtdSkipList.IsAfterLast : boolean;

begin

Result := FCursor = FTail;

end;

function TtdSkipList.IsBeforeFirst : boolean;

begin

Result := FCursor = FHead;

end;

function TtdSkipList.IsEmpty : boolean;

begin

Result := Count = 0;

end;

procedure TtdSkipList.MoveAf terLast;

begin

FCursor := FTail;

end;

procedure TtdSkipList.MoveBeforeFirst;

begin

FCursor := FHead;

end;

procedure TtdSkipList.MoveNext;

begin

if (FCursor <> FTail) then

FCursor := FCursor^.sknNext[0];

end;

procedure TtdSkipList.Move Prior;

begin

if (FCursor <> FHead) then

FCursor := FCursor^.sknPrev;

end;

С использованием набора диспетчеров узлов для списка с пропусками связана одна проблема, о которой мы еще не говорили. Она не так очевидна для связных списков. А заключается она в пробуксовке. Проблема пробуксовки становится все более заметной при увеличении количества узлов до миллионов. Дело в том, что в списке с пропусками соседние узлы, скорее всего, будут находиться в разных страницах памяти. Поэтому при последовательном прохождении по списку от начала до конца на пути будут попадаться узлы разного размера, находящиеся в разных страницах памяти. Это приводит к подкачке страниц. К сожалению, мы никак не можем устранить свопинг (при использовании списков с несколькими миллионами узлов данные узлов в любом случае могут находиться в разных страницах). Проблему можно немного смягчить за счет использования стандартного диспетчера кучи Delphi. Тем не менее, даже в этом случае не исключается возможность возникновения пробуксовки.

Резюме

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

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

И, наконец, был рассмотрен список с пропусками - структура данных, используемая для хранения данных в отсортированном порядке. Было показано, каким образом случайные числа позволяют повысить характеристики быстродействия списков с пропусками.

Глава 7. Хеширование и хеш-таблицы

В главе 4 были рассмотрены алгоритмы поиска элемента в

массиве (например, TList) или в связном списке. Наиболее быстрым из рассмотренных методов был бинарный поиск, для выполнения которого требовался отсортированный контейнер. Бинарный поиск представляет собой алгоритм класса O(log(n)). Так, чтобы установить наличие или отсутствие заданного элемента в списке из 1000 элементов, требуется выполнить приблизительно 10 сравнений (поскольку 2(^10^) = 1024). Возможен ли еще более эффективный подход?

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

Однако если бы элемент можно было связать с уникальным индексом, его можно было бы найти посредством однонаправленного действия: просто извлекая элемент, расположенный в позиции MyList[ItemIndex]. Это пример поиска с использованием индексирования по ключу, когда ключ элемента преобразуется в индекс, и элемент извлекается из массива с помощью этого индекса. Такой подход кардинально отличается от бинарного поиска, при котором, по существу, ключ элемента используется для перемещения по структуре с применением метода, в основе которого лежит сравнение.

Преобразование ключа элемента в значение индекса называется хешированием (hashing) и оно выполняется с помощью функции хеширования (hash function). Массив, используемый для хранения элементов, с которым используется значение индекса, называют хеш-таблицей (hash table).

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

Хеш-таблица - прекрасный пример достижения компромисса между быстродействием и занимаемым объемом памяти. Если бы ключи элементов были уникальными значениями типа word, нужно было бы всего лишь создать 65536 элементов, и при этом можно было бы гарантировать нахождение элемента с конкретным ключом в результате выполнения одной операции. Однако если нужно хранить, скажем, не более 100 элементов, подобный подход оказывается чрезмерно расточительным. Да, возможно, этот метод работает достаточно быстро, но 99.85% области памяти массива пребывает пустой. Впадая в другую крайность, можно было бы выделить только необходимый объем памяти, выделяя массив требуемого размера, храня элементы в отсортированном порядке и используя бинарный поиск. Согласен, этот метод работает медленнее, но зато отсутствует бесполезно расходуемая память. Хеширование и хеш-таблицы позволяют выбрать золотую середину между этими двумя диаметрально противоположными подходами. Хеш-таблицы будут занимать больше места, причем некоторые элементы окажутся пустыми, тем не менее, использование функции хеширования позволяет найти элемент в результате очень небольшого числа обращений - обычно одного при тщательном выполнении хеширования.

Время от времени, с хеш-таблицами придется выполнять следующие операции:

* вставлять элементы в хеш-таблицу;

* выяснять, содержит ли хеш-таблица определенный элемент (хеш-таблицы обеспечивают очень быстрое выполнение поиска, чему собственно и посвящен этот раздел);

* удалять элементы из хеш-таблицы.

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