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

Программа 11.2. Нечетно-четное слияние Бэтчера (рекурсивная версия)

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

  template <class Item>
  void merge(Item a[], int l, int m, int r)
 { if (r == l+1) compexch(a[l], a[r]);
   if (r < l+2) return;
   unshuffle(a, l, r);
   merge(a, l, (l+m)/2, m);
   merge(a, m+1, (m+1+r)/2, r);
   shuffle(a, l, r);
   for (int i = l+1; i < r; i += 2)
  compexch(a[i], a[i+1]);
 }
   

Чтобы слить ключи A G I N O R S T с ключами A E E L M P X Y, мы начинаем с выполнения операции обратного тасования, порождающей две независимые задачи слияния наполовину меньших массивов (показаны во второй строке): теперь нужно слить A I O S с A E M X (в первой половине массива) и G N R T с E L P Y (во второй половине массива). После рекурсивного решения этих подзадач мы тасуем результирующие массивы, (показаны в предпоследней строке) и завершаем сортировку выполнением операций сравнения-обмена E с A, G с E, L с I, N с M, P с O, R с S и T с X.

Почему данный метод сортирует все возможные перестановки входных данных? Ответ на этот вопрос далеко не очевиден; классическое доказательство этого факта является косвенным и зависящим от общих характеристик неадаптивных программ сортировки.

На самом деле нет необходимости тасовать данные. И действительно, программы 11.2 и 8.3 могут быть переделаны таким образом, чтобы получилась линейная сортирующая программа для любого N - для этого необходимо скорректировать реализации compexch и shuffle, чтобы они поддерживали индексы и косвенный доступ к данным (см. упражнение 11.12). Либо можно сделать так, чтобы программа генерировала последовательность команд сравнения-обмена, которую можно применить к исходному входному файлу (см. упражнение 11.13). Эти приемы можно использовать для любого неадаптивного метода сортировки, переупорядочивающего данные при помощи операций обмена, тасования или им подобных. Что касается слияния Бэтчера, то структура этого алгоритма настолько проста, что, как будет показано в разделе 11.2, для него можно непосредственно разработать восходящую реализацию.

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

Упражнения

11.1. Приведите результат тасования и обратного тасования ключей E A S Y Q U E S T I O N.

11.2. Обобщите программу 11.1 для реализации h-путевых тасования и обратного тасования. Обеспечьте работоспособность примененной стратегии для случая, если размер файла не кратен h.

11.3. Реализуйте операции тасования и обратного тасования без использования вспомогательного массива.

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

11.5. Покажите, как линейная программа, приведенная в тексте, сортирует каждую из шести перестановок чисел 1, 2 и 3.

11.6. Приведите пример линейной программы, которая выполняет сортировку четырех элементов.

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

11.8. Покажите, в стиле диаграммы на рис.11.2, как программа 11.2 выполняет слияние ключей A E Q S U Y E I N O S T.

11.9. Выполните упражнение 11.8 для ключей A E S Y E I N O Q S T U.

11.10. Выполните упражнение 11.8 для ключей 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0.

11.11. Эмпирически сравните время выполнения сортировки слиянием Бэтчера с временем выполнения стандартной нисходящей сортировки слиянием (программы 8.3 и 8.2) для N = 103, 104, 105 и 106 .

11.12. Приведите такие реализации функций compexch, shuffle и unshuffle, что программы 11.2 и 8.3 будут работать в режиме косвенной сортировки (см. ).

11.13. Приведите такие реализации функций compexch, shuffle и unshuffle, что программы 11.2 и 8.3 будут выводить для заданного N линейную программу сортировки N элементов. Для отслеживания значений индексов можно воспользоваться вспомогательным глобальным массивом.

11.14. Если переставить элементы второго сливаемого файла в обратном порядке, получится битоническая последовательность (см. определение в ). После изменения заключительного цикла программы 11.2 так, чтобы он начинался с l, а не с , как с помощью этого метода выполняется слияние ключей A E S Q U Y T S O N I E.

11.15. Докажите, что модификация программы 11.2, описанная в упражнении 11.14, способна отсортировать любую битоническую последовательность.

Сортирующие сети

Простейшей моделью для изучения неадаптивных алгоритмов сортировки является абстрактная машина, которая обращается к данным только с помощью операций сравнения-обмена. Такая машина называется сортирующей сетью (sorting network). Сортирующая сеть построена из простых неделимых модулей сравнения-обмена (compare-exchange module), или компараторов (comparator), соединенных между собой таким образом, что возможно выполнение полной сортировки общего вида.

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

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

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

Еще одним важным применением сортирующих сетей является использование их в качестве модели параллельных вычислений. Если два компаратора не используют для ввода данных одни и те же линии, то, очевидно, они могут работать одновременно. Например, сеть, изображенная на рис 11.4, показывает, что четыре элемента могут быть отсортированы за три параллельных шага. На первом шаге могут одновременно работать компаратор 0-1 и компаратор 2-3, после чего на втором шаге могут одновременно работать компаратор 0-2 и компаратор 1-3, и на третьем шаге компаратор 2-3 завершает сортировку. Для любой заданной сети компараторы нетрудно сгруппировать в последовательность параллельных каскадов (parallel stage), состоящих из компараторов, которые могут работать одновременно (см. упражнение 11.17). Для наибольшей эффективности параллельных вычислений нужно разрабатывать сети с минимально возможным числом параллельных каскадов.

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

