Методы внешней сортировки

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

В основе методов внешней сортировки лежит процедура слияния, заключающаяся в объединении двух или более отсортированных последовательностей. Рассмотрим эту процедуру на примере слияния двух последовательностей A и B в последовательность C. Пусть элементы A и B отсортированы по возрастанию, то есть a₁ £ a₂ £ …£ a_m и b₁ £ b₂ £ …£ b_n . Требуется, чтобы последовательность C также располагалась по возрастанию, то есть выполнялось c₁ £ c₂ £ …£ c_m+n.

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

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

Базовым методом внешней сортировки является метод простого слияния. Рассмотрим его на следующем примере. Пусть имеется файл A, включающий элементы 27, 16, 13, 11, 18, 25, 7. Этот файл разделяется на два файла B и C путем поочередной записи элементов в эти файлы. Покажем это схемой

B: 27, 13, 18, 7

A: 27, 16, 13, 11, 18, 25, 7

C: 16, 11, 25

Затем файлы B и C снова соединяются путем поочередного включения в C элементов из A и B. При этом первым располагается меньший элемент каждой пары. Получится следующий результат

B: 27, 13, 18, 7

A: 16, 27,’ 11, 13,’ 18, 25, ‘ 7

C: 16, 11, 25

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

B: 16, 27,’ 18, 25

A: 16, 27,’ 11, 13,’ 18, 25, ‘ 7

C: 11, 13,’ 7

Далее происходит соединение пар в упорядоченные четверки путем использования процедуры слияния

B: 16, 27,’ 18, 25

A: 11, 13, 16, 27,’ 7, 18, 25

C: 11, 13,’ 7

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

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

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

Как видно из приведенных выше данных, метод может конкурировать по скорости с самыми быстрыми методами внутренней сортировки, но не применяется в таком качестве, так как требует значительных затрат памяти. Число проходов оценивается величиной log ₂ n, а общее число пересылок M пропорцинально n log ₂ n.

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

Назовем серией последовательность элементов a_i, a_i+1, …, a_j, удовлетворяющих соотношениям a_i-1 > a_i £ a_i+1 £ …£ a_j > a_j+1. В частных случаях серия может находиться в начале или конце последовательности.

Исходный файл A разбивается на серии. Распределение на B и C ведется по сериям. При соединении сливаются пары серий. Снова возможен как трехленточный, так и четырехленточный вариант метода. Ниже показан пример сортировки методом естественного слияния c 4 лентами.

B: 17, 25, 41, ‘6

A: 17, 25, 41, ‘ 9, 11, ‘ 6, ‘ 3, 5, 8, 44

C: 9, 11, ‘ 3, 5, 8, 44

A: 9, 11, 17, 25, 41 B: 3, 5, 6, 8, 9, 11, 17, 25, 41, 44

D: 3, 5, 6, 8, 44 C:

При последнем разделении лента C оказывается пустой, и отсортированный файл остается на ленте B.

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

Program SortSlian;

{ 3-ленточная, 2-фазная сортировка естественным слиянием }

{ ключи целые и положительные }

Uses Crt;

Type

elem=record

Key: integer;

{ другие поля }

end;

tape=file of elem;

Var

Name: string[30]; { имя исходного файла }

A, B, C: tape;

K, L: integer;

S, T: elem;

e: boolean;

Procedure Vvod(var F: tape);

Begin

Rewrite(F);

K:=1;

While K <> -1 do

begin

Write('Введите очередной ключ (конец -1): ');

Read(K);

S.Key:=K;

if K<>-1 then Write(F, S)

end;

ReadLn;

Close(F)

End;

Procedure Pech(var F: tape);

Begin

Reset(F);

While not eof(F) do

begin

Read(F, S);

Write(S. Key,' ')

end;

WriteLn

End;

Procedure CopyElem(var X, Y: tape;

var Buf: elem; var E: boolean);

{ копирование элемента и считывание следующего }

{ в Buf с проверкой конца серии (E=True) }

Begin

K:=Buf.Key;

Write(Y, Buf);

if not Eof(X) then Read(X, Buf)

else Buf.Key:=-1; { барьер: достигнут конец файла }

E:=(Buf.Key<K) { E=True в конце серии }

End;

Procedure CopySer(var X, Y: tape; var Buf: elem);

{ копирование серии из X в Y }

{ в начале Buf-первый элемент текущей серии на X }

{ в конце Buf-первый элемент следующей или –1 (конец X) }

Begin

if Buf.Key>0 then { файл X не считан }

Repeat

CopyElem(X, Y, Buf, E)

Until E { E=True в конце серии }

End;

Procedure Raspred;

{ распределение A ---> B и C }

Begin

Reset(A);

Read(A, S); { первый элемент из A }

Rewrite(B);

Rewrite(C);

Repeat

CopySer(A, B, S); { S-первый элемент следующей серии }

if S.Key>0 then { файл A скопирован не весь }

CopySer(A, C, S)

Until S.Key<0

End;

Procedure Slian;

{ слияние B и C--->A }

Var

E1, E2: boolean;

Procedure SlianSer;

{ слияние серий из B и C ---> A }

{ S и T - первые элементы серий }

{ S.Key<0-весь файл B считан, T.Key<0-файл C считан }

Begin

Repeat

E1:=False;

E2:=False;

if (S.Key>0) and ((S.Key<T.Key) or (T.Key<0)) then

{ файл B не считан и текущий элемент B меньше, чем в C }

{ либо файл C полностью считан }

begin

CopyElem(B, A, S, E1);

if E1 then { достигнут конец серии на B }

CopySer(C, A, T)

end

else

begin

CopyElem(C, A, T, E2);

if E2 then { достигнут конец серии на C }

CopySer(B, A, S)

end

Until E1 or E2

End;

Begin { начало Slian }

Reset(B);

Reset(C);

if not (Eof(B) or Eof(C)) then

begin { оба файла не пусты }

Rewrite(A);

Read(B, S);

Read(C, T);

L:=0; { счетчик числа серий }

While (S.Key>0) or (T.Key>0) do

begin

SlianSer;

L:=L+1

end

end

End;

Begin { начало основной программы }

ClrScr;

Write('Введите имя файла для записи элементов: ');

ReadLn(name);

Assign(A, Name);

Assign(B, 'Rab1');

Assign(C, 'Rab2');

Vvod(A);

L:=0; { L - число серий после слияния - параметр }

Repeat

WriteLn('Файл A: '); Pech(A);

Raspred; { фаза распределения }

WriteLn('Файл B: '); Pech(B);

WriteLn('Файл C: '); Pech(C);

ReadLn; { пауза }

Slian { фаза слияния }

Until L<=1; { L=0, если исходный файл отсортирован }

WriteLn('Файл A в конце: ');

Pech(A);

Close(A);

Close(B); Erase(B); { удаление рабочих файлов }

Close(C); Erase(C);

ReadLn

End.

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

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

На сколько может отличаться количество серий после разделения? На первый взгляд кажется, что не более, чем на одну, но это не так. Например, при распределении серий 17, 25, 41, ’ 9, 60, ‘ 50, 52, ‘ 7 первая и третья серии сливаются в общую серию, что не происходит со второй и четвертой сериями. В результате при последующем слиянии серии на одной из лент могут закончиться раньше, и придется впустую переписывать остаток другой ленты, теряя эффективность. Подобные ситуации учитываются в методе многофазной сортировки. Рассмотрим его на примере трех лент.

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

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

Заключение

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

1. Постановка задачи понимается неправильно. Порой это выясняется только при сдаче учебной программы. Часто студентами предъявляются претензии о некорректной или недостаточно полной формулировке задачи. Следует иметь в виду, что реальные задания на создание программного обеспечения как правило неполны, неточны и противоречивы. Достаточная ясность возможна только при тесном контакте с заказчиком. При обучении в роли такого заказчика выступает преподаватель.

2. Алгоритмическая проработка задачи проводится поверхностно. В результате при тестировании выявляются принципиальные ошибки.

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

4. Текст программы сложен для восприятия и проверки. Для повышения “удобочитаемости” программы рекомендуется [7,8]:

· применять осмысленные имена переменных;

· резко ограничивать использование одних и тех же идентификаторов для различных целей;

· вставлять подробные комментарии, поясняющие назначение и функционирование программных фрагментов;

· применять отступы в тексте программы, выделяющие группы операторов и показывающие вложенность программных единиц.

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

Более точное определение: “Тестирование – это процесс выполнения программы с целью нахождения ошибок” [7, 8]. Следуя данному определению, цель тестирования – заставить программу сбиться, “сломать” программу.

Обычно тестирование и отладка требуют большей трудоемкости, чем разработка программы. Рекомендуется придерживаться следующих правил тестирования [7, 8].

1. Выбор теста должен преследовать цель обнаружения ошибки, а не демонстрации правильности работы программы.

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

3. Необходимая часть всякого теста – описание ожидаемых результатов. Желательно прогнозировать результаты до выполнения теста.

4. Тесты должны охватывать как правильные, так и неправильные данные.

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

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

Литература

1. Кнут Д. Искусство программирования. Тома 1-3. - М.: Издат. дом “Вильямс”, 2003.

2. Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1980. - 406 c.

3. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989. - 360 с.

4. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980. - 476 с.

5. Лэнгсам И., Огенстайн М., Тенебаум А. Структуры данных для персональных ЭВМ. -М.: Мир, 1989. - 568 с.

6. Трамбле Ж., Соренсон П. Введение в структуры данных. - М.: Машиностроение, 1982. - 784 с.

7. Майерс Г. Надежность программного обеспечения. - М.: Мир, 1980. - 360 с.

8. Хьюз Дж., Мичтом Дж. Структурный подход к программированию. - М.: Мир, 1980. - 278 с.

9. Фараонов В.В. Турбо Паскаль 7.0. Практика программирования: Учебное пособие. – М.: Нолидж, 1997.- 432 с.

10. Нильсон Н. Искусственный интеллект. Методы поиска решений. – М.: Мир, 1973. – 270 с.

11. Автоматизация поискового конструирования / Под ред. А.И. Половинкина. – М.: Радио и связь, 1981. – 344 с.

12. Топп У., Форд У. Структуры данных в С++. – М.: Бином, 2000. – 815 с.

13. Галочкин В.И. Структуры и организация даннных в ЭВМ: Методические указания к выполнению лабораторных и расчетно-графических работ для студентов второго курса специальности 2204. – Йошкар-Ола: 1994. – 42 с.

14. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – М.: Издат. дом “Вильямс”, 2003. – 382 с.

Содержание