Характеристики производительности быстрой сортировки

 

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

 

Лемма 8: Быстрая сортировка в наихудшем случае выполняет примерно N²/2 операций сравнения.

 

В силу только что приведенного аргумента, число операций сравнения, выполненных при сортировке уже отсортированного файла, выражается как N+ (N- 1) + (N- 2) +... + 2 + 1 = (N + 1) N/ 2.

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

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

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

Член соответствует затратам на сортировку двух подфайлов; N суть затраты на проверку каждого элемента, для чего используется тот или иной разделяющий указатель. Уже известно, что это рекуррентное соотношение имеет решение

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

 

Лемма 9: Быстрая сортировка в среднем выполняет 2NlnN операций сравнения.

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

при =0. Член N + 1 учитывает затраты на выполнение операций сравнения разделяющего элемента с каждым из остальных элементов (два дополнительных в точке пересечения указателей); наличие остальных компонентов обусловлено тем фактом, что каждый элемент к может стать разделяющим элементом с вероятностью 1/k, после чего остаются файлы с произвольной организацией, имеющие размеры к — 1 и N — k.

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

Во-вторых, можно избавиться от суммы, если умножить обе части равенства на N и вычесть такую же формулу для N — 1

За счет такого упрощения рассматриваемое рекуррентное соотношение приобретает вид

В третьих, разделив обе части на N(N+ 1), получим рекуррентное соотношение, которое приобретает более компактную форму:

Это точное выражение почти равно сумме, которая легко аппроксимируется интегралом.

откуда вытекает объявленный ранее результат. Обратите внимание на то, что 2NlnN=1.39NlgN, так что среднее количество операций сравнения приблизительно лишь на 39 % больше, чем в самом лучшем случае.

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

 

Рис.30. Динамические характеристики быстрой сортировки на файлах различных типов

Сортировка слиянием

 

Семейство алгоритмов быстрой сортировки, рассмотренное в главе 5.8, основано на операции выборки: нахождение k-го минимальною элемента в файле. Мы убедились в том, что выполнение операции выборки аналогично делению файла на две части, на часть, содержащую все к наименьших элементов, и часть, содержащую N— к больших по значению элементов. В этой главе исследуется семейство алгоритмов сортировки, в основе которых лежит вспомогательный процесс, известный как слияние, т.е., объединение двух отсортированных файлов в один файл большего размера. Слияние является основой для простого алгоритма сортировки типа "разделяй и властвуй", а также для его двойника — алгоритма восходящей (снизу-вверх) сортировки слиянием, при этом оба из них достаточно просто реализуются[3].

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

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

Одним из наиболее привлекательных свойств сортировки слиянием является тот факт, что она сортирует файл, состоящий из N элементов, за время, пропорциональное NlogN, независимо от характера входных данных.

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

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

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

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

 

 

Двухпутевое слияние

 

Имея два упорядоченных входных файла, их можно объединить в один упорядоченный выходной файл просто отслеживая наименьший элемент в каждом файле и входя в цикл, в котором меньший из двух элементов, наименьших в своих файлах, переносится в выходной файл; процесс продолжается до тех пор, пока оба входных файла не будут исчерпаны. Мы ознакомимся с несколькими реализации этой базовой абстрактной операции в этом и следующем разделах. Время выполнения линейно зависит от количества элементов в выходном файле, если на каждую операцию поиска следующего наименьшего элемента в файле уходит одно и то же время, что как раз и имеет место в том случае, когда отсортированные файлы представлены структурой данных, которая поддерживает последовательный доступ с постоянным временем доступа, такой как связный список или массив. Эта процедура представляет собой двухпутевое слияние {two-way merging). Наиболее важным приложением многопутевого слияния является внешняя сортировка, которая подробно рассматривается в текущей главе[3].

Для начала предположим, что имеются два непересекающихся упорядоченных массива целых чисел a[0],...,a[N-l] и b[0],...,b[М-1], которые требуется слить в третий массив c[0],...,c[N+M-l]. Легко реализуемая очевидная стратегия заключается в том, чтобы последовательно выбирать для с наименьший оставшийся элемент из а и b, как показано в программе 16. Эта реализация отличается простотой, в то же время она обладает характеристиками, которые мы сейчас и рассмотрим.

Программа 16: Слияние