Показанные на этом рисунке различные представления сетей на четыре (вверху), восемь (в центре) и 16 (внизу) линий демонстрируют рекурсивную структуру, на которой основаны сети. Слева показаны непосредственные представления построения сети размера N с помощью двух копий сетей размера N/2 (одна для линий с четными номерами, другая для линий с нечетными номерами) плюс каскад компараторов между линиями 1 и 2, 3 и 4, 5 и 6 и т.д. Справа показаны более простые сети, полученные из сетей, изображенных слева, путем группирования компараторов одинаковой длины. Такое группирование возможно потому, что компараторы на нечетных линиях можно перемещать независимо от компараторов на нечетных линиях.

Программа 11.3. Нечетно-четное слияние Бэтчера (нерекурсивная версия)

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

  template <class Item>
  void merge(Item a[], int l, int m, int r)
 { int N = r-l+1; // предполагается,
   // что N/2 равно m-l+1
   for (int k = N/2; k > 0; k /= 2)
  for (int j = k % (N/2); j+k < N; j += k+k)
    for (int i = 0; i < k; i++)
   compexch(a[l+j+i], a[l+j+i+k]);
 }
   

Для создания сливающей сети размера N мы воспользуемся двумя копиями сети размером показан пример выполнения такого слияния.

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

Программа 11.3 является восходящей реализацией слияния Бэтчера без тасования; она соответствует сетям, представленным на рис 11.5. Эта программа представляет собой компактный и элегантный обменный метод слияния, который, возможно, лучше считать альтернативным представлением сетей, хотя прямое доказательство того, что она правильно выполняет задачу слияния, интересно и само по себе. Одно такое доказательство будет рассмотрено в конце этого раздела.

На рис 11.7 показана нечетно-четная сортирующая сеть Бэтчера, построенная на основе сетей слияния, которые показаны на рис 11.5, с помощью стандартного построения рекурсивной сортировки слиянием. Все построение дважды рекурсивно: один раз для сливающих сетей, другой - для сортирующих сетей. Они не оптимальны (мы вскоре рассмотрим оптимальные сети), но тем не менее они эффективны.

Данная сортирующая сеть на 32линии содержит две копии сетей на 16линий, четыре копии сетей на восемь линий и т.д. Просматривая эту структуру справа налево, мы как бы глядим на нее сверху вниз: сортирующая сеть на 32линии состоит из сливающей сети 16-и-16, за которой следуют две копии сортирующей сети на 16 линий (для верхней половины и для нижней половины). Каждая сеть на 16 линий состоит из сливающей сети 8-и-8, за которой следуют две копии сортирующей сети на 8 линий и т.д. Просматривая эту структуру слева направо, мы как бы глядим на нее снизу вверх: первый столбец компараторов создает упорядоченные файлы размером 2; далее идут сливающие сети 2-и-2, создающие отсортированные подфайлы размером 4; затем идут сливающие сети 4-и-4, создающие отсортированные подфайлы размером 8 и т.д.

Использование функции слияния из программы 11.3 в стандартной рекурсивной сортировке слиянием, представленной программой 8.3, дает компактный обменный метод сортировки, который является неадаптивным и использует O (N (lgN)2) операций сравнения-обмена. С другой стороны, из сортировки слиянием можно удалить рекурсию и непосредственно реализовать полную восходящую версию, как показано в программе 11.4. Как и в случае программы 11.3, эту программу легче понять, если рассматривать ее как альтернативное представление сети, показанной на рис 11.7.

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

Программа 11.4. Нечетно-четная сортировка Бэтчера (нерекурсивная версия)

Данная реализация нечетно-четной сортировки Бэтчера непосредственно соответствует представлению сети на рис 11.7. Она разбивается на фазы, индексируемые переменной p. Последняя фаза, где p равно N, является нечетно-четным слиянием Бэтчера. Предпоследняя фаза, где p равно N/2, является нечетно-четным слиянием с первым каскадом, в котором удалены компараторы, пересекающие N/2; третья с конца фаза, где p равно N/4, является нечетно-четным слиянием с двумя первыми каскадами, в котором удалены компараторы, пересекающие N/4, и т.п.

  template <class Item>
  void batchersort(Item a[], int l, int r)
 { int N = r-l+1;
   for (int p = 1; p < N; p += p)
  for (int k = p; k > 0; k /= 2)
    for (int j = k%p; j+k < N; j += (k+k))
   for (int i = 0; i < N-j-k; i++)
     if ((j+i)/(p+p) == (j+i+k)/(p+p))
    compexch(a[l+j+i], a[l+j+i+k]);
 }
   

