Курсовая работа - Сравнение эффективности различных подходов к хранению данных

Подождите немного. Документ загружается.

Министерство транспорта и связи РФ

СибГУТИ

Кафедра ВС

Курсовая работа.

Сравнение эффективности

Различных подходов к хранению данных

(Хеширование, красно-черные деревья, Скип-листы)

Выполнили:

Проверил: Пудов С.Г.

г.Новосибирск 2005

Содержание:

1.Теория----------------------------------------------------------------------------- 3

1.1.Хеш-таблицы------------------------------------------------------------------ 3

1.2.Красно-черные деревья------------------------------------------------------7

1.3.Слоеные списки (скип-листы)----------------------------------------------9

2. Программа на языке С++-----------------------------------------------------11

2.1.Хеш-таблицы------------------------------------------------------------------11

2.2.Красно-черные деревья----------------------------------------------------- 15

2.3.Слоеные списки (скип-листы)-------------------------------------------- 22

3. Сравнительная характеристика--------------------------------------------- 27

1.Теория

1.1.Хеш-таблицы

Открытое Хеширование

Один из наиболее эффективных способов реализации словаря - хеш-

таблица. Среднее время поиска элемента в ней есть O(1), время для

наихудшего случая - O(n). Прекрасное изложение хеширования можно

найти в работах Кормена[1990] и Кнута[1998].

Хеш-таблица - это обычный массив с необычной адресацией,

задаваемой хеш-функцией.

Например, на рис - это массив из 8 элементов. Каждый элемент

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

Хеш-функция в этом примере просто делит ключ на 8 и использует

остаток как индекс в таблице. Это дает нам числа от 0 до 7. Поскольку

для адресации в hashTable нам и нужны числа от 0 до 7, алгоритм

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

Хеширование полезно, когда широкий диапазон возможных значений

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

быстрого, практически произвольного доступа. Хэш-таблицы часто

применяются в базах данных, и, особенно, в языковых процессорах

типа компиляторов и ассемблеров, где они изящно обслуживают

таблицы идентификаторов. В таких приложениях, таблица -

наилучшая структура данных.

Так как всякий доступ к таблице должен быть произведен через хэш-

функцию, функция должна удовлетворять двум требованиям: Она

должна быть быстрой, и она должна порождать хорошие ключи для

распределения элементов по таблице. Последнее требование

минимизирует коллизии (случаи, когда два разных элемента имеют

одинаковое значение хеш-функции) и предотвращает случай, когда

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

часть таблицы.

Чтобы вставить в таблицу новый элемент, мы хешируем ключ,

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

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

11, мы делим 11 на 8 и получаем остаток 3. Таким образом, 11 следует

разместить в списке, на начало которого указывает [3]. Чтобы найти

число, мы его хешируем и проходим по соответствующему списку.

Чтобы удалить число, мы находим его и удаляем элемент списка, его

содержащий. При добавлении элементов в хеш-таблицу выделяются

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

списков, каждый из которых соответствует входу хеш-таблицы. Этот

метод называется связыванием.

Если хеш-функция распределяет совокупность возможных ключей

равномерно по множеству индексов, то хеширование эффективно

разбивает множество ключей. Наихудший случай - когда все ключи

хешируются в один индекс. При этом мы работаем с одним линейным

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

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

функция.

 Деление (размер таблицы hashTableSize - простое число). Этот

метод использован в последнем примере. Хеширующее значение

hashValue, изменяющееся от 0 до (hashTableSize - 1), равно

остатку от деления ключа на размер хеш-таблицы. Для успеха

этого метода очень важен выбор подходящего значения

hashTableSize. Если, например, hashTableSize равняется двум, то

для четных ключей хеш-значения будут четными, для нечетных

- нечетными. Ясно, что это нежелательно - ведь если все ключи

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

Аналогично, если все ключи окажутся четными, то

hashTableSize, равное степени двух, попросту возьмет часть

битов Key в качестве индекса. Чтобы получить более случайное

распределение ключей, в качестве hashTableSize нужно брать

простое число, не слишком близкое к степени двух.

 Мультипликативный метод (размер таблицы hashTableSize есть

степень 2n). Значение key умножается на константу, затем от

результата берется n бит. В качестве такой константы Кнут

рекомендует золотое сечение (sqrt(5) - 1)/2 = 0.6180339887499.

Пусть, например, мы работаем с таблицей из

hashTableSize=32(25) элементов, хэширование производится

байтами(8 бит, unsigned char). Тогда необходимый множитель:

28*sqrt(5) - 1)/2 = 158.

 Далее, умножая 8-битовый ключ на 158, будем получать

некоторое 16-битное число. Для таблицы длиной 25 в качестве

хеширующего значения берем 5 старших битов младшего слова,

содержащего такое произведение.

 Аддитивный метод для строк переменной длины (размер

таблицы равен 256). Для строк переменной длины вполне

разумные результаты дает сложение по модулю 256. В этом