Чтобы объединить два упорядоченных массива, а и b в упорядоченный массив с, используется цикл for, который помещает элемент в массив с на каждой итерации. Если, а исчерпан, элемент берется из Ь; если исчерпан Ь, то элемент берется из а; если же элементы остаются и в том и в другом массиве, наименьший из оставшихся элементов в а и b переходит в с. Помимо неявного предположения об упорядоченности обоих массивов, эта реализация предполагает также, что массив с не пересекается (т.е., не перекрывается или совместно не использует памяти) а и b.

 

template <class Item>

void mergeAB (I tem c[], Item a[], int N,

Item b[], int M)

{

for (int i = 0, j = 0, k = 0; k < N+M; k++)

{

if (i = N) { c[k] = b[j++]; continue; }

if (j == M) { c[k] = a[i++]; continue; }

c[k] = (a[i] < b[j])? a[i++]: b[j++];

}

}

 

Во-первых, эта реализация предполагает, что массивы не пересекаются. В частности, если, а и b являются крупными массивами, то для размещения выходных данных необходим третий массив с (также крупный). Вместо того чтобы использовать дополнительное пространство памяти, пропорциональное размерам слитого файла, желательно иметь в своем распоряжении такой метод, чтобы с помощью операций обмена мы могли, например, объединить два упорядоченных файла а[1],...,а[m] и а[m+1],..,а[r] в один упорядоченный файл за счет соответствующего перемещения

элементов а[1],...,а[r] без использования больших объемов дополнительного пространства памяти. Здесь желательно на какое-то время остановиться и подумать о том, как можно все это сделать. На первый взгляд кажется, что у этой проблемы есть простое решение, однако на самом деле все известные до сих пор решения достаточно сложные, особенно если их сравнить с программой 16. И в самом деле, довольно трудно разработать алгоритм обменного слияния, т.е. в рамках пространства памяти, занимаемого входными файлами, который обладал бы лучшими характеристиками и который мог бы стать альтернативой обменной сортировке.

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

 

Лемма 10: Сортировка слиянием требует выполнения примерно NlgN операций сравнения для сортировки любого файла из N элементов.

 

В реализациях, каждое слияние типа (N/2) на (N/2) требует N сравнений (это значение будет для разных файлов отличаться на 1 или на 2, в зависимости от того, как используются служебные метки). Следовательно, общее количество сравнений при сортировке в полном объеме может быть описано стандартным сбалансированным рекуррентным соотношением: Такое рекуррентное соотноше- ние описывает также сумму меток узлов и длину внешнего пути дерева типа "разделяй и властвуй" с N узлами. Это утверждение нетрудно проверить, когда N является степенью числа 2 и доказать методом индукции для произвольного N.

 

Лемма 11: Сортировка слиянием использует дополнительное пространство, пропорциональное N.

 

Мы можем предпринять некоторые шаги, дабы уменьшить размеры используемого дополнительного пространства за счет существенного усложнения алгоритма. Сортировка слиянием также эффективна, если сортируемый файл организован как связный список. В этом случае указанное свойство сохраняется, однако для связей расходуется дополнительное пространство памяти. В случае массивов, можно выполнять обменное слияние, однако эта стратегия вряд ли оправдывается на практике.

 

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

 

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

 

Лемма 13: Потребность ресурсов со стороны сортировки слиянием не чувствительна по отношению к исходному порядку входного файла.

 

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

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

 

 

Поиск

 

Получение конкретного фрагмента или фрагментов информации из больших томов ранее сохраненных данных — основополагающая операция, называемая поиском, характерная для многих вычислительных задач. Как и в случае с алгоритмами сортировки и очередями конкретного приоритета, мы работаем с данными, разделенными на записи, или элементы, каждый из которых имеет ключ, используемый при поиске. Цель поиска — отыскание элементов с ключами, которые соответствуют заданному ключу поиска. Обычно, назначением поиска является получение доступа к информации внутри элемента (а не про- просто к ключу) с целью ее обработки[3].