Как это часто бывает с методами " разделяй и властвуй " , в случае, когда N не равно степени 2, имеется две возможности (см. упражнения 11.24 и 11.21). Можно поделить файл пополам (нисходящий вариант), либо поделить по максимальной степени 2, меньшей N (восходящий вариант). Последний вариант для сортирующих сетей несколько удобнее, поскольку он эквивалентен построению полной сети для минимальной степени 2, большей или равной N, с последующим использованием только первых N линий и компараторов, подключенных к этим линиям обоими концами. Доказать, что это построение корректно, довольно просто. Предположим, что на неиспользуемые линии поданы сигнальные ключи, которые больше любых других ключей сети. Тогда компараторы на этих линиях никогда не производят операций обмена, и их можно спокойно удалить. Вообще-то можно воспользоваться любым набором из N смежных линий большей сети: достаточно считать, что на игнорируемых линиях в верхней части имеются сигнальные ключи с малыми значениями, а на игнорируемых линиях в нижней части - сигнальные ключи с большими значениями. Все эти сети содержат порядка N (lgN)2 / 4 компараторов.

Теория сортирующих сетей развивалась достаточно интересно (см. раздел ссылок). Задача построения сетей с минимально возможным числом компараторов была поставлена Бозе (Bose) еще до 1960 г., впоследствии она получила название задачи Бозе-Нельсона (Bose-Nelson). Сети Бэтчера были первым достаточно приемлемым решением этой задачи, и некоторое время даже считалось, что сети Бэтчера оптимальны. Сливающие сети Бэтчера оптимальны, и поэтому любая сортирующая сеть с существенно меньшим числом компараторов может быть построена только с помощью подхода, отличного от рекурсивной сортировки слиянием. Задача нахождения оптимальных сортирующих сетей не исследовалась до 1983 г., когда Аджтай (Ajtai), Комлос (Komlos) и Шемереди (Szemeredy) доказали существование сетей с O (Nlog N) компараторами. Однако сети AKS (Ajtai-Kolmos-Szemeredy) - это всего лишь математические построения, не имеющие практического применения, и сети Бэтчера все еще входят в число наиболее подходящих практических методов.

Связь между идеальным тасованием и сетями Бэтчера позволяет удивительным образом завершить рассмотрение сортирующих сетей анализом еще одной версии рассматриваемого алгоритма. Если перетасовать линии нечетно-четного слияния Бэтчера, то получатся сети, в которых все компараторы соединяют смежные линии. На рис 11.8 показана сеть, которая соответствует реализации тасования, приведенной в программе 11.2. Такое переплетение соединений иногда называется сеть-бабочка (butterfly network). На этом рисунке дано еще одно представление той же линейной программы, обеспечивающее еще более однотипное переплетение; в нем используются только операции полного тасования.

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

На рис 11.9 показана еще одна интерпретация рассматриваемого метода, которая вскрывает его базовую структуру.

Начав с двух отсортированных файлов в первом ряду, мы сливаем их с помощью повторения следующей операции:разбиваем каждый ряд на две равные части, чередуем полученные половины (слева) и выполняем операции сравнения-обмена над смежными по вертикали элементами из разных рядов (справа). Сначала было 16 столбцов и 1 ряд, затем 8 столбцов и 2 ряда, 4 столбца и 4 ряда, 2 столбца и 8 рядов и, наконец, 16 рядов и один столбец, который к этому моменту отсортирован.

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

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

На рис 11.11 показаны динамические характеристики как восходящего метода, так и версии нечетно-четного слияния Бэтчера с полным тасованием.

Тасование - это важная абстракция, описывающая движение данных в алгоритмах " разделяй и властвуй " , и она возникает в различных задачах, не связанных с сортировкой. Например, если квадратная матрица размером 2n х 2n хранится в памяти по строкам, то n идеальных тасований транспонируют эту матрицу (преобразуют в упорядоченную по столбцам). Более важные примеры - быстрые преобразования Фурье и вычисление полиномов (см. часть 8). Каждая из этих задач может быть решена при помощи циклической машины идеального тасования, подобной показанной на рис 11.10, но с более мощными процессорами. Можно даже обдумать вариант с использованием универсальных процессоров, способных выполнять прямое и обратное тасование (некоторые из машин этого типа были даже реально построены); к таким параллельным машинам мы еще вернемся в разделе 11.5.

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

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

Упражнения

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

11.17. Напишите программу для подсчета количества параллельных шагов, необходимых для выполнения любой линейной программы. Совет: Воспользуйтесь следующей стратегией присвоения меток. Пометьте входные линии как принадлежащие к каскаду 0, затем для каждого компаратора выполните следующие действия: пометьте обе выходные линии как входные для каскада i + 1, если метка одной из входных линий равна i, а метка другой линии не больше чем i.

11.18. Сравните время выполнения программы 11.4 с временем выполнения программы 8.3 для случайно упорядоченных ключей при N = 10³, 10⁴, 10⁵ и 10⁶.

11.19. Начертите сеть Бэтчера для выполнения слияния 10-и-11.

11.20. Докажите существование зависимости между рекурсивным тасованием и обратным тасованием (см. рис 11.8).

11.21. Из изложенного в тексте следует, что на рис 11.7 неявно представлено 11 сетей для упорядочения 21 элемента. Начертите ту из них, которая содержит минимальное количество компараторов.

11.22. Приведите количество компараторов в нечетно-четных сортирующих сетях Бэтчера для $$$2\leq N \leq 32$$$ , если при N, не равном степени 2, сети строятся из первых N линий сети, построенной для наименьшей степени 2, большей N.

