AOP_Tom3 (1021738), страница 65
Текст из файла (страница 65)
К счастью, слияние оперирует только очень простыми структурами данных, а именно — линейными списками, обрабатывать которые можно последовательно, как стеки или очереди. Поэтому для реализации метода слияния годятся самые непритязательные устройства внешней памяти. Только что описанный процесс — внутренняя сортировка с последующим "внешним слиянием" — весьма популярен, и наше изучение внешней сортировки сведется, в основном., к вариациям на эту тему, Возрастающие последовательности записей, получаемые на начальной фазе внутренней сортировки, в литературе о сортировке часто называются цепочками (э1Нпб). Этот термин довольно широко распространен, но, к сожалению, он противоречит еще более популярному термину ' в1г1пи" в других разделах вычислительной науки, в которых он означает произвольную последовательность символов. При изучении перестановок уже было дано вполне подходящее название для упорядоченных сегментов файла, которые мы договорились называть восходящими сериями или просто сериями.
В соответствии с этим будем использовать слово "серии" для обозначения упорядоченных частей файла. Таким образом, использование понятий "цепочки серий" и "серии цепочек" не приведет ни к каким недоразумениям. Рассмотрим сначала процесс внешней сортировки, использующей в качестве вспомогательной памяти накапотпелн на магиошнмх лентах (в дальнейшем для краткости будем употреблять термин "магнитные ленты"), Вероятно, простейшим и наиболее привлекательным способом слияния с помощью лент служит сбалансированное даухпутевае слияние, в основе которого лежит идея, использовавшаяся ранее в алгоритмах 5.2.4, Х, Б и 1.
В процессе слияния нам потребуются четыре "рабочие ленты". На первой фазе восходящие серии, получаемые при внутренней сортировке, помещаются поочередно на ленты 1 и 2 до тех пор, пока не исчерпаются исходные данные. Затем ленты 1 и 2 перематываем к началу и выполняем слияние серий, которые находятся на этих лентах, получая новые серии, вдвое длиннее исходных. Эти новые серии записываются по мере их формирования попеременно на Л! ° ° Л!ОООООО Л200000! .
ЛЗОООООО! Л400000! ° ° Л5000000 В!ааааа! . Взаааоао,' Лзааоаа! "Взоааооа (Пустая) (Пустая) Лента 1 Лента 2 Лента 3 Лента 4 После первого прохода слияния на лентах 3 и 4 получатся более длинные серии, чем на лентах 1 и 2: Лента 3 Л1 .. Взоопюа' Взооаао! Взоаоооо Лента 4 Взаооао! . В4аааооа (2) (В конеЦ ленты 2 неЯвно ДобавлЯетсЯ фнктивнвл сеРиЯ, так что сеРиЯ Взооаош ...
Взааааоа просто копируется на ленту 3.) После перемотки всех лент к началу следу- ющий проход по данным приведет к такому результату: Лента 1 Л! . Лзааоаоо Лента 2 В4ооаоо! .. Взаоооао (3) (Серия Л ааааа! Взааооао снова копируется, но если бы мы начали с 8 млн записей, в этот момент на ленте 2 содержалось бы Взоаоао! . Лз!юоаао ) Например "осле еще одной перемотки на ленте 3 окажется серия В!... Взоаоааа и сортировка закончится. Сбалансированное слияние легко обобщается для 'Т лент при любом Т > 3.
Выберем произвольное число Р, 1 < Р < Т, и разделим Т лент на два "банка": Р лент в левом банке и Т вЂ” Р лент в правом банке. Распределим исходные серии квк можно равномернее по Р лентам левого "банка", затем выполним Р-путевое слияние слева направо, после этого — (Т вЂ” Р)-путевое слияние справа налево и так до тех пор, пока сортировка не завершится. Обычно значение Р лучше всего выбирать равным (Т~21 (см. упр. 3 и 4). При Т = 4, Р = 2 имеем частный случай — сбалансированное двухпутевое слияние. Вновь рассмотрим предыдущий пример, используя большее количество лент; положим Т = б и Р = 3.
Начальное распределение теперь будет таким: Лента 1 Л! .. В!ааоооо, 'Взоаааш Ваюоооа Лента 2 Л!Ооооо! ° ° Лзооаааа; Лзааоао! Взоааоао Лента 3 Взооооа! . Взоааооа (4) ленты 3 и 4. (Если на ленте 1 на одну серию больше, чем на ленте 2, то предполагается, что лента 2 содержит дополнительную "фиктивную" серию длиной 0.) Затем все ленты перематываются к началу и содержимое лент 3 и 4 сливается в серии удвоенной длины, записываемые поочередно на ленты 1 и 2. Процесс продолжается (при этом длина серий каждый раз удваивается) до тех пор, пока не останется одна серия (а именно — весь упорядоченный Файл).
Если после внутренней сортировки было получено Я серий, причем 2" ' < 5 < 24, то процедура сбалансированного двухпутевого слияния произведет ровно й = ()й 51 проходов по всем данным. Например, в рассмотренной выше ситуации, когда требуется упорядочить 5 млн записей, а объез! внутренней памяти составляет 1 млн записей, мы имеем Я = 5. На начальной распределительной фазе процесса сортировки пять серий будут помещены на ленты следующим образом: Первый проход слияния приведет к следующему результату: Л1 .. Лзаааааа Лзааа001 .. Лзаааааа (Пустая) Лента 4 Лента 5 Лента 6 (5) Л1 ..
Лзаааааа', Лзааааа1 .. Л1000000 Л1000001 ° Л2000000 Л4000001 Л0000000 Лза00001 Лзаааааа (Пустая) Лента 1 Лента 2 Лента 3 Лента 4 Теперь, выполнив трехпутевое слияние на ленту 4 и перемотку лент 3 и 4 с последующим трехпутевым слиянием на ленту 3, можно было бы завершить сортировку, прочитав всего 3000000 -ь 5000000 = 8000000 записей. Наконец, если бы мь1 имели шесть лент, то могли бы, конечно, записать исходные серии на ленты 1 — 5 и закончить сортировку за один проход, выполнив пятипутевое слияние на ленту 6. Анализ этих случаев показывает, что простое сбалансированное слияние не является наилучшим и было бы интересно поискать более удачные способы слияния.
В последующих разделах этой главы внешняя сортировка исследуется более глубоко. В разделе 5.4.1 рассматривается фаза внутренней сортировки, порождающая начальные серии. Особый интерес представляет технология "выбор с замещением'; (Предполагается, что на ленте 3 помещена фиктивнаи серия.) На втором проходе слиЯниЯ Работа завеРшаетсЯ и сеРии Л1... Лзаааааа помешаютсЯ на лентУ 1. Этот частный случай для Т = 6 эквивалентен случаю для Т = 5, поскольку лента 6 используется лишь при Я > 7. При трехпутевом слиянии затрачивается фактически несколько больше времени центрального процессора, чем при двухпутевом, но оно обычно пренебрежимо мало по сравнению со временем, необходимым для чтения, записи и перемотки ленты.
Мы довольно хорошо оценим время выполнения сортировки, если примем во внимание только суммарнук1 величину перемещений лент. В предыдущем примере ((4) и (5)) требуются только два прохода по данным по сравнению с тремя проходами при Т = 4. Таким образом, слияние при Т = 6 займет около двух третей времени по отношению к предыдущему случаю. Сбалансированное слияние кажется очень простым и естественным. Но если приглядеться внимательнее, то сразу видно, что это не наилучший способ для рассмотренных выцзе частных случаев.
Вместо того чтобы переходить от (1) к (2) и перематывать все ленты, нам следовало остановить первое слияние, когда иа лентах 3 и 4 содержались соответственно Л1 ..Лзаааааа и Лзаааааз Л1000000, а пенза 1 была готова к считыванию Лзаааащ... Лзашааа. Затем ленты 2 — 4 могли быть перемотаны к началу и сортировка завершилась бы трехпутевым слиянием на ленту 2. Общее число записей, прочитанных с ленты в ходе этой процедуры, составило бы 4000000 + 5000000 = 9000000 против 5000000 + 5000000 + 5000000 = 15,000000 в сбалансированной схеме.
Сообразительная машина могла бы постичь и это! Имея пять серий и четыре ленты, можно поступить еще лучше, распределив серии следующим образом: в которой используется порядок, присутствующий в большинстве данных, чтобы породить длинные серии, значительно превосходящие емкость внутренней памяти. В разделе 5.4Л обсуждаются также структуры данных, удобные для многопутевого слияния. Важнейшие схемы слияния рассматриваются в разделах 5.4.2 — 5.4.5. Пока мы не вступим в единоборство с грубой действительностью работающих накопителей на ма1 нитных лентах и реальных сортируемых данных, лучше, изучая характеристики этих схем, ограничиться весьма приближенным представлениезв о сортировке на лентах.
Например, можно с легкой душой полагать (как мы делали до сих пор), что первоначальные исходные записи появляются волшебным образом в течение первой распределительной фазы. На самом деле'они, вероятно, будут занимать одну из наших лент и, быть может, даже целиком заполнят несколько бобин, так как лента не бесконечна! Лучше всего пренебречь подобными техническими деталями до тех пор, пока не будет достигнуто "академическоеь понимание классических схем слияния. Затем в разделе 5.4.6 мы ивернемся на землю", рассмотрев практические ограничения, которые существенно влияют на выбор схемы слияния. В разделе 5.4.6 сравниваются основные схемы слияния из разделов 5.4.2-5.4.5 с учетом множества разнообразных предположений, которые встречаются на практике.
Иные подходы к проблеме внешней сортировки, не основанные на слиянии, обсуждаются в разделах 5.4.7 и 5.4.8. Анализ разнообразных аспектов внешней сортировки заканчивается в разделе 5.4.9. в котором рассматривается важная проблема сортировки с использованием таких устройств внешней памяти, как магнитвые диски и барабаны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