случае результат hashValue заключен между 0 и 255.

 Исключающее ИЛИ для строк переменной длины (размер

таблицы равен 256). Этот метод аналогичен аддитивному, но

успешно различает схожие слова и анаграммы (аддитивный

метод даст одно значение для XY и YX). Метод, как легко

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

последовательно применяется операция "исключающее или". В

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

чтобы еще улучшить результат.

 Исключающее ИЛИ для строк переменной длины (размер

таблицы <= 65536). Если мы хешируем строку дважды, мы

получим хеш-значение для таблицы любой длины до 65536.

Когда строка хешируется во второй раз, к первому символу

прибавляется 1. Получаемые два 8-битовых числа объединяются

в одно 16-битовое.

Размер хеш-таблицы должен быть достаточно большим, чтобы в ней

оставалось разумно большое число пустых мест. Как видно из таблицы

3.1, чем меньше таблица, тем больше среднее время поиска ключа в

ней. Хеш-таблицу можно рассматривать как совокупность связанных

списков. По мере того, как таблица растет, увеличивается количество

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

уменьшается. Пусть количество элементов равно n. Если размер

таблицы равен 1, то таблица вырождается в один список длины n. Если

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

иметь дело с двумя списками по n/100 элементов в каждом. Это сильно

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

таблице, имеется значительная свободы в выборе длины таблицы

Таблица:iЗависимость среднего времени поиска (µs) от hashTableSize.

Сортируются 4096 элементов

Размер Время Размер Время

1 869 128 9

2 432 256 6

4 214 512 4

8 106 1024 4

16 54 2048 3

32 28 4096 3

64 15 8192 3

Закрытая адресация.

Только что рассматривалось хеширование со списками, но есть и

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

превышающей количество данных, длины.

Закрытые хеш-таблицы особенно эффективны, когда максимальные

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

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

эффективность значительно ухудшается (см. Структуры Данных, и

Программируйте Проект на C, Робертом Крус, Брюсом Леунг, и Clovis

Tondo, Prentice Холл, 1991).

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

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

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

легко доступна.

Пусть нам необходимо представлять множества элементов типа T,

причем число элементов заведомо меньше n. Выберем некоторую

функцию h, определенную на значениях типа T и принимающую

значения 0..(n-1). Было бы хорошо, чтобы эта функция принимала на

элементах будущего множества по возможности более разнообразные

значения. Худший случай - это когда ее значения на всех элементах

хранимого множества одинаковы. Эту функцию будем называть хеш-

функцией.

Введем два массива

В этих массивах будут храниться элементы множества. По

возможности мы будем хранить элемент t на месте h(t), считая это

место "исконным" для элемента t. Однако может случиться так, что

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

занятое место (для которого used истинно). В этом случае мы отыщем

ближайшее справа свободное место и запишем элемент туда.

("Справа" значит "в сторону увеличения индексов"; дойдя до края, мы

перескакиваем в начало.) По предположению, число элементов всегда

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

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

любого элемента множества участок справа от его исконного места до

его фактического места полностью заполнен.

Благодаря этому проверка принадлежности заданного элемента t

осуществляется легко: встав на h(t), двигаемся направо, пока не

дойдем до пустого места или до элемента t. В первом случае элемент t

отсутствует в множестве, во втором присутствует. Если элемент

отсутствует, то его можно добавить на найденное пустое место. Если

присутствует, то можно его удалить (положив used = false).

Есть одна проблема:

Дело в том, что при удалении требуемое свойство 'отсутствия пустот'

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

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

(тогда на этом можно успокоиться) или на элемент, стоящий не на

исконном месте. Во втором случае посмотрим, не нужно ли этот

элемент поставить на место дыры. Если нет, то продолжаем поиск,

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

дыра, с которой делаем все то же самое.

1.2.Красно-черные деревья

Красно-черные деревья - один из способов балансировки деревьев.

Название происходит от стандартной раскраски узлов таких деревьев в

красный и черный цвета. Цвета узлов используются при балансировке

дерева. Во время операций вставки и удаления поддеревья может

понадобиться повернуть, чтобы достигнуть сбалансированности

дерева. Оценкой как среднего время, так и наихудшего является

O(log n).

Прекрасно написанные разделы о красно-черных деревьях вы найдете

у Кормена-Ривеста-Лейзертона в их талмуде об алгоритмах.

Красно-черное дерево - это бинарное дерево с следующими

свойствами:

 Каждый узел покрашен либо в черный, либо в красный цвет.

 Листьями объявляются NIL-узлы (т.е. "виртуальные" узлы,

наследники узлов, которые обычно называют листьями; на них

"указывают" NULL указатели). Листья покрашены в черный

цвет

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

 На всех ветвях дерева, ведущих от его корня к листьям, число

черных узлов одинаково.

Количество черных узлов на ветви от корня до листа называется

черной высотой дерева. Перечисленные свойства гарантируют, что