11.23. Выведите точное выражение для количества компараторов, используемых в нечетно-четных сетях сортировки Бэтчера при N = 2n . Совет: Сверьте свой ответ с рис 11.7, на котором показано, что для N, равного 2, 4, 8, 16 и 32, в сетях имеется, соответственно, 1, 3, 9, 25 и 65 компараторов.

11.24. Постройте сортирующую сеть для упорядочения 21 элемента, используя нисходящий рекурсивный стиль, когда сеть размером N строится как композиция сетей размерами $$$\lfloor N/2\rfloor$$$ и $$$\lceil N/2\rceil$$$ , за которыми следует сливающая сеть. (Для завершающей части сети воспользуйтесь решением упражнения 11.19.)

11.25. С помощью рекуррентных соотношений подсчитайте количество компараторов в сортирующих сетях, построенных, как описано в упражнении 11.24, для $$$2\leq N \leq 32$$$. Сравните полученные результаты с результатами из упражнения 11.22.

11.26. Найдите 16-линейную сортирующую сеть, которая использует меньшее число компараторов, чем сеть Бэтчера.

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

11.28. Начертите сортирующие сети, соответствующие сортировке Шелла с последовательностью шагов Пратта () для N = 32.

11.29. Приведите таблицу, содержащую количество компараторов в сетях, описанных в упражнении 11.28, и количество компараторов в сетях Бэтчера для N = 16, 32, 64, 128 и 256.

11.30. Создайте сортирующие сети, способные выполнять сортировку 3-упорядочен-ных и 4-упорядоченных файлов из N элементов.

11.31. Воспользуйтесь сетями из упражнения 11.30 для разработки схемы, подобной алгоритму Пратта, с использованием множителей 3 и 4. Начертите полученную сеть для N = 32 и решите упражнение 11.29 применительно к этой сети.

11.32. Начертите версию нечетно-четной сортирующей сети Бэтчера для N = 16, в которой между каскадами независимых компараторов, соединяющих смежные линии, выполняются идеальные тасования (четырьмя последними каскадами этой сети должны быть каскады из сети слияния в нижней части рис.11.8).

11.33. Напишите программу слияния для машины, которая изображена на рис 11.10, соблюдая следующие соглашения. Каждая инструкция является последовательностью из 15 битов, где i-й бит, при $$$1\leq i \leq 15$$$, показывает (если он равен 1), что процессор i и процессор i - 1 должны выполнить операцию сравнения-обмена. Программа представляет собой последовательность инструкций; между каждыми двумя инструкциями машина выполняет идеальное тасование.

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

Внешняя сортировка

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

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

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

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

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

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

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

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

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

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

Простейшая стратегия сортировки-слияния, называемая сбалансированное многопутевое слияние (balanced multiway merging), показана на рис 11.12. Этот метод состоит из прохода, выполняющего начальное распределение (initial distribution), за которым следуют несколько проходов многопутевого слияния (multiway merging pass).

Во время начального прохода входные данные распределяются по внешним устройствам P, P + 1, ..., 2P - 1 в виде отсортированных блоков данных по M записей (за исключением, возможно, последнего блока, который меньше остальных, если N не кратно M). Такое распределение нетрудно выполнить: мы считываем первые M записей с входного устройства, сортируем их и записываем упорядоченный блок на устройство P ; затем считываем с входного устройства следующие M записей, сортируем их и записываем упорядоченный блок на устройство P + 1 и т.д. Если мы достигли устройства 2P - 1, и еще есть необработанные данные (т.е. если N > PM), мы записываем на устройство P второй отсортированный блок, затем второй блок на устройство P + 1 и т.д., до исчерпания всех входных данных. По завершении распределения количество отсортированных блоков, размещенных на каждом устройстве, равно N/PM, округленному до ближайшего целого числа в ту или другую сторону. Если N кратно M, то размеры всех блоков равны M (если это не так, то размер M имеют все блоки, за исключением последнего). Для небольших N количество блоков может оказаться меньше P, тогда одно или несколько устройств будут пустыми.

На первом проходе многопутевого слияния устройства в интервале от P до 2P - 1 рассматриваются как входные, а устройства в интервале от 0 до P - 1 как выходные.

На проходе начального распределения мы выбираем из входных данных элементы A S O, сортируем их и записываем упорядоченную последовательность A O S на первое выходное устройство. Далее мы выбираем из входных данных элементы R T I, сортируем их и записываем упорядоченную последовательность I R T на второе выходное устройство. Продолжая таким образом и циклически переключаясь между выходными устройствами, мы окончательно получаем 15 отрезков: по пять на каждом выходном устройстве. На первом этапе слияния сливаются отрезки A O S, I R T и A G N, и получается последовательность A A G I N O R S T, которую мы записываем на первое выходное устройство, затем выполняется слияние вторых отрезков на входных устройствах, и получается последовательность D E G G I M N N R, которую мы записываем на второе выходное устройство и т.д.; теперь получилось сбалансированное распределение данных на трех устройствах. После еще двух проходов слияния сортировка завершается.

Мы выполняем P-путевое слияние блоков данных размером M, помещенных на входные устройства, и получаем отсортированные блоки данных размером PM, которые максимально сбалансированно размещаем на выходных устройствах. Сначала сливаются первые блоки с каждого входного устройства, а результат этого слияния записывается на устройство 0, затем сливаются вторые блоки с каждого входного устройства и записываются на устройство 1 и т.д. После использования устройства P - 1 вторые блоки данных записываются на устройство 0, затем на устройство 1 и т.д. Этот процесс продолжается до тех пор, пока все входные данные не будут исчерпаны. После распределения количество отсортированных блоков на каждом устройстве равно N/PM, округленному до ближайшего целого числа в ту или другую сторону. Если N кратно PM, то все блоки имеют размер PM, иначе последний блок меньше остальных. Если N не больше PM, то остается один отсортированный блок (на устройстве 0), и на этом сортировка заканчивается.

В противном случае мы повторяем этот процесс и выполняем второй проход многопутевого слияния, рассматривая устройства 0, 1, ..., P - 1 в качестве входных, а устройства P, P + 1, ..., 2P - 1 в качестве выходных. В результате P-путевого слияния отсортированных блоков размером PM, размещенных на входных устройствах, получаются блоки размером P2M, которые размещаются на выходных устройствах. Сортировка заканчивается по завершении второго прохода (результат на устройстве P), если N не больше P2M.

Продолжая таким образом и переключаясь между устройствами от 0 до P - 1 и устройствами от P до 2P - 1, каждое P-путевое слияние увеличивает размер блоков в P раз, пока в конечном итоге не получится один блок, на устройстве 0 или на устройстве P. Последнее слияние на каждом проходе может не быть полным P-путевым слиянием, если это не так, то процесс хорошо сбалансирован. Этот процесс проиллюстрирован на рис 11.13, где указаны только количество и относительные размеры отрезков. Оценку стоимости слияния можно получить, выполнив умножения, указанные в представленной на рисунке таблице, просуммировав результаты (без нижней строки) и поделив сумму на число первоначальных отрезков. Эти вычисления выражают затраты через количество проходов по данным.

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

Распределение отрезков в сбалансированном 3-путевом слиянии

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

Например, если нужно отсортировать 1 миллиард записей, используя шесть внешних устройств и оперативную память, позволяющую разместить 1 миллион записей, это можно сделать с помощью трехпутевой сортировки-слияния, выполнив всего восемь проходов по данным: один проход начального распределения и $$$\lceil \log_{3}{1000}\rceil =7$$$ проходов слияния. После начального распределения получаются отсортированные отрезки данных, содержащие по 1 миллиону записей, после первого слияния - по 3 миллиона записей, после второго слияния - по 9 миллионов записей, после третьего слияния - по 27 миллионов записей в каждом блоке и т.д. Можно подсчитать, что на сортировку файла уйдет в 9 раз больше времени, чем на его копирование.

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

Упражнения

11.35. В стиле примера, представленного на рис 11.12, покажите, как ключи E A S Y Q U E S T I O N W I T H P L E N T Y O F K E Y S сортируются с помощью 3-путе-вого сбалансированного слияния.

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

11.37. Как отразится на количестве проходов многопутевого слияния увеличение объема доступной оперативной памяти в 10 раз?

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

11.39. Пользуясь интерфейсом из упражнения 11.38, напишите программу обращения порядка записей в файле максимально допустимого в вашей системе размера.

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

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

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

11.43. Как отсортировать содержимое внешнего устройства, если недоступны любые другие внешние устройства (кроме оперативной памяти)?

11.44. Как отсортировать содержимое внешнего устройства, если доступно лишь еще одно устройство (а также оперативная память)?

Реализации сортировки-слияния

Общая стратегия сортировки-слияния, описанная в разделе 11.13, доказала свою эффективность на практике. В данном разделе мы рассмотрим два усовершенствования этой стратегии, позволяющих снизить затраты. Первое из них, метод выборки с замещением (replacement selection), оказывает на время выполнения тот же эффект, что и увеличение объема используемой оперативной памяти; следующий метод, полифазное слияние (polyphase merging), дает тот же эффект, что и увеличение числа используемых устройств.

В разделе 11.3 обсуждалось применение очереди с приоритетами для P-путевого слияния, но при этом было сказано, что P настолько мало, что повышение быстродействия очереди практически ничего не дает. Однако на этапе начального распределения можно воспользоваться быстрыми очередями с приоритетами, чтобы получить отсортированные отрезки, размеры которых больше объема оперативной памяти. Идея заключается в том, чтобы пропустить (неупорядоченные) входные данные через большую очередь с приоритетами - как и раньше, выбирая из очереди с приоритетами наименьший элемент и заменяя его следующим элементом из входных данных, с одним дополнительным условием: если новый элемент меньше, чем только что выбранный из очереди, то, поскольку он может и не стать частью текущего сортируемого блока, мы помечаем его как принадлежащий следующему блоку и считаем, что он больше всех остальных элементов текущего блока. Когда помеченный элемент доходит до вершины очереди с приоритетами, мы начинаем новый блок. Работа этого метода показана на рис 11.14.

Эта последовательность показывает, как из последовательности A S O R T I N G E X A M P L E можно получить два отрезка данных - A I N O R S T X и A E E G L M P - длиной соответственно 8 и 7, используя для этой цели сортирующее дерево размером 5.

Для случайно упорядоченных файлов практический результат применения выборки с замещением состоит в возможном уменьшении числа проходов на один: вместо того, чтобы начать с отсортированных отрезков с размером, примерно равным объему оперативной памяти, мы можем начать с отрезков в два раза большего размера. Для P = 2 такая стратегия экономит точно один проход слияния, для больших значений P эффект менее заметен. Однако мы знаем, что на практике сортировка случайно упорядоченных файлов встречается редко, и при наличии некоторой упорядоченности использование выборки с замещением может дать отрезки очень больших размеров. Например, если ни одному из ключей в файле не предшествуют более M больших его ключей, то этот файл может быть полностью отсортирован во время прохода выборки с замещением, и слияние вообще не понадобится! Эта возможность служит наиболее веским аргументом в пользу практического применения выборки с замещением.

Главным недостатком сбалансированной многопутевой сортировки является то, что во время слияний активно используется лишь примерно половина внешних устройств: P входных устройств и устройство, на которое записываются выходные данные. Альтернативой этому является выполнение (2P - 1)-путевых слияний с записью на устройство 0 и с распределением данных на другие устройства после каждого прохода слияния. Но этот способ не повышает эффективность, поскольку он удваивает количество проходов распределения данных. Сбалансированное многопутевое слияние, похоже, требует либо дополнительного числа внешних устройств, либо выполнения дополнительных копирований. Разработано несколько хитроумных алгоритмов, которые обеспечивают занятость всех внешних устройств с помощью замены способа, которым сливаются небольшие отсортированные блоки. Простейший из этих методов называется полифазное слияние.

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

Стратегия " сливать до исчерпания " работает для произвольного количества лент, как показано на рис 11.16.

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

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

В примере, представленном на рис 11.16, мы рассуждаем следующим образом: нужно закончить слияние с 1 отрезком на устройстве 0. Следовательно, перед последним слиянием устройство 0 должно быть свободным, а на устройствах 1, 2 и 3 должно быть по одному отрезку. Далее мы определяем, каким должно быть распределение отрезков до выполнения предпоследнего слияния, чтобы получить требуемое распределение. Одно из устройств 1, 2 или 3 должно быть пустым (чтобы его можно было использовать в качестве выходного для предпоследнего слияния) - пусть это будет устройство 3. То есть предпоследнее слияние сливает по одному отрезку с каждого из устройств 0, 1 и 2 и записывает результат на устройство 3. Поскольку предпоследнее слияние оставляет 0 отрезков на устройствах 0 и 1, оно должно начаться с одним отрезком на устройстве 0 и двумя отрезками на каждом из устройств 1 и 2. Аналогичные рассуждения приводят нас к заключению, что слияние, предшествующее только что рассмотренному, должно начинаться с 2, 3 и 4 отрезками на устройствах 3, 0 и 1 соответственно. Продолжая в том же духе, можно построить таблицу распределения отрезков: для получения очередного ряда выбираем из следующего за ним ряда максимальное число, заменяем его нулем и добавляем его к каждому из оставшихся чисел. Это соглашение соответствует определению в предыдущем ряду слияния максимального порядка, которое порождает текущий ряд. Такая техника работает с любым количеством устройств (не менее трех). Возникающие при этом числа являются обобщенными числами Фибоначчи, которые обладают множеством интересных свойств. Если количество отрезков не есть обобщенное число Фибоначчи, то вводятся фиктивные отрезки, которые необходимы для заполнения таблицы.

Основная трудность при реализации полифазного слияния состоит в распределении начальных отрезков (см. упражнение 11.54).

Получив распределение отрезков и рассуждая в прямом направлении, можно вычислить относительные размеры отрезков, рассчитывая их после каждого слияния. Например, первое слияние в примере на рис 11.16 порождает 4 отрезка размером 3 единицы на устройстве 1 и оставляет 2 отрезка размером 1 на устройстве 0 и 1 отрезок размером 1 на устройстве 3 и т.д. Как и в случае сбалансированного многопутевого слияния, можно выполнить указанные операции умножения, просуммировать результаты (кроме нижней строки) и поделить на количество начальных отрезков, чтобы вычислить относительную стоимость в виде числа, кратного стоимости полного прохода по всем данным. Для простоты в расчет затрат мы включаем и фиктивные отрезки, что дает верхнюю границу истинной стоимости.

При начальном распределении для полифазного трехпутевого слияния файла, размер которого в 17 раз больше объема оперативной памяти, мы помещаем 7 отрезков на устройство 0, 4 отрезка на устройство 2 и 6 отрезков на устройство 3. Затем на первой фазе мы выполняем слияния до исчерпания устройства 2, при этом на устройстве 0 остаются 3 отрезка размером 1, на устройстве 3 - 2 отрезка размером 1, и на устройстве 1 - вновь созданные 4 отрезка размером 3. Для файла, в 15 раз большего объема оперативной памяти, мы вначале помещаем на устройство 0 два фиктивных отрезка (см. рис 11.15). Общее количество обработанных в процессе полного слияния отрезков равно 59, т.е. на один меньше, чем в примере сбалансированного слияния (см. рис 11.13), но при этом используется на 2устройства меньше (см. также упражнение 11.50).

Например, если нужно отсортировать 1 миллиард записей, используя 3 устройства и оперативную память, достаточную для размещения 1 миллиона записей, то с помощью двухпутевого полифазного слияния это можно сделать за $$$\lceil \log_{ф}{500}\rceil /ф= 8$$$ проходов. Добавив проход начального распределения, мы получаем несколько большие затраты (один проход), чем для сбалансированного слияния, использующего вдвое больше устройств. То есть можно считать, что полифазное слияние позволяет выполнить ту же работу, но с половиной внешних устройств. Для заданного количества устройств поли-фазное слияние всегда более эффективно, чем сбалансированное слияние, о чем свидетельствует рис 11.17.

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

Количество проходов, выполняемых сбалансированным слиянием с 4 устройствами (вверху), всегда больше, чем количество эффективных проходов, выполняемых полифазным слиянием с 3 лентами (внизу). Представленные графики получены для функций из свойств 11.4 и 11.6, для N/M от 1 до 100. Из-за наличия фиктивных отрезков истинная производительность полифазного слияния имеет более сложный характер, чем показано данной ступенчатой функцией.

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

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

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

Упражнения

11.45. Покажите, какие отрезки порождаются выборкой с замещением, использующей очередь с приоритетами размером 4, для ключей E A S Y Q O U E S T I O N.

11.46. Как отразится использование выборки с замещением для файла, порожденного с помощью выборки с замещением из заданного файла?

11.47. Определите эмпирически среднее число отрезков, порожденных выборкой с замещением, в которой используется очередь с приоритетами размером 1000, для случайно упорядоченных файлов размером N = 103, 104, 105 и 106 .

11.48. Каким будет количество отрезков в худшем случае при использовании выборки с замещением для генерации начальных отрезков из файла, содержащего N записей, с использованием очереди с приоритетами размером M, при M < N?

11.49. Покажите, в стиле рис 11.15, как с помощью полифазного слияния выполняется сортировка ключей E A S Y Q U E S T I O N W I T H P L E N T Y O F K E Y S.

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

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

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

11.53. Напишите программу, вычисляющую количество проходов, выполняемых многопутевым слиянием, и эффективное количество проходов, выполняемых поли-фазным слиянием для заданного количества устройств и заданного количества начальных блоков. Используйте полученную программу для вывода таблицы этих затрат при работе каждого метода, для P = 3, 4, 5, 10 и 100 и N = 103, 104, 105 и 106 .

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

11.55. Реализуйте выборку с замещением, воспользовавшись интерфейсом, определенным в упражнении 11.38.

11.56. Реализуйте сортировку-слияние, комбинируя решения упражнений 11.38 и 11.55. Используйте полученную программу для сортировки файла максимально возможного в вашей системе размера, воспользовавшись полифазным слиянием. При возможности определите, как отражается на времени выполнения программы увеличение числа устройств.

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

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

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

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

Параллельная сортировка-слияние

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

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

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

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

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

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

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

Эту операцию нетрудно реализовать: достаточно слить два входных файла и передать на выход первую и вторую половину полученного файла.

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

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

Для реализации сливающего компаратора на двух процессорах нужно, чтобы они могли обмениваться копиями их блоков данных, выполнять слияние (параллельно), и хранить половины наборов ключей: с меньшими значениями и с большими значениями. Если пересылка блоков происходит медленно по сравнению с быстродействием самих процессоров, то общее время, необходимое для сортировки, можно оценить, умножив время пересылки одного блока на (lgP)2/ 2. Эта оценка предполагает большое число допущений - например, предполагается, что пересылки блоков данных могут производиться параллельно без дополнительных затрат, что редко наблюдается в реальных компьютерах с параллельными процессорами. И все же она представляет собой отправную точку для понимания того, чего можно ожидать от практической реализации.

Если стоимость пересылки блока данных сравнима с быстродействием отдельного процессора (еще одна идеальная цель, к которой реальные машины лишь приближаются), то тогда нужно принимать в расчет время на начальную сортировку. Каждый процессор для начальной сортировки N/P блоков выполняет (N/P) lg (N/P) сравнений (параллельно), и затем примерно P2(lg P) / 2 этапов слияния N/P-и-N/P. Если стоимость сравнения равна $$$\alpha$$$, а стоимость слияния на одну запись равна $$$\beta$$$, то общее время выполнения приблизительно равно $$ $\alpha (N/P) lg(N/P) + \beta (N/P) P^{2} (lgP) / 2$$$.

Для очень больших N и малых P эта производительность является лучшей из того, на что можно рассчитывать, если использовать метод параллельной сортировки, основанной на сравнениях, поскольку в этом случае затраты равны приблизительно $$$\alpha (N lg N) / P$$$, то есть оптимальны: любая сортировка требует N lg N сравнений и лучшее, что можно сделать в этом случае - выполнять P сравнений одновременно. В случае больших значений P преобладает второе слагаемое, и затраты приблизительно равны $$$\beta N (P lg P) / 2$$$, что субоптимально, но вполне конкурентоспособно. Например, при сортировке 1 миллиарда элементов на 64 процессорах вклад второго слагаемого составляет $$$256 \beta N/P$$$, а вклад первого слагаемого - $$$32 \alpha N/P$$$.

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

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

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

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

Упражнения

11.61. Докажите лемму 11.7, воспользовавшись принципом нулей и единиц (лемма 11.1).

11.62. Реализуйте последовательную версию поблочной сортировки с нечетно-четным слиянием Бэтчера: (1) для сортировки блоков данных используйте стандартную сортировку слиянием (программы 8.3 и 8.2), (2) для реализации сливающих компараторов используйте стандартное абстрактное обменное слияние (программа 8.2), а (3) для реализации поблочной сортировки используйте восходящее нечетно-четное слияние Бэтчера (программа 11.3).

11.63. Оцените время выполнения программы, описанной в упражнении 11.62, как функции от N и M, для больших N.

11.64. Выполните упражнения 11.62 и 11.63, но в обоих случаях замените восходящее нечетно-четное слияние Бэтчера (программа 11.3) на программу 8.2.

11.65. Приведите значения P, для которых (N/P) lg N = NP lgP, для N = 103, 106, 109 и 1012 .

11.66. Приведите приближенные выражения вида $$$c_{1}N lgN + c_{2}N$$$ для количества сравнений элементов данных, используемых параллельной поблочной сортировкой Бэтчера для P = 1, 4, 16, 64 и 256.

11.67. Сколько параллельных шагов потребуется для сортировки 10¹⁵ записей, распределенных на 1000 дисках, с помощью 100 процессоров?

Ссылки для части III

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

По вопросам сортировки имеется обширная литература. Опубликованная Кнутом и Райвестом (Rivest) в 1973 г. библиография содержит сотни ссылок на статьи, благодаря которым можно понять, как разрабатывались многие рассмотренные нами классические методы. Более поздние ссылки, с обширной библиографией, охватывающей последние работы, можно найти в книге Баеса-Ятеса и Гонне (Baeza-Yates and Gonnet). Обзор состояния наших знаний о сортировке Шелла можно найти в статье Седжвика (Sedgewick) за 1996 г.

Что касается быстрой сортировки, то наилучшей ссылкой может служить пионерская статья Хоара (Hoare), вышедшая в свет в 1962 г., в которой рассматриваются все наиболее важные варианты, в том числе и использование выборки, упомянутое в . Множество деталей, касающихся математического анализа и практических эффектов многих модификаций и усовершенствований, появившихся после широкого распространения алгоритма, можно найти в статье Седжвика за 1978 г. Бентли и Мак-Илрой (Bently and McIlroy) дали его современную трактовку. Материал по трехпутевому разбиению в и трехпутевой поразрядной быстрой сортировке в основан на этой статье и статье Бентли и Седжвика за 1997 г. Первый алгоритм, использующий разбиения (бинарная быстрая сортировка или поразрядно-обменная сортировка), появился в статье Хильдебрандта и Исбица (Hildebrandt and Isbitz) в 1959 г.

Структура данных биномиальной очереди Вильемина (Vuillemin) в том виде, в каком она была реализована и исследована Брауном (Brown), элегантно и эффективно поддерживает все операции над очередями с приоритетами. Парные пирамидальные деревья, описанные Фредменом (Fredman), Седжвиком, Слитором (Sleator) и Тарьяном (Tarjan), являются усовершенствованиями базового понятия и представляют немалый практический интерес.

В статье, появившейся в 1993 г., Мак-Илрой, Бостик (Bostic) и Мак-Илрой описывают положение дел с реализациями поразрядной сортировки.

Список литературы

1. R. Baeza-Yates and G.H. Gonnet, Handbook of Algorithms and Data Structures, second edition, Addison-Wesley, Reading, MA, 1984.

2. J.L. Bentley and M.D. McIlroy, "Engineering a sort function," Software-Practice and Experience 23, 1 (January, 1993).

3. J.L. Bentley and R. Sedgewick, "Sorting and searching strings," Eighth Symposium on Discrete Algorithms, New Orleans, January, 1997.

4. M.R. Brown, "Implementation and analysis of binomial queue algorithms," SIAM Journal of Computing 7, 3 (August, 1978).

5. M.L. Fredman, R. Sedgewick, D.D. Sleator, and R.E. Tarjan, "The pairing heap: a new form of self-adjusting heap," Algorithmica 1, 1 (1986).

6. P. Hildebrandt and H. Isbitz, "Radix exchange - an internal sorting method for digital computers," Journal of the ACM, 6, 2 (1959).

7. C.A.R. Hoare, "Quicksort," Computer Journal, 5, 1 (1962).

8. Д.Э. Кнут, Искусство программирования, том 3. Сортировка и поиск, 2-е издание, ИД "Вильямс", 2008 г.

9. PM. McIlroy, K. Bostic, and M.D. McIlroy, "Engineering radix sort," Computing Systems 6, 1 (1993).

10. R.L. Rivest and D.E. Knuth, "Bibliography 26: Computing Sorting," Computing Reviews, 13 6 (June, 1972).

11. R. Sedgewick, "Implementing quicksort programs," Communications of the ACM 21, 10 (October 1978).

12. R. Sedgewick, "Analysis of shellsort and related algorithms," Fourth European Symposium on Algorithms, Barcelona, September, 1996.

13. J. Vuillemin, "A data structure for manipulating priority queues," Communications of the ACM 21, 4 (April 1978).