17. Почему быстрая сортировка проще всего программно реализуется с помощью рекурсии?

18. Как программно реализуется рекурсивный вариант метода быстрой сортировки?

19. Какие особенности имеет не рекурсивная программная реализация метода быстрой сортировки?

20. В чем состоит суть метода пирамидальной сортировки?

21. Какой набор данных имеет пирамидальную организацию?

22. Чем отличаются друг от друга дерево поиска и пирамидальное дерево?

23. Приведите пример пирамидального дерева с целочисленными ключами.

24. Какие полезные свойства имеет пирамидальное дерево?

25. Какие шаги выполняются при построении пирамидального дерева?

26. Что такое просеивание элемента через пирамиду?

27. Приведите практический пример построения пирамидального дерева.

28. Какие шаги выполняются на втором этапе пирамидальной сортировки?

29. Приведите практический пример реализации второго этапа пирамидальной сортировки.

30. Что можно сказать о трудоемкости метода пирамидальной сортировки?

3. Специальные методы сортировки

3.1 Простейшая карманная сортировка

Как было отмечено ранее, специальные методы сортировки основаны либо на использовании некоторой дополнительной информации об исходном наборе данных, либо на использовании дополнительной памяти, сопоставимой по объему с самим сортируемым массивом. Отсюда следует, что они имеют ограниченную область применения, но их огромное преимущество - более высокая эффективность, оцениваемая как O(n).

Самая простая разновидность специальных методов - так называемая карманная сортировка.

Пусть как обычно исходный набор данных включает n элементов, причем относительно их ключей известно следующее:

· ключи являются целыми числами, изменяющимися только от 1 до n

· все эти ключи различные.

В этом случае ключи можно рассматривать как индексы элементов в массиве. Если в исходном массиве значение ключа может НЕ совпадать с индексом элемента, то после сортировки соответствие должно быть полным: ключ 1 - в ячейке 1, ключ 2 - в ячейке 2 и т.д., ключ n - в ячейке n.

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

Например, для массива из 10 элементов с неповторяющимися ключами от 1 до 10 получим:



Вся сортировка сводится лишь к 10 пересылкам и не требует ни одного сравнения! Реализация - одним единственным циклом (здесь Mas - исходный массив, RezMas - результирующий):

for i:= 1 to n do

RezMas [Mas [i].key]:= Mas [i];

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

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

· перемещаем в массиве первый элемент в ячейку i, а i-ый элемент - в первую ячейку; после этой операции i-ый элемент окажется на своем месте

· если ключ первого элемента не равен 1 (например - j), то обмениваем его с j-ым элементом, после чего и j-ый элемент оказывается на своем месте

· повторяем эти действия до тех пор, пока на первом месте не окажется элемент с ключом 1, причем каждое повторение обязательно размещает один элемент массива на своем "законном" месте

· при необходимости повторяем эти действия и для других элементов массива.

Пример работы алгоритма - в следующей таблице.

В этом примере потребовалось 17 сравнений и 7 пересылок. В общем случае, трудоемкость метода пропорциональна n.



Схема программной реализации:

for i:= 1 to n do

while Mas [i]. key <> i do

"переставить Mas [i]и Mas [Mas [i].key]";

3.2 Карманная сортировка для случая повторяющихся ключей

Рассмотренный метод можно обобщить следующим образом. Пусть по-прежнему ключи могут иметь значения только от 1 до n, но во входном наборе каждое значение может повторяться любое число раз, в том числе и ноль. Пусть исходный массив содержит m элементов, причем m>n. В этом случае с одним и тем же ключом может быть связано несколько элементов, и их нельзя поместить в одну ячейку результирующего массива.

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

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

Пример. Пусть задан следующий входной набор из 15 элементов с диапазоном изменения ключей от 1 до 5 (в скобках указан ключ элемента):

а ₁(4), а ₂(2), а ₃(5), а ₄(1), а ₅(4), а ₆(3), а ₇(4), а ₈(3), а ₉(5), а ₁₀(1), а ₁₁(3), а ₁₂(2), а ₁₃(2), а ₁₄(5), а ₁₅(3)

Тогда эти элементы будут распределены следующим образом:

После объединения списков получим:

а ₄, а ₁₀, а ₂, а ₁₂, а ₁₃, а ₆, а ₈, а ₁₁, а ₁₅, а ₁, а ₅, а ₇, а ₃, а ₉, а _14.

Для программной реализации необходимо объявить массив указателей и ссылочный тип для поддержки списков. Дополнительные затраты памяти связаны в первую очередь с реализацией дополнительных списков, т.к. общее число элементов в этих списках равно m, а кроме того для каждого элемента надо 4 байта для адресных полей. Трудоемкость данного метода оценивается соотношением O(m+n), а при m"n становится пропорциональной числу элементов m.

3.3 Поразрядная сортировка

Данный метод является обобщением карманной сортировки. Пусть известно, что каждый ключ является k-разрядным целым числом. Например, если k = 4, то все ключи находятся в диапазоне 0000-9999. Смысл поразрядной сортировки заключается в том, что k раз повторяется карманная сортировка. На первом шаге все ключи группируются по младшей цифре (разряд единиц). Для этого в каждом ключе выделяется младшая цифра и элемент помещается в соответствующий список-карман для данной цифры. Потом все списки объединяются и создается новый массив, в котором элементы упорядочены по младшей цифре ключа. К этому массиву опять применяется карманная сортировка, но уже по более старшей цифре (разряд десятков): в каждом ключе выделяется вторая справа цифра и элементы распределяются по соответствующим спискам. Потом списки объединяются в массив, где элементы будут упорядочены уже по двум младшим цифрам. Процесс распределения по все более старшим цифрам с последующим объединением повторяется до старшей цифры (разряд k).

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

Пример. Пусть имеется исходный набор из 15-ти двухразрядных ключей (k=2): 56, 17, 83, 09, 11, 27, 33, 02, 16, 45, 08, 37, 66, 99, 90

Первый шаг: выделяем младшую цифру и распределяем ключи по десяти спискам:

ключ 56 в список для цифры 6, ключ 17 в список для цифры 7, ….., ключ 16 опять в список для цифры 6 и т.д.

Объединяем списки: 90, 11, 02, 83, 33, 45, 56, 16, 66, 17, 27, 37, 08, 09, 99.

В этом наборе ключи упорядочены по младшей цифре.

Второй шаг: выделяем старшую цифру (десятки) и распределяем ключи по своим спискам:

ключ 90 в список для 9, ключ 11 в список для 1, ключ 02 в список для 0 и т.д.

Объединение этих списков дает отсортированный набор:

02, 08, 09, 11, 16, 17, 27, 33, 37, 45, 56, 66, 83, 90, 99

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

· обнулить все 20 указателей

· циклом по числу элементов (m) распределить элементы по своим спискам, выделяя в ключе необходимую цифру

· циклом по 10 объединить списки в новый набор данных.

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

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

3.4 Практическое задание

Реализовать специальные методы сортировки:

· Простейшую карманную с использованием второго массива и без него

· Обобщенную карманную сортировку с повторяющимися ключами и дополнительными списками

· Поразрядную сортировку.

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

3.5 Контрольные вопросы

1. В чем состоят особенности специальных методов сортировки?

2. Какие условия должны выполняться для применимости простейшего метода карманной сортировки?

3. Как в простейшем случае выполняется карманная сортировка?

4. Как программно реализуется простейшая карманная сортировка?

5. Как реализуется простейшая карманная сортировка без использования второго массива?

6. Приведите практический пример простейшей карманной сортировки массива "на месте".

7. Как программно реализуется простейшая карманная сортировка с использованием только одного массива?

8. Какое обобщение имеет простейшая карманная сортировка?

9. Какие структуры данных необходимы для реализации карманной сортировки с повторяющимися ключами?

10. Как выполняется карманная сортировка для случая повторяющихся ключей?

11. Приведите практический пример использования карманной сортировки с повторяющимися ключами.

12. Какие достоинства и недостатки имеет карманная сортировка массивов?

13. Какие условия необходимы для применения метода поразрядной сортировки?

14. В чем состоит смысл метода поразрядной сортировки массивов?

15. Какие структуры данных необходимы для реализации метода поразрядной сортировки?

16. Приведите практический пример использования поразрядной сортировки.

17. Какие шаги необходимы для реализации метода поразрядной сортировки?

18. Что можно сказать об эффективности метода поразрядной сортировки?

19. Какие достоинства и недостатки имеет поразрядная сортировка?

20. Как программно выполняется поразрядная сортировка?

4. Поиск с использованием хеш-функций

4.1 Основные понятия

Пусть имеется набор из n элементов а ₁, а ₂, а ₃,..., а_n с некоторыми ключами (как и раньше, для простоты будем считать, что сам элемент совпадает с его ключом). Требуется этот набор организовать в виде некоторой структуры данных с возможностью многократного поиска в нем элементов с заданным ключом. Эта задача может решаться различными способами:

· если набор элементов никак не упорядочен, то поиск выполняется прямым сравнением всех элементов в массиве или списке с трудоемкостью O(n)

· если элементы упорядочены в массиве или в дереве поиска, поиск более эффективно выполняется как двоичный, с трудоемкостью О(log ₂ n)

Возникает вопрос: существуют ли еще более эффективные методы поиска? Оказывается, при выполнении некоторых дополнительных условий можно организовать исходный набор ключей в виде специальной структуры данных, называемой хеш-таблицей, поиск в которой ЛЮБОГО элемента в идеале выполняется за ОДНО сравнение и НЕ зависит от размерности входного набора. Другими словами, трудоемкость такого метода поиска, называемого хеш-поиском, пропорциональна О(1), что является абсолютным рекордом!

Метод хеш-поиска заключается в следующем. Исходные элементы а ₁, а ₂, а ₃,..., а_n распределяются некоторым специальным образом по ячейкам массива. Пока будем считать, что число ячеек массива m > n. Идеальным поиском можно считать такой, когда по любому входному ключу сразу вычисляется индекс ячейки с этим ключом, без проверки содержимого остальных ячеек. Для вычисления индекса ячейки по входному ключу используется специальная функция, называемая хеш-функцией. Эта функция ставит в соответствие каждому ключу индекс ячейки массива, где должен располагаться элемент с этим ключом:

h (а_i) = j, j = (1, m);

Массив, заполненный элементами исходного набора в порядке, определяемом хеш-функцией, называется хеш-таблицей. Отсюда следует, что решение задачи поиска данным методом во многом зависит от используемой хеш-функции. Предложено довольно много различных хеш-функций. Самой простой, но не самой лучшей хеш-функцией является функция взятия остатка от деления ключа нацело на m:

h (а_i) = (а_i mod m) + 1;

Ясно, что каждое значение этой функции лежит в пределах от 1 до m и может приниматься в качестве индекса ячейки массива.

Принято считать, что хорошей является хеш-функция, которая удовлетворяет следующим условиям:

· функция должна быть очень простой с вычислительной точки зрения

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

Использование данного метода включает два этапа:

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

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

Рассмотрим два примера с целыми и строковыми ключами.

Пример 1. Пусть задан набор из 8 целочисленных ключей:

35, 19, 07, 14, 26, 40, 51, 72.

Требуется распределить эти ключи в массиве из 10 ячеек с помощью простейшей хеш-функции.

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

35 mod 10 = 5, индекс размещения ключа 35 равен 6

19 mod 10 = 9, индекс размещения ключа 19 равен 10

07 mod 10 = 7, индекс размещения ключа 07 равен 8

14 mod 10 = 4, индекс размещения ключа 14 равен 5

26 mod 10 = 6, индекс размещения ключа 26 равен 7

40 mod 10 = 0, индекс размещения ключа 40 равен 1

51 mod 10 = 1, индекс размещения ключа 51 равен 2

72 mod 10 = 2, индекс размещения ключа 72 равен 3

Получаем следующую хеш-таблицу:

Если требуется найти в этой хеш-таблице ключ со значением 26, то этот поиск выполняется ровно за одно сравнение: делим 26 на 10, берем остаток 6, входим в ячейку с индексом 7 и сравниваем находящееся там значение с заданным ключом.

Пример 2. Пусть ключи являются строковыми. В этом случае предварительно текстовый ключ надо преобразовать в числовой. Например, можно сложить ASCII-коды всех символов, входящих в этот текстовый ключ.

Например, если строковый ключ имеет значение END, то его целочисленный эквивалент будет равен сумме кодов всех трех символов: ord(E) + ord(N) + ord(D) = 69 + 78 + 68 = 215

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

h (END) = (215 mod 10) + 1 = 6

h (VAR) = (233 mod 10) + 1 = 4

h (AND) = (211 mod 10) + 1 = 2

h (NIL) = (227 mod 10) + 1 = 8

В результате для этих четырех строковых ключей получаем следующую хеш-таблицу:

Поиск в этой таблице некоторого ключа выполняется очень просто: находится целочисленный эквивалент строкового ключа, вычисляется значение хеш-функции и сравнивается содержимое полученной ячейки с заданным ключом. Например, h (VAR) = 4, сравниваем содержимое ячейки 4 с ключом VAR, фиксируем совпадение и завершаем поиск с признаком успеха.

Приведенные выше примеры носят несколько искусственный характер, поскольку они описывают идеальный случай, когда хеш-функция для всех различных ключей дает РАЗЛИЧНЫЕ значения индексов в массиве. В этом случае каждый ключ имеет свое уникальное расположение в массиве, не конфликтуя с другими ключами. Подобная ситуация возможна, если исходный набор ключей известен заранее и после построения хеш-таблицы не изменяется, т.е. ключи НЕ добавляются и НЕ удаляются из хеш-таблицы. В этом случае за счет подбора хеш-функции и, возможно, небольшого изменения самих ключей можно построить бесконфликтную хеш-таблицу. Важным практическим примером такой ситуации является построение таблицы ключевых слов в программах-трансляторах с языков программирования. Здесь набор ключевых слов является постоянным, изменяясь только при изменении версии транслятора, а с другой стороны, обработка транслятором входного текста на языке программирования требует многократного и очень быстрого распознавания в этом тексте ключевых слов языка.

К сожалению, идеальный случай возможен весьма редко, и ограничивать применение хеш-поиска только данным случаем было бы неразумно, учитывая выдающиеся потенциальные скоростные возможности метода. Поэтому были предложены различные усовершенствования хеш-поиска, существенно расширившие область его использования. Эти усовершенствования так или иначе связаны с обработкой конфликтных ситуаций, когда два РАЗНЫХ ключа претендуют на ОДНО и то же место в хеш-таблице, т.е. хеш-функция дает для этих разных ключей а_i и а_к одно и то же значение: h (а_i) = h (а_к) = j.

Например, в приведенном выше примере со строковыми ключами простая перестановка символов в ключе приводит к конфликту:

h (VAR) = h (RAV) = h (AVR) = (233 mod 10) + 1 = 4.

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

4.2 Разрешение конфликтов: открытое хеширование

Пусть имеется n элементов а ₁, а ₂, а ₃,..., а_n, на основе которых требуется построить хеш-таблицу, причем некоторые ключи могут конфликтовать между собой, претендуя на одну и ту же ячейку таблицы. Идея открытого хеширования совершенно прозрачна: связать все элементы с одним и тем же значением хеш-функции во вспомогательный линейный список. Данный метод иногда называют методом цепочек.

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

Алгоритм построения хеш-таблицы:

· находим значение хеш-функции для очередного ключа и по этому значению как индексу входим в таблицу

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

· если ячейка занята, то сравниваем хранящийся там ключ с заданным ключом:

· если ключи совпадают, то каким-то образом обрабатываем повторный ключ (например, просто ничего не выполняем)

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

Алгоритм поиска в построенной таблице:

· находим значение хеш-функции для искомого ключа и по этому значению как индексу входим в таблицу

· если ячейка с найденным индексом пустая, то поиск заканчивается неудачей

· если ячейка не пустая, то выполняем сравнение ключей:

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

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

Пример. Задано 10 целочисленных ключей, на основе которых надо построить хеш-таблицу размерности 5, используя для разрешения конфликтов метод открытого хеширования. Поскольку число исходных элементов n=10 больше размерности таблицы (m=5), то без использования вспомогательных списков таблицу построить нельзя. Набор входных ключей с соответствующими значениями хеш-функции приведены в следующей таблице (использована простейшая хеш-функция):

ключ	33	17	09	04	22	19	42	53	64	25
значение хеш-функции	4	3	5	5	3	5	3	4	5	1

Тогда хеш-таблица будет иметь следующий вид:

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

· ключ 33 - одно сравнение, т.к. он непосредственно находится в ячейке таблицы

· ключи 17 и 09 - тоже по одному сравнению

· ключ 04 - два сравнения (в ячейке 5 находится ключ 09, идем по списку, совпадение на первом элементе)

· ключ 22-2 сравнения

· ключи 19 и 42 - по 3 сравнения (вторые элементы в списках)

· ключ 53-2 сравнения

· ключ 64-4 сравнения

· ключ 25-1 сравнение.

Итого - 20 сравнений, т.е. в среднем 2 сравнения на один ключ.

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

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

4.3 Разрешение конфликтов: внутреннее хеширование

Пусть имеется n элементов а ₁, а ₂, а ₃,..., а_n, на основе которых требуется построить хеш-таблицу, причем некоторые ключи могут конфликтовать между собой, претендуя на одну и ту же ячейку таблицы. Внутреннее хеширование для размещения конфликтующих ключей использует не вспомогательные списки, а свободные ячейки хеш-таблицы. Для этого размер таблицы обязательно должен быть больше числа элементов (m>n).

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

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

Самое простое правило заключается в последовательном круговом просмотре всех ячеек, начиная с индекса j, т. е. ячеек с номерами j+1, j+2, …, m-1, m, 1, 2, …, j-1.

Пример. Пусть задано 6 целочисленных ключей 15, 17, 19, 35, 05, 28. Построим на их основе хеш-таблицу размерности 10 с помощью простейшего правила определения свободных ячеек.

h (15) = 6, размещаем ключ 15 в ячейке 6

h (17) = 8, размещаем ключ 17 в ячейке 8

h (19) = 10, размещаем ключ 19 в ячейке 10

h (35) = 6, но ячейка 6 уже занята, проверяем следующую: ячейка 7 свободна, размещаем ключ 35 в ячейке 7

h (05) = 6, ячейка 6 занята, следующая ячейка 7 тоже занята, ячейка 8 - тоже, поэтому размещаем ключ 05 в ячейке 9

h (28) = 9, ячейка 9 занята, ячейка 10 занята и является последней, проверяем ячейку 1 и размещаем ключ 28 именно в ней.

Получим следующую хеш-таблицу:

Для поиска любого из шести ключей в этой таблице потребуется в среднем (1+2+1+4+1+6 = 15)/6 = 2,5 сравнений.

Для циклического вычисления индекса ключа а_k в простейшем случае можно использовать следующую простую формулу:

j = (h(а_k) + i) mod m) + 1,

где i = 0, 1, 2, …, m-2

Здесь для целочисленных ключей h(а_k) = а_k.

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

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

j = ((h (а_k) + i²) mod m) + 1,

где i = 0, 1, 2, …, m-2.

Эта функция дает не постоянный шаг приращения индекса (+1), а переменный: +1, +4, +9, +16 и т.д.

Алгоритм построения хеш-таблицы:

· находим значение хеш-функции для очередного ключа и по этому значению как индексу входим в таблицу

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

· если ячейка занята, то сравниваем хранящийся там ключ с заданным ключом:

· если ключи совпадают, то каким-то образом обрабатываем повторный ключ (например, просто ничего не выполняем)

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

Алгоритм поиска:

· находим значение хеш-функции для искомого ключа и по этому значению как индексу входим в таблицу

· если ячейка с найденным индексом пустая, то поиск заканчивается неудачей

· если ячейка не пустая, то выполняем сравнение ключей

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

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

Эффективность внутреннего хеширования существенно зависит от наличия в хеш-таблице пустых ячеек, поэтому на практике идут на искусственное увеличение размерности таблицы на. 10-20 % для обеспечения достаточного количества свободных клеток.

Многочисленные эксперименты показывают, что для заполненной на 50 % таблицы (половина ячеек пустые) для поиска любого ключа в среднем требуется лишь 1,5 сравнения, причем это число не зависит от количества элементов. Это еще раз подтверждает высочайшую эффективность хеш-поиска!

В заключение дадим общие рекомендации по применению хеш-поиска.

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

2. Если набор ключей может меняться и заранее неизвестен, то важным становится выбор хеш-функции для равномерного распределения ключей по таблице. Одной из лучших хеш-функций считается следующая: исходный целочисленный ключ возводится в квадрат, преобразуется в двоичное представление в виде набора битов и из середины этого набора извлекается необходимое число битов в соответствии с размерностью таблицы (например, для таблицы размерности 1024 необходимо извлечь 10 битов).

3. При использовании открытого хеширования рекомендуется размер таблицы выбирать равным n/2, что в среднем должно обеспечивать короткие вспомогательные списки (1-2 элемента), которые могут просматриваться только последовательно.

4. При использовании внутреннего хеширования рекомендуется размер таблицы выбирать равным 1,2*n для обеспечения достаточного количества свободных ячеек.

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

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

7. Ну и, наконец - ложка дегтя в бочке меда: метод совершенно непригоден для обработки упорядоченных наборов.

4.4 Практические задания

Задание 1. Построить бесконфликтную хеш-таблицу для заданного набора текстовых ключей. Число ключей (и размер таблицы) равен 10. В качестве ключей взять 10 любых служебных слов языка Паскаль. Для преобразования текстовых ключей в числовые значения использовать суммирование кодов символов текстового ключа:

код (End) = код (E) + код (n) + код (d).

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

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

Если некоторые исходные ключи будут конфликтовать друг с другом, можно изменить исходное слово, например - сменить регистр начальной буквы или всех букв в слове, полностью заменить слово на близкое по значению (End на Stop и.т.д.), ввести какие-либо спецсимволы или придумать другие способы.

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

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

· вывести хеш-таблицу на экран

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

Задание 2. Реализовать метод внутреннего хеширования. Исходные ключи - любые слова (например - фамилии). Размер хеш-таблицы должен задаваться в программе с помощью константы m. Хеш-функция - такая же, что и в задании 1, но делить надо на константу m. В случае возникновения конфликта при попытке размещения в таблице нового ключа, для него ищется первое свободное по порядку место по формуле:

j = ((h (ключ) + i) mod m) + 1,

где i = 0, 1, 2,..., m-2.

Программа должна выполнять следующие действия:

· добавление нового ключа в таблицу с подсчетом сделанных при этом сравнений

· поиск заданного ключа в таблице с подсчетом сделанных при этом сравнений

· вывод текущего состояния таблицы на экран.

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

Задание 3. Реализовать метод открытого хеширования. Исходные ключи - любые слова (например - фамилии). Размер хеш-таблицы должен задаваться в программе с помощью константы m. Хеш-функция - такая же, что и в задании 1, но делить надо на константу m. В случае возникновения конфликта при попытке размещения в таблице нового ключа этот ключ добавляется в конец вспомогательного списка. Это требует включения в каждую ячейку хеш-таблицы двух указателей на начало и конец вспомогательного списка.

Программа должна выполнять следующие действия:

· добавление нового ключа в таблицу с подсчетом сделанных при этом сравнений

· поиск заданного ключа в таблице с подсчетом сделанных при этом сравнений

· вывод текущего состояния таблицы на экран

· удаление заданного ключа из таблицы.

Алгоритм удаления:

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

· если удаляемый элемент найден в ячейке таблицы, то эта ячейка либо становится пустой (если связанный с ней список пуст), либо в нее записывается значение из первого элемента списка с соответствующим изменением указателей

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

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

4.5 Контрольные вопросы

1. В чем заключается метод хеш-поиска?

2. Для чего используется хеш-функция и какие к ней предъявляются требования?

3. Что такое хеш-таблица и как она используется?

4. Как по трудоемкости соотносятся между собой основные методы поиска (полный перебор, двоичный поиск, хеш-поиск)?

5. Как с помощью простейшей хеш-функции находится расположение в таблице строковых ключей?

6. Какие проблемы могут возникать при построении хеш-таблиц с произвольными наборами ключей?

7. В каких ситуациях можно построить бесконфликтную хеш-таблицу?

8. Где на практике и почему можно использовать бесконфликтные хеш-таблицы?

9. Что такое открытое хеширование и для чего оно применяется?

10. Какие структуры данных используются для реализации открытого хеширования?

11. Какие шаги выполняет алгоритм построения хеш-таблицы при открытом хешировании?

12. Какие шаги выполняет алгоритм поиска в хеш-таблице при открытом хешировании?

13. Какие проблемы могут возникать при использовании открытого хеширования?

14. Как влияет размер хеш-таблицы на эффективность открытого хеширования?

15. Что такое внутреннее хеширование и для чего оно применяется?

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

17. Какие шаги выполняет алгоритм построения хеш-таблицы при внутреннем хешировании?

18. Какие шаги выполняет алгоритм поиска в хеш-таблице при внутреннем хешировании?

19. Как влияет размер хеш-таблицы на эффективность внутреннего хеширования?

20. В каких задачах НЕ следует применять метод хеш-поиска?

5. Внешний поиск и внешняя сортировка

5.1 Особенности обработки больших наборов данных

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

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

В свою очередь, это требует четкого понимания особенностей хранения информации во внешней памяти. Как известно, для хранения данных на диске создаются элементарные физические единицы (секторы), которые на логическом уровне объединяются в более крупные кластеры. Размер кластера определяется типом операционной системы. За одно обращение к диску считывается содержимое сразу всего кластера. Это связано с тем, что при таком подходе минимизируется время поиска необходимых секторов на диске, включающее в себя время на подвод считывающей головки к нужной дорожке и время на поворот диска к нужному сектору. Считываемые с диска наборы байтов помещаются в буферную область памяти. Отсюда можно сделать вывод, что методы поиска и сортировки должны быть построены таким образом, чтобы можно было обрабатывать сразу целую группу элементов. Нельзя читать данные из внешней памяти в ОП по одному элементу - должна быть считана целая группа логически связанных элементов, которая потом обрабатывается алгоритмом и, возможно, приводит к необходимости чтения другой группы элементов.

На этих принципах построен ряд методов внешнего поиска и сортировки. Среди них одним из наиболее известных методов поиска является метод Б-деревьев (B-tree).

5.2 Организация внешнего поиска с помощью Б-деревьев

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

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

В качестве примера рассмотрим обычное дерево поиска из 15 вершин. Пусть для простоты оно является идеально сбалансированным. Выделим в нем 5 элементарных поддеревьев по 3 вершины в каждом и логически объединим эти вершины вместе в виде страниц. Если в дереве необходимо найти какую-либо терминальную вершину, и вершины считываются в ОП по одной, то для этого в обычном дереве потребуется 4 обращения к внешней памяти. А в дереве со страничной организацией потребуется считать из внешней памяти лишь 2 страницы - корневую и одну из терминальных. Даже в этом простейшем примере страничная организация дерева позволяет уменьшить число обращений к диску в два раза. Для сверхбольших деревьев этот эффект становится еще более заметным.

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

Б-дерево порядка m со страничной организацией - это структура данных, удовлетворяющая следующим условиям:

· весь набор из n элементов разбивается на отдельные страницы, причем каждая страница может содержать от m до 2m вершин, за исключением корневой страницы, для которой число вершин может изменяться от 1 до 2m

· каждая страница является либо терминальной (потомков нет), либо имеет ровно на одного потомка больше по сравнению с текущим числом вершин на этой странице

· все терминальные страницы находятся на одном уровне.

Пример. Рассмотрим простейшее Б-дерево порядка m=2 с ключами целого типа. В соответствии с приведенными выше правилами, каждая страница такого дерева содержит от 2 до 4 вершин, а корневая - от 1 до 4. Каждая нетерминальная страница может иметь от 3 до 5 потомков. Пример дерева - на рисунке (к сожалению, терминальные страницы приходится располагать на разных уровнях).

Поскольку Б-дерево является обобщением классического дерева поиска, то оно обладает следующими свойствами:

· на каждой странице элементы упорядочены по возрастанию ключей

· каждая страница-потомок содержит ключи в строго определенном диапазоне, который задается родительскими ключами.

Последнее свойство является обобщением основного правила дерева поиска. Например, страница с ключами 40, 50 и 60 имеет четырех потомков, причем самый левый потомок содержит ключи меньше 40 (но больше 30), более правая страница содержит ключи в диапазоне от 40 до 50, еще более правая - в диапазоне от 50 до 60, а самая правая - больше 60.

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

Например, если число элементов в наборе данных n = 1 миллион, а порядок Б-дерева m = 100, то log₁₀₀1000000 = 3, т.е. максимум может потребоваться 3 обращения к внешней памяти. С другой стороны, даже в этом наихудшем случае оперативная память используется достаточно эффективно (примерно половина памяти от заявленного объема).

5.3 Б-дерево как структура данных

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

Каждая страница должна содержать следующие данные:

· текущее количество элементов на странице (оно изменяется от m до 2m)

· указатель на страницу, являющуюся самым левым потомком данной страницы

· основной массив элементов страницы, размерность массива 2m, каждый элемент - это запись со следующими полями:

· ключ некоторого типа

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

· информационная часть (как некоторая структура или указатель на область памяти).

Соответствующие описания типов можно сделать следующим образом:

type pPage = ^Page; {ссылочный тип для адресации страниц}

TItem = record {описание структуры элемента массива}

key: integer; {ключ вершины дерева}

cPage: pPage; {указатель на страницу-потомка}

inf: <описание информационной части>;

end;

Page = record {описание структуры страницы}

nPage: word; {число вершин на странице}

leftPage: pPage; {указатель на самого левого потомка}

mas: array [1.. 2m]of TItem; {основной массив}

end;

Из переменных достаточно ввести два указателя: на корневую страницу (pRoot) и текущую обрабатываемую в данный момент страницу (pCurrent).

Схематично структуру страницы можно представить следующим образом (для краткости указатель pCurrent заменен идентификатором pC):

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

5.4 Поиск элемента в Б-дереве

Пусть имеется Б-дерево порядка m, в котором требуется найти вершину с ключом x. Алгоритм поиска:

· считываем в ОП корневую страницу и организуем на этой странице поиск заданного элемента; если порядок Б-дерева небольшой, то можно применить обычный поиск прямым перебором; для деревьев большого порядка можно использовать метод двоичного поиска в упорядоченном массиве

· если заданный элемент на корневой странице найден, то обрабатываем его и завершаем поиск

· если заданного элемента на корневой странице нет, то возможно появление одной из трех следующих ситуаций:

Ш искомый элемент меньше самого левого ключа (x<pRoot^.mas [1].key); в этом случае поиск надо продолжить на странице, определяемой самой левой ссылкой (pRoot^.leftPage), для чего в ОП загружается вторая страница и поиск на ней повторяется описанным выше образом

Ш искомый элемент находится между двумя элементами (pRoot^.mas [j].key < x < pRoot^.mas [j+1].key); в этом случае поиск надо продолжить на странице, которая определяется ссылкой pRoot^.mas [j].cPage

Ш искомый элемент больше самого правого элемента (x > pRoot^.mas [nPage].key); поиск продолжаем на странице, определяемой ссылкой в последнем элементе массива (pRoot^.mas [nPage].cPage)

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

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

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

Например, для рассмотренного выше Б-дерева поиск элемента с ключом 43 будет выполнен следующим образом:

· заходим на корневую страницу и устанавливаем, что ключ 43 больше всех ключей на корневой странице

· загружаем в ОП новую страницу, определяемую самой правой ссылкой на корневой странице

· организуем поиск ключа 43 среди элементов новой страницы (40, 50, 60) и фиксируем ситуацию расположения ключа 43 между ключами 40 и 50

· загружаем в ОП третью страницу, определяемую ссылкой у элемента 40 и организуем ее просмотр

· на этой странице (41, 42, 43, 44) находим искомый элемент.

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

5.5 Добавление вершины в Б-дерево

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

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

При этом возможны следующие две ситуации:

· текущая страница, в которую должен быть вставлен новый элемент, заполнена не полностью (pCurrent^.nPage < 2m); в этом случае новый элемент просто вставляется в данную страницу в нужное место, с увеличением счетчика числа элементов на странице

· пусть текущая страница заполнена полностью, т.е. pCurrent^.nPage = 2m; добавление элемента на полностью заполненную страницу реализуется за счет разделения этой страницы на две страницы; создается новая страница, и после этого старая и новые страницы заполняются равномерно:

Ш левые m элементов передаются на новую страницу

Ш правые m элементов остаются на старой странице

Ш центральный (серединный) элемент передается наверх на родительскую страницу.

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

Пример. Пусть в Б-дерево порядка 2 надо добавить вершину с ключом х = 32.

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

Такой алгоритм добавления сохраняет структуру Б-дерева, т.к. синхронно на 1 увеличивается число элементов на родительской странице и число ее страниц-потомков.

Если в данном примере добавить еще элементы 36 и 38, то при попытке добавления элемента 33 опять придем к необходимости расщепления страницы:

Поскольку корневая страница заполнена полностью, происходит ее расщепление на две страницы, выталкивание наверх элемента 30 и создание новой корневой страницы

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

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

· адрес новой текущей страницы, используемый как в процессе движения от корневой страницы к терминальной, так и обратно; поскольку этот адрес автоматически должен запоминаться и восстанавливаться, ссылочный параметр надо объявить как параметр-значение

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

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

Схематично подпрограмма Add описывается следующим образом:

procedure Add (pCurrent: pPage; var IsUp: boolean; var Item: TItem);

...