Сойдется ли при таком начальном распределении алгоритм внешней многофазной сортировки слиянием
Сойдется ли при таком начальном распределении алгоритм внешней многофазной сортировки слиянием
В другом вопросе описывается простейшая сортировка слиянием. Ее вполне можно применить к любому файлу и она будет работать.
Н иже мы разберем серьезно улучшенный алгоритм внешней сортировки слиянием работающий намного быстрее.
Многофазная сортировка слиянием.
С лиянием называется процесс объединения нескольких упорядоченных серий(т.е упорядоченных списков) в одну.
Пример для 3-х серий, слияемых на 4-ю:
H а каждом шаге мы беpем наименьший из начальных элементов входных серий и перемещаем в конец выходной серии.
В реальной ситуации в качестве лент выступают односвязные списки или файлы.
С трелки показывают процесс слияния. Hапример, на втором шаге мы слияем с f1, f2, f3, f4 и f6 на f5, пока одна из лент не опустеет.
В каждый момент времени слияние происходит на пустую ленту с остальных, поэтому число требующихся проходов приблизительно равно log n.
Д алее нам понадобятся числа Фибоначчи порядка p.
И з этого следует, что наш алгоритм многофазного слияния применим только к таким входным данным, в которых число серий есть сумма n-1 таких сумм Фибоначчи.
Х олостые серии по возможности равномерно распределяются по лентам, чтобы реальное слияние (в котором холостые серии участвуют лишь ‘в уме’) проходило с как можно большего количества лент.
С начала все данные располагаются на одной ленте. Лента читается и отрезки распределяются по другим лентам, имеющимся в системе. после того, как созданы начальные отрезки, они сливаются, как описано выше. Один из методов, который можно использовать для создания начальных отрезков, состоит в чтении порции записей в память, их сортировке и записи результата на ленту. Выбор с замещением(см. другой вопрос) позволяет нам получать более длинные отрезки. Этот алгоритм работает с буфером, располагающимся в оперативной памяти. Сначала мы заполняем буфер. Затем повторяем следующие шаги до тех пор, пока не будут исчерпаны входные данные:
Выбрать запись с наименьшим ключом, т.е. с ключом, значение которого >= значения ключа последней прочитанной записи.
Если все «старые» ключи меньше последнего ключа, то мы достигли конца отрезка. Выбираем запись с наименьшим ключом в качестве первого элемента следующего отрезка.
Записываем выбранную запись.
Заменяем выбранную и записанную запись на новую из входного файла.
H а следующей таблице выбор с замещением иллюстрируются для совсем маленького файла.
О братите внимание мы храним записи в буфере до тех пор, пока не наступит время записать их в выходной файл. Если вход случаен, средняя длина отрезков равна примерно удвоенной длине буфера. Однако, если данные хоть как-то упорядочены, отрезки могут быть очень длинными. Вот почему этот метод, вообще говоря, более эффективен промежуточных, частичных сортировок.
П рочитав из входного файла очередную запись, мы ищем наименьший ключ, который >= последнего считанного. При этом мы, конечно, можем просто сканировать записи в буфере. Однако, если таких записей тысячи, время поиска может оказаться недопустимо большим. Если на этом этапе использовать двоичные деревья, нам понадобится всего лишь log n сравнений.
В реализации внешней сортировки на ANSI-C функция makeRuns вызывает readRec для чтения очередной записи. В функции readRec используется выбор с замещением (с двоичными деревьями) для получения нужной записи, а makeRuns распределяет записи согласно ряду Фибоначчи. Если количество отрезков оказывается вне последовательности Фибоначчи, в начало каждого файла добавляются пустые отрезки(холостые серии). Затем вызывается функция mergeSort, которая производит многофазное слияние отрезков.
Д ля проверки и демонстрации прилагаю две дополнительные программы:
В торая читает бинарный файл ‘output’ размера AMOUNT и выдает ключи в порядке появления. Предположения о типах те же.
Сортировки слиянием
Сортировки слиянием работают по такому принципу:
Как видите, объединить два упорядоченных массива в один не просто, а очень просто. Нужно двигаться одновременно в обоих массивах слева-направо и сравнивать очередные пары элементов из обоих массивов. Меньший элемент отправляется в общий котёл. Когда в одном из массивов элементы заканчиваются, оставшиеся элементы из другого массива просто по порядку переносятся в главный список.
В этом-то и соль алгоритмов данного класса. Изначально рандомный массив можно разбить на множество небольших упорядоченных подмассивов. При попарном слиянии количество упорядоченных подмассивов уменьшается, длина каждого из них увеличивается. На последнем шаге массив представляет из себя всего два упорядоченных подмассива, которые сливаются в единую упорядоченную структуру.
Автором данной концепции является Джон фон Нейман. Иногда встречается спорное утверждение, что сортировку он придумал во время работы над Манхеттенским проектом, поскольку перед ним стояла задача обеспечить эффективные расчёты огромного количества статистических данных при разработке ядерной бомбы. Сложно оценить правдоподобность данной версии, поскольку первые его работы по сортировке слиянием датируются 1948 годом, а создание бомбы были завершено 3-мя годами раннее. Впрочем, что же там за атомная сортировка, давайте на неё взглянем.
Естественное неймановское слияние
На неймановский алгоритм повлияли конструктивные особенности компьютеров 40-х годов. Выглядело это так:
Сложность данного алгоритма скромна — O(n 2 ), и, тем не менее, для пионеров ламповых вычислений это был прорыв.
На примере этой первой сортировки слиянием уже виден недостаток этого класса алгоритмов — расходы на дополнительную память. В этом плане почти все сортировки слиянием дополнительно требуют O(n), однако изредка встречаются элегантные исключения.
Прямое слияние Боуза-Нельсона
Строго говоря, алгоритм Боуза-Нельсона — это сортировочная сеть, а не сортировка. В процессе массив и все его подмассивы делятся пополам и ничто не препятствует тому, чтобы все эти половинки на всех этапах обрабатывались параллельно. Однако можно представить и в виде именно сортировки. А до темы сортировочных сетей мы когда-нибудь доберёмся тоже.
Ссылки
Merge / Слияние
Статьи серии:
Для сортировки Боуза-Нельсона поставлено ограничение — размер массива должен быть степенью двойки. Если это условие не будет выполнено, то макрос обрежет массив до подходящего размера.
Статья написана при поддержке компании EDISON Software, которая пишет софт 3d-реконструкции и занимается разработкой сложного измерительного оборудования.
Полифазная сортировка слиянием
СОДЕРЖАНИЕ
Обычная сортировка слиянием [ править ]
Если есть только три рабочих файла, то обычная сортировка слиянием слияниями отсортированных запускает два рабочих файла в один рабочий файл, а затем распределяет запуски равномерно между двумя выходными файлами. Итерация слияния уменьшает количество запусков в 2 раза, итерация с перераспределением не уменьшает количество запусков (коэффициент равен 1). Можно рассматривать каждую итерацию для уменьшения количества запусков в среднем на √ 2 ≈ 1,41. Если есть 5 рабочих файлов, то шаблон чередуется между трехсторонним слиянием и двухсторонним слиянием для среднего коэффициента √ 6 ≈ 2,45.
В общем, для четного числа рабочих файлов N каждая итерация обычной сортировки слиянием уменьшает количество запусков в N / 2, в то время как для нечетного числа рабочих файлов N каждая итерация уменьшает количество запусков на средний коэффициент. из √ ( N 2 −1) / 4 = √ N 2 −1 / 2.
Полифазное слияние [ править ]
Для N [1] [2] Обратите внимание, что, за исключением последней итерации, коэффициент уменьшения количества запусков немного меньше 2, 57/31, 31/17, 17/9, 9/5, 5/3, 3/1, около 1,84 для 4 файлов. случае, но каждая итерация, кроме последней, уменьшала количество запусков при обработке примерно 65% набора данных, поэтому коэффициент уменьшения количества запусков на набор данных, обработанный во время промежуточных итераций, составляет примерно 1,84 / 0,65 = 2,83. Для набора данных, состоящего из 57 прогонов по 1 записи в каждом, затем после начального распределения многофазная сортировка слиянием перемещает 232 записи в течение 6 итераций, необходимых для сортировки набора данных, с общим коэффициентом уменьшения 2,70 (более подробно это объясняется позже. ).
Идеальная сортировка слиянием многофазных 3 файлов [ править ]
Проще всего рассматривать многофазное слияние, начиная с его конечных условий и работая в обратном направлении. В начале каждой итерации будет два входных файла и один выходной файл. В конце итерации один входной файл будет полностью использован и станет выходным файлом для следующей итерации. Текущий выходной файл станет входным файлом для следующей итерации. Остальные файлы (только один из трех файлов) были израсходованы только частично, и их оставшиеся прогоны будут введены для следующей итерации.
Файл 1 только что очистился и стал новым выходным файлом. На каждой входной ленте остается по одному прогону, и объединение этих прогонов вместе создаст отсортированный файл.
Возвращаясь к другой итерации, 2 прогона объединяются с 1 и 3, прежде чем файл 3 станет пустым.
Возвращаясь к другой итерации, 3 прогона объединяются из 2 и 3, прежде чем файл 2 станет пустым.
Возвращаясь к другой итерации, 5 прогонов объединяются из 1 и 2, прежде чем файл 1 станет пустым.
Распределение для многофазной сортировки слиянием [ править ]
Чтобы все работало оптимально, последняя фаза слияния должна иметь ровно один запуск для каждого входного файла. Если какой-либо входной файл имеет более одного запуска, потребуется еще одна фаза. Следовательно, сортировка с многофазным слиянием должна быть умной в отношении начального распределения прогонов входных данных по исходным выходным файлам. Например, входной файл с 13 запусками будет записывать 5 запусков в файл 1 и 8 запусков в файл 2.
После начального распределения обычная сортировка слиянием с использованием 4 файлов сортирует 16 прогонов отдельных записей в 4 итерациях всего набора данных, перемещая в общей сложности 64 записи, чтобы отсортировать набор данных после начального распределения. При многофазной сортировке слиянием с использованием 4 файлов будет отсортировано 17 прогонов отдельных записей за 4 итерации, но поскольку каждая итерация, но последняя итерация перемещает только часть набора данных, она перемещает всего 48 записей, чтобы отсортировать набор данных после начальной распределение. В этом случае обычный коэффициент сортировки слиянием равен 2,0, а общий коэффициент многофазности составляет ≈2,73.
Чтобы объяснить, как коэффициент уменьшения связан с производительностью сортировки, используются следующие уравнения коэффициента уменьшения:
Используя уравнение подсчета ходов для приведенных выше примеров:
Вот таблица эффективных коэффициентов уменьшения для многофазной и обычной сортировки слиянием, перечисленных по количеству файлов на основе фактических сортировок из нескольких миллионов записей. Эта таблица примерно соответствует коэффициенту уменьшения для перемещенных таблиц набора данных, показанных на рис. 3 и рис. 4 многофазного слияния sort.pdf.
В общем, многофазная сортировка слиянием лучше, чем обычная сортировка слиянием, когда файлов меньше 8, в то время как обычная сортировка слиянием начинает улучшаться примерно при 8 или более файлах. [6] [7]
Алгоритмы сортировки массивов. Внешняя сортировка
К наиболее известным алгоритмам внешних сортировок относятся:
Из представленных внешних сортировок наиболее важным является метод сортировки с помощью слияния. Прежде чем описывать алгоритм сортировки слиянием введем несколько определений.
Основным понятием при использовании внешней сортировки является понятие серии. Серия (упорядоченный отрезок) – это последовательность элементов, которая упорядочена по ключу.
Количество элементов в серии называется длиной серии. Серия, состоящая из одного элемента, упорядочена всегда. Последняя серия может иметь длину меньшую, чем остальные серии файлов. Максимальное количество серий в файле N (все элементы не упорядочены). Минимальное количество серий одна (все элементы упорядочены).
В основе большинства методов внешних сортировок лежит процедура слияния и процедура распределения. Слияние – это процесс объединения двух (или более) упорядоченных серий в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. Распределение – это процесс разделения упорядоченных серий на два и несколько вспомогательных файла.
Общий алгоритм сортировки слиянием
Выделим основные характеристики сортировки слиянием:
Рассмотрим основные и наиболее важные алгоритмы внешних сортировок более подробно.
Сортировка простым слиянием
Одна из сортировок на основе слияния называется простым слиянием.
Алгоритм сортировки простым слиянием
Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2. При этом упорядоченные пары переходят в упорядоченные четверки.
Шаг 4. Повторяя шаги, сливаем четверки в восьмерки и т.д., каждый раз удваивая длину слитых последовательностей до тех пор, пока не будет упорядочен целиком весь файл ( рис. 43.1).
Признаками конца сортировки простым слиянием являются следующие условия:
Заметим, что для выполнения внешней сортировки методом простого слияния в оперативной памяти требуется расположить всего лишь две переменные – для размещения очередных элементов (записей) из вспомогательных файлов. Исходный и вспомогательные файлы будут O(log n) раз прочитаны и столько же раз записаны.
Сойдется ли при таком начальном распределении алгоритм внешней многофазной сортировки слиянием
Привет Всем.
Кто-нибудь поможет разобраться с алгоритмом внешней многофазной сортировки слиянием (со специальным распределением начальных серий)? Перелопатил уже книжки Д.Кнута и Н.Вирта и все никак до конца не разберусь. Давно сижу уже за заданием, никак не осилю, при всем моем большом желании и энтузиазме.
Проблема немного возникает с распределением серий, а именно, с добавлением фиктивных серий. Также были попытки хотя бы со 12900 элементов (а не 10000, как в задании), что будет являться фибоначевским распределением, но возникает проблема со слиянием тогда. Вообщем, кто сталкивался (или даже может не сталкивался, но понял задание), прошу пожалуйста помочь, алгоритмом быть может, ну или чем сможете 🙂 Заранее спасибо.
Александр, если еще актуально, то слияние делается так:
Есть K реальных серий.
1) Выбираем наименьший(это зависит от критерия сортировки) элемент из крайних элементов всех серий.
2) запоминаем серию в которой нашли минимальный элемент
3) копируем его в результирующий файл, а из той серии читаем следующий,
чтобы опять получить список из K крайних элементов.
4) если в серии больше нет элементов, то убираем ее(файл с ней) из рабочего списка,
при этом естественно уменьшается К.
5) если К стало равно 0, значит мы слили K серий, если нет то идем к пункту 1.
6) PROFIT.
Мне кажется эта часть алгоритма сравнительно простая по сравнению с распределением серий. У Вирта, кстати, есть и реализация для произвольного количества файлов и если переписать ее, дав переменным адекватные имена, то можно попробовать разобраться.
Да, надо сливать по сериям. На самом деле я как раз это и имел ввиду, просто не учел, что заранее известна длина серии. Если не известна, то надо определять конец в процессе чтения, но не зависимо от этого слияние прекращается когда из каждого файла было извлечено по 1 серии. Опять же надо учесть, что размер файла может быть не кратен размеру серии, со всеми вытекающими.
«Мало хочется использовать функцию write, а оператором » (fstream) что-то не смог обойтись.»
Да вроде ничего плохого в этом нет. Единственное что fstream нужно достать из for, достаточно открыть файл в начале слияния и закрыть в конце, а не открывать и закрывать для записи каждого элемента.
Кроме того серии заканчиваются не одновременно и надо исключать из поиска минимального элемента те, из которых уже было прочитано 100.
В остальном по слиянию похоже все ок.