Поиск используется повсеместно и связан с выполнением множества различных операций. Например, в банке требуется отслеживать информацию о счетах всех клиентов и выполнять поиск в этих записях для подведения баланса и выполнения банковских операций. На авиалинии необходимо отслеживать количество мест на каждом рейсе и выполнять поиск свободных мест, отказа в продаже билетов или внесения каких-либо изменений в списки пассажиров. Еще один пример — средство поиска в сетевом интерфейсе программы, которое отыскивает в сети все документы, содержащие заданное ключевое слово. Требования, предъявляемые к этим приложениям, в чем-то совпадают (и для банка, и для авиалинии требуются точность и надежность), а в чем-то различны (банковские данные имеют длительный срок хранения по сравнению с данными остальных упомянутых приложений); тем не менее, во всех случаях требуются эффективные алгоритмы поиска.

 

 

6.1 Поиск с использованием индексации по ключам

 

Предположим, что значения ключей – отдельные небольшие числа. В этом случае простейший алгоритм поиска основывается на сохранении элементов в массиве, индексированном по ключам. Код весьма прост: оператор new[ ] инициализирует все записи значением nullItem, затем мы вставляем (Insert) элемент со значением ключа k, просто сохраняя его в массиве st[k], и выполняем поиск (search) элемента со значением ключа k, отыскивая его в st[k]. Для удаления (remove) элемента со значением ключа k значение nullItem помещается в st[k]. Реализации операций выбора (select), сортировки (sort) и подсчета (count) в программе используют линейный просмотр массива с пропуском нулевых элементов[3].

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

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

Операция индексации, на которой основывается поиск с использованием индексации по ключам, совпадает с базовой операцией в методе сортировки с подсчетом индексированных ключей. Когда это возможно, следует выбирать метод поиска с использованием индексации по ключам, поскольку операции search и insert трудно реализовать эффективнее.

Если элементы вообще отсутствуют (имеются только ключи), можно использовать таблицу бит. В этом случае таблица символов называется таблицей существования k в наборе ключей таблиц. Например, на 32-разрядном компьютере этот метод можно было использовать для быстрого выяснения того, используется ли уже конкретный 4-значный номер телефонного коммутатора, используя таблицу на 313 слов.

Лемма 13: Если значения ключей — положительные целые числа меньшие М, и элементы имеют различные ключи, то тип данных таблицы символов может быть реализован по­средством индексированных по ключам массивов элементов так, чтобы для выполнения операций insert, search и rеmovе требовалось постоянное время; время для выполнения операций initialize, select и sort: пропорционально M всегда, когда любая из операций вы­полняется по отношению к таблице, состоящей из N-элементов.

Это свойство становится очевидным после ознакомления с кодом. Обратите внима­ние, что на ключи накладывается условие N < М.

Программа 17 не обрабатывает дублированные ключи и в ней предполагается, что значения ключей лежат в пределах между 0 и М-1. Для хранения любых элементов с одинаковыми ключами можно было бы использовать связные списки, а перед использованием ключей в качестве индек­сов можно было бы выполнить их простые преобразования. Пока будем предполагать, что старым элементом со значением ключа, равным ключу вставляемого элемента, можно молча пренебречь или же считать это условием ошибки.

Программа 17: Таблица символов, основывающаяся на индексированном по ключам массиве.

 

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

 

 

Template <class Item, class Key>

class ST