самая длинная ветвь от корня к листу не более чем вдвое длиннее

любой другой ветви от корня к листу. Чтобы понять, почему это так,

рассмотрим дерево с черной высотой 2. Кратчайшее возможное

расстояние от корня до листа равно двум - когда оба узла черные.

Длиннейшее расстояние от корня до листа равно четырем - узлы при

этом покрашены (от корня к листу) так: красный, черный, красный,

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

нарушится свойство 4, из которого вытекает корректность понятия

черной высоты. Поскольку согласно свойству 3 у красных узлов

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

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

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

красных и черных узлов, что и приводит нас к удвоенной длине пути,

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

должны уметь работать с перечисленными свойствами. В частности,

при вставке и удалении эти свойства должны сохраниться.

Вставка

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

следует добавить. Новый узел всегда добавляется как лист, поэтому

оба его потомка являются NIL-узлами и предполагаются черными.

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

предка и проверяем, не нарушается ли красно-черное свойство. Если

необходимо, мы перекрашиваем узел и производим поворот, чтобы

сбалансировать дерево. Вставив красный узел с двумя NIL-потомками,

мы сохраняем свойство черной высоты (свойство 4). Однако, при этом

может оказаться нарушенным свойство 3, согласно которому оба

потомка красного узла обязательно черны. В нашем случае оба

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

NIL-узлами), так что рассмотрим ситуацию, когда предок нового узла

красный: при этом будет нарушено свойство 3. Достаточно

рассмотреть следующие два случая:

Красный предок, красный "дядя": Ситуацию красный-красный

иллюстрирует рис. 1. У нового узла X предок и "дядя" оказались

красными. Простое перекрашивание избавляет нас от красно-красного

нарушения. После перекраски нужно проверить "дедушку" нового

узла (узел B), поскольку он может оказаться красным. Обратите

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

дерева. В самом конце корень мы красим в черный цвет корень дерева.

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

дерева.

Красный предок, черный "дядя": На рис представлен другой вариант

красно-красного нарушения - "дядя" нового узла оказался черным.

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

поддеревья. В этом месте алгоритм может остановиться из-за

отсутствия красно-красных конфликтов и вершина дерева (узел A)

окрашивается в черный цвет. Обратите внимание, что если узел X был

в начале правым потомком, то первым применяется левое вращение,

которое делает этот узел левым потомком.

Каждая корректировка, производимая при вставке узла, заставляет нас

подняться в дереве на один шаг. В этом случае до остановки алгоритма

будет сделано 1 вращение (2, если узел был правым потомком). Метод

удаления аналогичен.

Рис. 1:iВставка - Красный предок, красный "дядя

Рис. 2:iВставка - красный предок, черный "дядя"

1.3.Слоеные списки (скип-листы)

Слоёные списки - это связные списки, которые позволяют вам

пропустить (skip) ненужные элементы, прыгнув сразу к нужному. Это

позволяет преодолеть ограничения последовательного поиска,

являющегося основным источником неэффективного поиска в

списках. В то же время вставка и удаление остаются сравнительно

эффективными. Оценка среднего времени поиска в таких списках есть

O(lg n). Для наихудшего случая оценкой является O(n), но худший

случай крайне маловероятен.

Эта структура очень удобна и сочетает простоту несбалансированного

бинарного дерева с хорошими показателями AVL-tree.

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

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

вы помечаете буквой страницу, откуда начинаются имена,

начинающиеся с этой буквы. На рис., например, самый верхний

список представляет обычный односвязный список. Добавив один

"уровень" ссылок, мы ускорим поиск. Сначала мы идем по ссылкам

уровня 1, затем, когда дойдем по нужного отрезка списка, пойдем по

ссылкам нулевого уровня.

Рис:iУстройство слоёного списка

Эта простая идея может быть расширена - мы можем добавить нужное

число уровней. Внизу на рис. 3.8 мы видим второй уровень, который

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

двигаемся по этому уровню, пока не дойдем до нужного отрезка

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

двигаясь по ссылкам 1-го уровня. Лишь после этого мы проходим по

ссылкам 0-го уровня.

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

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

случайного механизма: при добавлении нового узла мы "бросаем

монету", чтобы определить, нужно ли добавлять еще уровень.

Например, мы можем добавлять очередные уровни до тех пор, пока

выпадает "решка". Если реализован только один уровень, мы имеем

дело фактически с обычным списком и время поиска есть O(n).

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

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

время поиска есть O(lg n).

Поскольку реализация слоёных списков включает в себя случайный

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

границы. При обычных условиях эти границы довольно узки.

Например, когда мы ищем элемент в списке из 1000 узлов,

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

можно оценить как 1/1,000,000,000,000,000,000.

2. Программы на языке С++

2.1.Хеш-таблицы

#include <iostream>

#include <iterator>

#include <stdlib.h>

#include <string>

#define HTBS 100

using namespace std;

int hash(string data,int size)

{

int sum=0;