С физической точки зрения таблица представляет собой вектор, элементами которого являются записи. Характерной логической особенностью таблиц, которая определяет их отдельное рассмотрение, является то, что доступ к элементам таблицы производится не по номеру (индексу), а по ключу - по значению одного из свойств объекта, описываемого элементом таблицы. Ключ - это свойство, идентифицирующее данную запись во множестве однотипных записей. Как правило, к ключу предъявляется требование уникальности в данной таблице. Ключ может включаться в состав записи и быть одним из ее полей, но может и не включаться в запись, а вычисляться по положению записи. Таблица может иметь один или несколько ключей.
Основной операцией при работе с таблицами является операция доступа к записи по ключу. Она реализуется процедурой поиска. Поскольку поиск может быть значительно более эффективным в таблицах, упорядоченных по значениям ключей, довольно часто над таблицами необходимо выполнять операции сортировки. Эти операции рассматриваются в следующих разделах.
Объективным критерием, позволяющим оценить эффективность того или иного алгоритма, является, так называемый, порядок алгоритма. Порядком алгоритма называется функция O(N), позволяющая оценить зависимость времени выполнения алгоритма от объема перерабатываемых данных (N - количество элементов в массиве или таблице). Эффективность алгоритма тем выше, чем меньше время его выполнения зависит от объема данных. Большинство алгоритмов с точки зрения порядка сводятся к трем основным типам:
- степенные - O(Na);
- линейные - O(N);
- логарифмические - O(loga(N)).
Эффективность степенных алгоритмов обычно считается плохой, линейных - удовлетворительной, логарифмических - хорошей.
В последующем изложении все описания алгоритмов даны для работы с таблицей, состоящей из записей R[1], R[2], ..., R[N] с ключами K[1], K[2], ..., K[N]. Во всех случаях N – количество элементов таблицы.
1. Операции логического уровня над таблицами. Поиск
1.1. Последовательный или линейный поиск
Простейшим методом поиска элемента, находящегося в неупорядоченном наборе данных, по значению его ключа является последовательный просмотр каждого элемента набора, который продолжается до тех пор, пока не будет найден желаемый элемент. Если просмотрен весь набор, но элемент не найден - значит, искомый ключ отсутствует в наборе.
Для последовательного поиска в среднем требуется (N+1)/2 сравнений. Таким образом, порядок алгоритма - линейный - O(N).
1.2. Бинарный поиск (дихотомический, двоичный)
Записи в таблицу заносятся в лексикографическом (символьные ключи) или численно (числовые ключи) возрастающем порядке. Поиск отдельной записи с определенным значением ключа происходит по следующему алгоритму. Сначала приближенно определяется запись в середине таблицы и анализируется значение ее ключа. Если оно слишком велико, то анализируется значение ключа, соответствующего записи в середине первой половины таблицы, и указанная процедура повторяется в этой половине до тех пор, пока не будет найдена требуемая запись. Если значение ключа слишком мало, испытывается ключ, соответствующий записи в середине второй половины таблицы, и процедура повторяется в этой половине. Этот процесс продолжается до тех пор, пока не будет найден требуемый ключ или не станет пустым интервал, в котором осуществляется поиск.
Для того, чтобы найти нужную запись в таблице, в худшем случае требуется log2(N) сравнений.
2. Операции логического уровня над таблицами. Сортировка
Для самого общего случая сформулируем задачу сортировки таким образом: имеется некоторое неупорядоченное входное множество ключей и мы должны получить выходное множество тех же ключей, упорядоченных по возрастанию или убыванию в численном или лексикографическом порядке.
Из всех задач программирования сортировка, возможно, имеет самый богатый выбор алгоритмов решения. Вот некоторые факторы, которые влияют на выбор алгоритма (помимо порядка алгоритма).
1). Имеющийся ресурс памяти: должны ли входное и выходное множества располагаться в разных областях памяти или выходное множество может быть сформировано на месте входного. В последнем случае имеющаяся область памяти должна в ходе сортировки динамически перераспределяться между входным и выходным множествами; для одних алгоритмов это связано с большими затратами, для других - с меньшими.
2). Исходная упорядоченность входного множества: во входном множестве могут попадаться упорядоченные участки. В предельном случае входное множество может оказаться уже упорядоченным. Одни алгоритмы не учитывают исходной упорядоченности и требуют одного и того же времени для сортировки любого (в том числе и уже упорядоченного) множества данного объема, другие выполняются тем быстрее, чем лучше упорядоченность на входе.
3). Временные характеристики операций: при определении порядка алгоритма время выполнения считается обычно пропорциональным числу сравнений ключей. Однако, сравнение числовых ключей выполняется быстрее, чем строковых, операции пересылки, характерные для некоторых алгоритмов, выполняются тем быстрее, чем меньше объем записи, и т.п. В зависимости от характеристик записи таблицы может быть выбран алгоритм, обеспечивающий минимизацию числа тех или иных операций.
4). Сложность алгоритма. Простой алгоритм требует меньшего времени для его реализации и вероятность ошибки в реализации его меньше.
Разнообразие алгоритмов сортировки требует некоторой их классификации. Выбран один из применяемых для классификации подходов, ориентированный прежде всего на логические характеристики применяемых алгоритмов. Согласно этому подходу любой алгоритм сортировки использует одну из следующих четырех стратегий (или их комбинацию).
1). Стратегия выборки. Из входного множества выбирается следующий по критерию упорядоченности элемент и включается в выходное множество на место, следующее по номеру.
2). Стратегия включения. Из входного множества выбирается следующий по номеру элемент и включается в выходное множество на то место, которое он должен занимать в соответствии с критерием упорядоченности.
3). Стратегия распределения. Входное множество разбивается на ряд подмножеств (возможно, меньшего объема) и сортировка ведется внутри каждого такого подмножества.
4). Стратегия слияния. Выходное множество получается путем слияния маленьких упорядоченных подмножеств.
Далее приводится обзор (далеко не полный) методов сортировки, сгруппированных по стратегиям, применяемым в их алгоритмах.
2.1. Сортировки выборкой
СОРТИРОВКА ПРОСТОЙ ВЫБОРКОЙ. Данный метод реализует практически "дословно" сформулированную выше стратегию выборки.
ОБМЕННАЯ СОРТИРОВКА ПРОСТОЙ ВЫБОРКОЙ. Входное и выходное множество располагаются в одной и той же области памяти; выходное - в начале области, входное - в оставшейся ее части. В исходном состоянии входное множество занимает всю область, а выходное множество - пустое. По мере выполнения сортировки входное множество сужается, а выходное - расширяется.
ПУЗЫРЬКОВАЯ СОРТИРОВКА. Входное множество просматривается, при этом попарно сравниваются соседние элементы множества. Если порядок их следования не соответствует заданному критерию упорядоченности, то элементы меняются местами. В результате одного такого просмотра при сортировке по возрастанию элемент с самым большим значением ключа переместится ("всплывет") на последнее место в множестве. При следующем проходе на свое место "всплывет" второй по величине ключа элемент и т.д. Для постановки на свои места N элементов следует сделать N-1 проходов. Выходное множество, таким образом, формируется в конце сортируемой последовательности, при каждом следующем проходе его объем увеличивается на 1, а объем входного множества уменьшается на 1.
СОРТИРОВКА ШЕЛЛА. Модификация пузырьковой сортировки. Здесь выполняется сравнение ключей, отстоящих один от другого на некотором расстоянии d. Исходный размер d обычно выбирается соизмеримым с половиной общего размера сортируемой последовательности. Выполняется пузырьковая сортировка с интервалом сравнения d. Затем величина d уменьшается вдвое и вновь выполняется пузырьковая сортировка, далее d уменьшается еще вдвое и т.д. Последняя пузырьковая сортировка выполняется при d=1.
2.2. Сортировки включением
СОРТИРОВКА ПРОСТЫМИ ВСТАВКАМИ. Этот метод - "дословная" реализации стратегии включения. Порядок алгоритма сортировки простыми вставками - O(N^2), если учитывать только операции сравнения. Но сортировка требует еще и в среднем N2./4 перемещений, что делает ее в таком варианте значительно менее эффективной, чем сортировка выборкой.
ПУЗЫРЬКОВАЯ СОРТИРОВКА ВСТАВКАМИ. Входное и выходное множества находятся в одной последовательности, причем выходное - в начальной ее части. В исходном состоянии можно считать, что первый элемент последовательности уже принадлежит упорядоченному выходному множеству, остальная часть последовательности - неупорядоченное входное. Первый элемент входного множества примыкает к концу выходного множества. На каждом шаге сортировки происходит перераспределение последовательности: выходное множество увеличивается на один элемент, а входное - уменьшается. Это происходит за счет того, что первый элемент входного множества теперь считается последним элементом выходного. Затем выполняется просмотр выходного множества от конца к началу с перестановкой соседних элементов, которые не соответствуют критерию упорядоченности. Просмотр прекращается, когда прекращаются перестановки. Это приводит к тому, что последний элемент выходного множества "выплывает" на свое место в множестве.
СОРТИРОВКА УПОРЯДОЧЕННЫМ ДВОИЧНЫМ ДЕРЕВОМ. Алгоритм складывается из построения упорядоченного двоичного дерева и последующего его обхода. Если нет необходимости в построении всего линейного упорядоченного списка значений, то нет необходимости и в обходе дерева, в этом случае применяется поиск в упорядоченном двоичном дереве. Алгоритмы работы с упорядоченными двоичными деревьями рассмотрены в теме 6. Порядок алгоритма - O(N*log2N)), но в конкретных случаях все зависит от упорядоченности исходной последовательности, который влияет на степень сбалансированности дерева
2.3. Сортировки распределением
ПОРАЗРЯДНАЯ ЦИФРОВАЯ СОРТИРОВКА. Алгоритм требует представления ключей сортируемой последовательности в виде чисел в некоторой системе счисления P. Число проходов сортировка равно максимальному числу значащих цифр в числе - D. В каждом проходе анализируется значащая цифра в очередном разряде ключа, начиная с младшего разряда. Все ключи с одинаковым значением этой цифры объединяются в одну группу. Ключи в группе располагаются в порядке их поступления. После того, как вся исходная последовательность распределена по группам, группы располагаются в порядке возрастания связанных с группами цифр. Процесс повторяется для второй цифры и т.д., пока не будут исчерпаны значащие цифры в ключе. Основание системы счисления P может быть любым, в частном случае 2 или 10. Для системы счисления с основанием P требуется P групп.
БЫСТРАЯ СОРТИРОВКА ХОАРА. Данный алгоритм относится к распределительным и обеспечивает показатели эффективности O(N*log2(N)) даже при наихудшем исходном распределении.
Используются два индекса - i и j - с начальными значениями 1 и N соответственно. Ключ K[i] сравнивается с ключом K[j]. Если ключи удовлетворяют критерию упорядоченности, то индекс j уменьшается на 1 и производится следующее сравнение. Если ключи не удовлетворяют критерию, то записи R[i] и R[j] меняются местами. При этом индекс j фиксируется и начинает меняться индекс i (увеличиваться на 1 после каждого сравнения). После следующей перестановки фиксируется i и начинает изменяться j и т.д. Проход заканчивается, когда индексы i и j становятся равными. Запись, находящаяся на позиции встречи индексов, стоит на своем месте в последовательности. Эта запись делит последовательность на два подмножества. Все записи, расположенные слева от нее имеют ключи, меньшие чем ключ этой записи, все записи справа - большие. Тот же самый алгоритм применяется к левому подмножеству, а затем к правому. Записи подмножества распределяются по двум еще меньшим подмножествам и т.д., и т.д. Распределение заканчивается, когда полученное подмножество будет состоять из единственного элемента - такое подмножество уже является упорядоченным.
2.4. Сортировки слиянием
Алгоритмы сортировки слиянием, как правило, имеют порядок O(N*log2(N)), но отличаются от других алгоритмов большей сложностью и требуют большого числа пересылок. Алгоритмы слияния применяются в основном, как составная часть внешней сортировки. Здесь же для понимания принципа слияния приведен простейший алгоритм слияния в оперативной памяти.
СОРТИРОВКА ПОПАРНЫМ СЛИЯНИЕМ. Входное множество рассматривается, как последовательность подмножеств, каждое из которых состоит из единственного элемента и, следовательно, является уже упорядоченным. На первом проходе каждые два соседних одноэлементных множества сливаются в одно двухэлементное упорядоченное множество. На втором проходе двухэлементные множества сливаются в 4-элементные упорядоченные множества и т.д. В конце концов получается одно большое упорядоченное множество.
3. Прямой доступ и хеширование
В рассмотренных выше методах поиска число проб при поиске в лучшем случае было пропорционально log2(N). Естественно, возникает желание найти такой метод поиска, при котором число проб не зависело бы от размера таблицы, а в идеальном случае поиск сводился бы к одной пробе.
3.1. Таблицы прямого доступа
Простейшей организацией таблицы, обеспечивающей идеально быстрый поиск, является таблица прямого доступа. В такой таблице ключ является адресом записи в таблице или может быть преобразован в адрес, причем таким образом, что никакие два разных ключа не преобразуются в один и тот же адрес. При создании таблицы выделяется память для хранения всей таблицы и заполняется пустыми записями. Затем записи вносятся в таблицу - каждая на свое место, определяемое ее ключом. При поиске ключ используется как адрес и по этому адресу выбирается запись, если выбранная запись пустая, то записи с таким ключом вообще нет в таблице.
Таблицы прямого доступа эффективны в использовании, но область их применения весьма ограничена. Назовем пространством ключей множество всех теоретически возможных значений ключей записи. Назовем пространством записей множество тех слотов в памяти, которые мы выделяем для хранения таблицы. Таблицы прямого доступа применимы только для таких задач, в которых размер пространства записей может быть равен размеру пространства ключей. В большинстве реальных задач, однако, размер пространства записей много меньше, чем пространства ключей.
3.2. Таблицы со справочниками
Основная таблица содержит записи в произвольном порядке. В дополнение к основной строится справочная или индексная таблица, записи которой состоят всего из двух полей: ключа и адреса в основной таблице. Поиск по ключу производится в справочной таблице. Если справочная таблица является таблицей прямого доступа, то потери памяти на пустые записи уменьшаются. Однако, очевидно, что в случае ключа-фамилии справочная таблица нас не спасет. Поэтому, обычно справочные таблицы содержат только фактические ключи и к ним применяются методы сортировки и поиска, описанные выше. Для таблиц прямого доступа и для таблиц со справочниками нет необходимости хранить ключ в составе записи основной таблицы, так как ключ может быть восстановлен по адресу записи либо по справочнику.
3.3. Хешированные таблицы и функции хеширования
Поскольку память является одним из самых дорогостоящих ресурсов вычислительной системы, из соображений ее экономии целесообразно назначать размер пространства записей равным размеру фактического множества записей или превосходящим его незначительно. В этом случае мы должны иметь некоторую функцию, обеспечивающую отображение точки из пространства ключей в точку в пространстве записей, т.е., преобразование ключа в адрес записи: r = H(k), где - r адрес записи, k - ключ. Такая функция называется функцией хеширования (функция перемешивания, функция рандомизации).
При попытке отображения точек из некоторого широкого пространства в узкое неизбежны ситуации, когда разные точки в исходном пространстве отобразятся в одну и ту же точку в целевом пространстве. Ситуация, при которой разные ключи отображаются в один и тот же адрес записи, называется коллизией или переполнением, а такие ключи называются синонимами. Коллизии - основная проблема для хешированных таблиц.
Если функция H, преобразующая ключ в адрес, может порождать коллизии, то однозначной обратной функции: k = H`(r), позволяющей восстановить ключ по известному адресу, существовать не может. Поэтому ключ должен обязательно входить в состав записи хешированной таблицы как одно из ее полей.
К функции хеширования в общем случае предъявляются следующие требования:
- она должна обеспечивать равномерное распределение отображений фактических ключей по пространству записей;
- она должна порождать как можно меньше коллизий для данного фактического множества записей;
- она не должна отображать какую-либо связь между значениями ключей в связь между значениями адресов;
- она должна быть простой и быстрой для вычисления.
В книге Кнута [2] приведен почти исчерпывающий обзор и анализ применяемых на практике функций хеширования, мы ограничимся лишь перечислением некоторых наиболее простых: функция деления по модулю, функция середины квадрата, функция свертки, функция преобразования системы счисления.
3.3.1. Проблема коллизий в хешированных таблицах
Удачно подобранная функция хеширования может минимизировать число коллизий, но не может гарантировать их полного отсутствия. Ниже рассматриваются методы разрешения проблемы коллизий в хешированных таблицах.
ПОВТОРНОЕ ХЕШИРОВАНИЕ. Повторное хеширование предусматривает следующее: если при попытке записи в таблицу оказывается, что требуемое место в таблице уже занято, то значение записывается в ту же таблицу на какое-то другое место. Другое место определяется при помощи вторичной функции хеширования H2, аргументом которой в общем случае может быть и исходное значение ключа и результат предыдущего хеширования: r = H2(k,r`), где r` - адрес, полученный при предыдущем применении функции хеширования. Если полученный в результате применения функции H2 адрес также оказывается занятым, функция H2 применяется повторно - до тех пор, пока не будет найдено свободное место.
ПАКЕТИРОВАНИЕ. Записи таблицы объединяются в пакеты фиксированного, относительно небольшого размера. Функция хеширования дает на выходе не адрес записи, а адрес пакета. После нахождения пакета, в пакете выполняется линейный поиск по ключу. Пакетирование позволяет сгладить нарушения равномерности распределения ключей по пространству пакетов и, следовательно, уменьшить число коллизий, но не может гарантированно их предотвратить. Пакеты также могут переполняться. Поэтому пакетирование применяется как дополнение к более радикальным методам.
ОБЩАЯ ОБЛАСТЬ ПЕРЕПОЛНЕНИЙ. Для таблицы выделяются две области памяти: основная область и область переполнений. Функция хеширования на выходе дает адрес записи или пакета в основной области. При вставке записи, если ее "законное" место в основной области уже занято, запись заносится на первое свободное место в области переполнения. При поиске, если "законное" место в основной занято записью с другим ключом, выполняется линейный поиск в области переполнения.
РАЗДЕЛЬНЫЕ ЦЕПОЧКИ ПЕРЕПОЛНЕНИЙ. В структуру каждой записи добавляется еще одно поле - указатель на следующую запись. Через эти указатели записи с ключами-синонимами связываются в линейный список, начало которого находится в основной таблице, а продолжение - вне ее. При вставке записи в таблицу по функции хеширования вычисляется адрес записи (или пакета) в основной таблице. Если это место в основной таблице свободно, то запись заносится в основную таблицу. Если же место в основной таблице занято, то запись располагается вне ее. Память для такой записи с ключом-синонимом может выделяться либо динамически для каждой новой записи, либо для синонима назначается элемент из заранее выделенной области переполнения. После размещения записи-синонима поле указателя из записи основной таблицы переносится в поле указателя синонима, а на его место в записи основной таблицы записывается указатель на только что размещенный синоним.