{

private:

Item nullItem, *st;

Int M;

public:

ST(int maxN)

{ M = nullItem.key(); st = new Item(M); }

int count

{ int N = 0;

for (int i = 0; i < M; i++)

if (! st[i].null()) N++;

return N;

}

void insert(Item x)

{ st [x.key() ] = x; }

Item search (Key v)

{return st[v]; }

void remove (Item x)

{ st [x.key() ] = nullItem; }

Item select(int k)

{ for (int I = 0; i < M; i++)

if (! st[i].null())

if (k-- == 0) return st[i];

return nullItem;

void show (ostream & os)

{ for int I = 0; i < M; i++}

if (!st[i].null ()) st[i].show(os); }

 

Реализация операции countв программе 17 — пример "ленивого" подхода, когда действия выполняются только при вызове функции count. Альтернативный ("энергич­ный") подход заключается в поддержке локальной переменной счетчика непустых по­зиций таблицы с увеличением значения переменной, когда вставка (insert) выполняется в позицию таблицы, содержащую nullItem, и с уменьшением значения счетчика, если удаление (remove) выполняется по отношению к позиции таблицы, не содержащей. "Ленивый" подход предпочтительнее, если операция count используется редко (или вообще не используется), а количество возможных зна­чений ключей мало; "энергичный" подход предпочтительнее, если операция count ис­пользуется часто или если количество возможных значений ключей очень велико. Для подпрограммы библиотеки общего назначения "энергичный" подход предпочтительней, поскольку он обеспечивает оптимальную производительность для наихудшего случая при небольшом постоянном коэффициенте увеличения затрат на выполнение операций insert и remove. Для внутреннего цикла в приложении с очень большим количеством опе­раций Item и remove, но незначительным количеством операций count"ленивый" под­ход оказывается предпочтительней, поскольку обеспечивает наиболее быструю реали­зацию часто выполняемых операций. Как мы уже неоднократно убеждались, подобная дилемма типична для разработки АТД, которые должны поддерживать различные на­боры операций.

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

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

Последовательный поиск

 

В общем случае, когда значения ключей относятся к слишком большому диапазону, чтобы их можно было использовать в качестве индексов, один из простых подходов к реализации таблиц символов — последовательное сохранение элементов в массиве в упорядоченном виде. Когда требуется вставить новый элемент, мы вставляем его в мас­сив, перемещая большие элементы на одну позицию, как это делалось для сортировки вставками; когда необходимо выполнить поиск, массив просматривается последователь­но. Поскольку массив упорядочен, при встрече ключа, значение которого больше ис­комого, можно сделать вывод о неудаче поиска. Более того, благодаря упорядочению массива, реализация операций select и sort не представляет сложности. Программа 17 содержит реализацию таблицы символов, которая основывается на этом подходе[3].

Программа 18: Таблица символов (упорядоченная) с использованием массива

 

Подобно программе 17, в этой реализации используется массив элементов, но для нее не обязательно, чтобы ключи были небольшими целыми числами. Поддержание упорядоченности массива обеспечивается тем, что при вставке нового элемента большие элементы смещаются с целью освобождения места, как это делается при сортировке вставками. В этом случае функция search может выполнять в массиве поиск элемента с указанным ключом, возвращая значение nullItem при обнаруже­нии элемента с большим ключом. Реализация функций select и sort тривиальны, а реализация функции remove оставляется на самостоятельную проработку.

 

Template <class Item, class Key>

class ST

{

private:

Item nullItem, *st;

Int N;

public:

ST(int maxN)

{ st = new Item[maxN+1]; N = 0; }

int count()

(return N;)

void insert(Item x)

{ int I = N++; Key v = x.key ();

While (I > 0 && v < st[i-1].key() }

(st[i] = st[i-1]; i--;)

St[i] = x;

}

Item search(Key v)

{

For (int I = 0; I < N; i++)

If (! (st[i].key () <v)) break;

If (v == st[i].key()) return st[i];

Return nullItem;

}

Item select (int k)

(return st[k];)

Void show (ostream & os)

{ int I = 0;

While (I < N) st [i++].show(os); }

};

 

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

Другой подход связан с созданием реализации, в которой размещение элементов в массиве по порядку не является обязательным. При вставке новый элемент поме­щается в конец массива; во время поиска массив просматривается последовательно.

Этот подход характеризуется тем, что операция insertвыполняется быстро, а опера­ции selectиsortтребуют значительно большего объема работы. Уда­ление {remove) элемента с указанным ключом можно выполнить, отыскав его, а затем переместив последний элемент массива в позицию удаляемого элемента и уменьшив раз­мер массива на 1; удаление всех элементов с заданным ключом реализуется путем повто­рения этой операции. Если доступен дескриптор, предоставляющий индекс элемента в массиве, поиск не требуется, и операция removeвыполняется за постоянное время.

Еще одна простая реализация таблицы символов — использование связного списка. В этом случае можно также хранить список в упорядоченном виде с целью урощения поддержки операции sort либо оставить его неупорядоченным для ускорения операции insert. Программа 19 демонстрирует второй подход. Как обычно, преимущество при­менения связных списков по сравнению с массивами состоит в том, что вовсе не обя­зательно заранее точно определять максимальный размер таблицы, а недостаток — в необходимости расхода дополнительного объема памяти (под ссылки) и невозможнос­ти эффективной поддержки операции select.

Программа 19: Таблица символов (неупорядоченная) с использованием связного списка

 

В этой реализации операций consrtuct, count, searchиinsert используется односвяз­ный список, каждый узел которого содержит элемент с ключом и ссылкой. Функция insert помещает новый элемент в начало списка и выполняется за постоянное вре­мя. Функция-член search использует приватную рекурсивную функцию searchR для просмотра списка.

Поскольку список не упорядочен, реализации операций sortиselectопущены.

 

#include <stdlib.h>

template <class Item, class Key>

class ST

{

private:

Item nullltem;

struct node { Item item; node* next;

node (Item x, node* t)

{ item = x;

next = t; }

};

typedef node *link;

int N;

link head;

Item searchR (link t, Key v)

{ if (t == 0) return nullltem;

if (t-> item.key() == v) return t-> item;

return searchR(t-> next, v);

}

public:

ST(int maxN)

{ head = 0; N = 0; }

int count ()

{ return N; }

Item search (Key v)

{ return searchR(head, v); }

void insert (Item x)

{ head = new node(x, head);

N++; }

};

 

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

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

В приложении, где функция sortтребуется часто, нужно было бы выбрать упорядоченное представление (с использованием массива или списка), поскольку такая структура таблицы делает реа­лизацию функции sort тривиальной, в отличие от необходимости полной реализации сортировки. В приложении, в котором заведомо потребуется частое выполнение опе­рации select, нужно было бы использовать представление с использованием упорядочен­ного массива, поскольку при такой структуре таблицы затрачиваемое на выполнение упомянутой операции время постоянно. И напротив, время выполнения операции select в связном списке линейно зависит от количества элементов, даже если список упоря­дочен.

Чтобы подробнее проанализировать последовательный поиск произвольных ключей, начнем с рассмотрения затрат на вставку новых ключей и отдельно рассмотрим случаи успешногоинеуспешного поиска. Первый часто называют попаданием при поиске, а вто­рой — промахом при поиске. Нас интересуют затраты как при попаданиях, так и при про­махах в среднем и худшем случаях. Строго говоря, в реализации с использованием упо­рядоченного массива (см. программу 18) для каждого исследуемого элемента используются две операции сравнения (== и <).

Лемма 14: При последовательном поиске в таблице символов с N элементами для вы­явления попаданий при поиске требуется выполнение около N/2 сравнений (в среднем).

Лемма 15: При последовательном поиске в таблице символов, содержащей N неупоря­доченных элементов, используется постоянное количество шагов для выполнения вставок и N сравнений для выявления промахов при поиске (всегда).

 

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

Лемма 16: Для вставки, обнаружения попаданий и промахов при последовательном по­иске в таблице символов, содержащей N упорядоченных элементов, требуется выполне­ние приблизительно N/2 операций сравнения (в среднем).

 

Построение упорядоченных таблиц путем последовательной вставки, по существу, эквивалентно выполнению алгоритма сортировки вставками. Общее время, необходимое для построения таблицы, связано квадратичной зависимостью с количеством элементов, поэтому вряд ли стоит использовать этот ме­тод для построения больших таблиц. Однако при выполнении огромного количества операций searchв небольшой таблице поддержка упорядоченности элементов вполне оправдана, поскольку в соответствии с леммами 14 и 15 этот подход может в два раза уменьшить время, затрачиваемое на обнаружение промахов при поиске. Если элемен­ты с дублированными ключами не должны храниться в таблице, дополнительные зат­раты на поддержку упорядоченности таблицы не столь велики, как может казаться, поскольку вставка выполняется только после обнаружения промаха при поиске и, сле­довательно, время, затрачиваемое на вставку, пропорционально времени, затрачивае­мому на поиск. С другой стороны, если элементы с дублированными ключами могут храниться в таблице, при использовании неупорядоченной таблицы время выполнения операции insert может оставаться постоянным. Использование неупорядоченной табли­цы предпочтительнее для приложений, в которых выполняется огромное количество операций insert при сравнительно небольшом числе операций search.

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

 

6.3 Бинарный поиск

 

В реализации последовательного поиска на базе массивов общее время поиска на больших наборах элементов можно значительно уменьшить, исполь­зуя процедуру поиска, основанную на стандартном подходе "разделяй и властвуй". Для этого набор элементов необходимо разделить на две части, определить, к какой из двух частей при­надлежит ключ поиска, а затем сосредоточить свои усилия именно на этой части. Рациональный способ разделения наборов элементов на части состоит в поддержке элементов в отсортированном виде с последующим использованием индексов в отсорти­рованном массиве для определения части массива, над которой будет выполняться дальнейшая работа[3].

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

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