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

Курсовая работа - Сравнение эффективности различных подходов к хранению данных
скачать (241 kb.)
Доступные файлы (1):
n1.doc241kb.30.05.2012 08:08скачать

n1.doc

  1   2   3


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

СибГУТИ
Кафедра ВС

Курсовая работа.
Сравнение эффективности

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

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

Выполнили:

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

г.Новосибирск 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]. Чтобы найти число, мы его хешируем и проходим по соответствующему списку. Чтобы удалить число, мы находим его и удаляем элемент списка, его содержащий. При добавлении элементов в хеш-таблицу выделяются куски динамической памяти, которые организуются в виде связанных списков, каждый из которых соответствует входу хеш-таблицы. Этот метод называется связыванием.
Если хеш-функция распределяет совокупность возможных ключей равномерно по множеству индексов, то хеширование эффективно разбивает множество ключей. Наихудший случай - когда все ключи хешируются в один индекс. При этом мы работаем с одним линейным списком, который и вынуждены последовательно сканировать каждый раз, когда что-нибудь делаем. Отсюда видно, как важна хорошая хеш-функция.

Размер хеш-таблицы должен быть достаточно большим, чтобы в ней оставалось разумно большое число пустых мест. Как видно из таблицы 3.1, чем меньше таблица, тем больше среднее время поиска ключа в ней. Хеш-таблицу можно рассматривать как совокупность связанных списков. По мере того, как таблица растет, увеличивается количество списков и, соответственно, среднее число узлов в каждом списке уменьшается. Пусть количество элементов равно n. Если размер таблицы равен 1, то таблица вырождается в один список длины n. Если размер таблицы равен 2 и хеширование идеально, то нам придется иметь дело с двумя списками по n/100 элементов в каждом. Это сильно уменьшает длину списка, в котором нужно искать. Как мы видим в таблице, имеется значительная свободы в выборе длины таблицы
Таблица: Зависимость среднего времени поиска (µ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   3


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации