Рассмотренный метод можно обобщить следующим образом. Пусть по-прежнему ключи могут иметь значения только от 1 до n, но во входном наборе каждое значение может повторяться любое число раз, в том числе и ноль. Пусть исходный массив содержит m элементов, причем m>n. В этом случае с одним и тем же ключом может быть связано несколько элементов, и их нельзя поместить в одну ячейку результирующего массива.
Очевидным решением является использование вспомогательных списков для хранения элементов с одинаковыми ключами. Тем самым, приходим к использованию комбинированной структуры данных, а именно – массиву списков. Каждая ячейка массива соответствует одному конкретному значению ключа в диапазоне от 1 до n и хранит указатель на связанный список одноключевых элементов.
Тогда прежде всего надо распределить элементы входного набора по ячейкам результирующего массива в соответствии со значениями ключей, создавая и дополняя при необходимости вспомогательные списки. После этого, если требуется получить общий результирующий отсортированный набор данных, можно объединить все списки, добавляя в конец одного списка начало другого. Это легко реализуется, если в каждой ячейке результирующего массива хранить не только адрес первого элемента списка, но и адрес последнего элемента.
Пример. Пусть задан следующий входной набор из 15 элементов с диапазоном изменения ключей от 1 до 5 (в скобках указан ключ элемента):
а1(4), а2(2), а3(5), а4(1), а5(4), а6(3), а7(4), а8(3), а9(5), а10(1), а11(3), а12(2), а13(2), а14(5), а15(3)
Тогда эти элементы будут распределены следующим образом:
| ключ |
| ||||||||
   начало
| |||||||||
| |||||||||
   начало
| |||||||||
| |||||||||
   начало
| |||||||||
 конец
| |||||||||
| |||||||||
  конец
| |||||||||
| |||||||||
  конец
|
После объединения списков получим:
а4, а10, а2, а12, а13, а6, а8, а11, а15, а1, а5, а7, а3, а9, а14
Для программной реализации необходимо объявить массив указателей и ссылочный тип для поддержки списков. Дополнительные затраты памяти связаны в первую очередь с реализацией дополнительных списков, т.к. общее число элементов в этих списках равно m, а кроме того для каждого элемента надо 4 байта для адресных полей. Трудоемкость данного метода оценивается соотношением O(m+n), а при m>>n становится пропорциональной числу элементов m.
Поразрядная сортировка
Данный метод является обобщением карманной сортировки. Пусть известно, что каждый ключ является 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 и т.д.
9 0 1 1 0 2 8 3 4 5 5 6 1 7 0 8 0 9
3 3 1 6 2 7 9 9
6 6 3 7
Объединяем списки: 90, 11, 02, 83, 33, 45, 56, 16, 66, 17, 27, 37, 08, 09, 99
В этом наборе ключи упорядочены по младшей цифре
Второй шаг: выделяем старшую цифру (десятки) и распределяем ключи по своим спискам:
ключ 90 в список для 9, ключ 11 в список для 1, ключ 02 в список для 0 и т.д.
0 2 1 1 2 7 3 3 4 5 5 6 6 6 8 3 9 0
0 8 1 6 3 7 9 9
0 9 1 7
Объединение этих списков дает отсортированный набор:
02, 08, 09, 11, 16, 17, 27, 33, 37, 45, 56, 66, 83, 90, 99
Для программной реализации необходимо объявить десятиэлементный массив и ссылочный тип для организации списков. Удобно вместе с началом каждого списка хранить указатель на его последний элемент, что упрощает как добавление новых элементов в конец списка, так и объединение отдельных списков. Внешний цикл алгоритма повторяется k раз (разрядность ключа). Каждый раз внутри этого цикла необходимо:
· обнулить все 20 указателей
|
|
· циклом по числу элементов (m) распределить элементы по своим спискам, выделяя в ключе необходимую цифру
· циклом по 10 объединить списки в новый набор данных
В целом, поразрядная сортировка не эффективна при малых объемах входных данных, но чем больше этот объем, тем выше эффективность метода. Трудоемкость пропорциональна объему входных данных, что лучше чем у быстрой сортировки. Платой за это являются дополнительные затраты памяти для поддержки вспомогательных списков.
Интересно отметить, что данный метод очень хорошо подходит для современных архитектур вычислительных систем с конвейерной обработкой данных и использованием нескольких процессоров.
Практическое задание
Реализовать специальные методы сортировки:
· Простейшую карманную с использованием второго массива и без него
· Обобщенную карманную сортировку с повторяющимися ключами и дополнительными списками
· Поразрядную сортировку
Все методы реализуются как подпрограммы и поэтапно добавляются в главную программу.
3.5. Контрольные вопросы по теме
1. В чем состоят особенности специальных методов сортировки?
2. Какие условия должны выполняться для применимости простейшего метода карманной сортировки?
3. Как в простейшем случае выполняется карманная сортировка?
4. Как программно реализуется простейшая карманная сортировка?
5. Как реализуется простейшая карманная сортировка без использования второго массива?
6. Приведите практический пример простейшей карманной сортировки массива “на месте”.
7. Как программно реализуется простейшая карманная сортировка с использованием только одного массива?
8. Какое обобщение имеет простейшая карманная сортировка?
9. Какие структуры данных необходимы для реализации карманной сортировки с повторяющимися ключами?
10. Как выполняется карманная сортировка для случая повторяющихся ключей?
11. Приведите практический пример использования карманной сортировки с повторяющимися ключами.
12. Какие достоинства и недостатки имеет карманная сортировка массивов?
13. Какие условия необходимы для применения метода поразрядной сортировки?
14. В чем состоит смысл метода поразрядной сортировки массивов?
15. Какие структуры данных необходимы для реализации метода поразрядной сортировки?
16. Приведите практический пример использования поразрядной сортировки.
17. Какие шаги необходимы для реализации метода поразрядной сортировки?
18. Что можно сказать об эффективности метода поразрядной сортировки?
19. Какие достоинства и недостатки имеет поразрядная сортировка?
20. Как программно выполняется поразрядная сортировка?
Тема 4. Поиск с использованием хеш-функций
Основные понятия
Пусть имеется набор из n элементов а1, а2, а3,..., аn с некоторыми ключами (как и раньше, для простоты будем считать, что сам элемент совпадает с его ключом). Требуется этот набор организовать в виде некоторой структуры данных с возможностью многократного поиска в нем элементов с заданным ключом. Эта задача может решаться различными способами:
· если набор элементов никак не упорядочен, то поиск выполняется прямым сравнением всех элементов в массиве или списке с трудоемкостью O(n)
· если элементы упорядочены в массиве или в дереве поиска, поиск более эффективно выполняется как двоичный, с трудоемкостью О(log 2 n)
Возникает вопрос: существуют ли еще более эффективные методы поиска? Оказывается, при выполнении некоторых дополнительных условий можно организовать исходный набор ключей в виде специальной структуры данных, называемой хеш-таблицей, поиск в которой ЛЮБОГО элемента в идеале выполняется за ОДНО сравнение и НЕ зависит от размерности входного набора. Другими словами, трудоемкость такого метода поиска, называемого хеш-поиском, пропорциональна О(1), что является абсолютным рекордом!
Метод хеш-поиска заключается в следующем. Исходные элементы а1, а2, а3,..., а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
В результате для этих четырех строковых ключей получаем следующую хеш-таблицу:
| индекс | ||||||||||
| ключ | AND | VAR | END | NIL |
Поиск в этой таблице некоторого ключа выполняется очень просто: находится целочисленный эквивалент строкового ключа, вычисляется значение хеш-функции и сравнивается содержимое полученной ячейки с заданным ключом. Например, h (VAR) = 4, сравниваем содержимое ячейки 4 с ключом VAR, фиксируем совпадение и завершаем поиск с признаком успеха.
Приведенные выше примеры носят несколько искусственный характер, поскольку они описывают идеальный случай, когда хеш-функция для всех различных ключей дает РАЗЛИЧНЫЕ значения индексов в массиве. В этом случае каждый ключ имеет свое уникальное расположение в массиве, не конфликтуя с другими ключами. Подобная ситуация возможна, если исходный набор ключей известен заранее и после построения хеш-таблицы не изменяется, т.е. ключи НЕ добавляются и НЕ удаляются из хеш-таблицы. В этом случае за счет подбора хеш-функции и, возможно, небольшого изменения самих ключей можно построить бесконфликтную хеш-таблицу. Важным практическим примером такой ситуации является построение таблицы ключевых слов в программах-трансляторах с языков программирования. Здесь набор ключевых слов является постоянным, изменяясь только при изменении версии транслятора, а с другой стороны, обработка транслятором входного текста на языке программирования требует многократного и очень быстрого распознавания в этом тексте ключевых слов языка.
К сожалению, идеальный случай возможен весьма редко, и ограничивать применение хеш-поиска только данным случаем было бы неразумно, учитывая выдающиеся потенциальные скоростные возможности метода. Поэтому были предложены различные усовершенствования хеш-поиска, существенно расширившие область его использования. Эти усовершенствования так или иначе связаны с обработкой конфликтных ситуаций, когда два РАЗНЫХ ключа претендуют на ОДНО и то же место в хеш-таблице, т.е. хеш-функция дает для этих разных ключей аi и ак одно и то же значение:
h (аi) = h (ак) = j
Например, в приведенном выше примере со строковыми ключами простая перестановка символов в ключе приводит к конфликту:
h (VAR) = h (RAV) = h (AVR) = (233 mod 10) + 1 = 4
Для разрешения конфликтов были предложены разные методы, которые можно сгруппировать в две основные группы – открытое хеширование и внутреннее хеширование (необходимо отметить, что данная терминология не является общепринятой и допускает разночтения, поэтому в первую очередь надо обращать внимание на сущность метода разрешения конфликтов).