3 Последовательный файл

3.1 Основные свойства последовательных файлов

Рассмотрим кратко файл в контексте нашего предмета, не повторяясь в части описания операций над фай­лами.

Общее свойство ранее рассмотренных структур данных состоит в том, что число их компонент конечно (т.е. конечно кардинальное число).

В усложненных структурах - последовательности, деревья, графы и т.д. – мы можем не знать число ком­понент (т.е. кардинальные числа бесконечны).

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

Формально (логически) определить структуру типа "последовательный файл" можно следующим образом.

Последовательность с базовым типом Т₀ – это либо пустая последовательность, либо конкатенация после­довательности элементов (базового типа Т₀) и элемента типа Т₀.

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

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

В качестве Т₀ может быть любой простой или структурированный тип, но не файл.

Вспомним, что над файлом можно выполнить два явных типа действий:

1. просмотр файла. Он выполняется в результате последовательного продвижения по файлу, начиная с начала;

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

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

3.2 Сортировка последовательных файлов

Вспомним задачу сортировки в общем виде. Даны элементы

a₁, a₂ ,..., a_n .

Сортировка означает перестановку этих элементов в порядке

a_k1, a_k2 ,...,a_kn , так что при заданной функции упорядочения ƒ справедливо отношение

f (a_k1) ≤ f (a_k2 ) ≤...≤ f (a_kn ) .

Обычно функция упорядочения хранится в самом элементе в виде явной компоненты (поля), и ее значение

называют ключом элемента. Следовательно, для представления элемента a_i хорошо подходит тип записи:

TYPE ITEM = RECORD

KEY : INTEGER; {другие компоненты} END "Другие компоненты" содержат все существенные данные об элементе. Для задач же сортировки единст­венной существенной компонентой является ключ.

Рассмотрим некоторые методы сортировки в массивах. К сожалению, они неприемлемы, если сортируе­мые данные находятся не в оперативной памяти, а на внешнем ЗУ последовательного доступа (последователь­ные файлы). В этом случае в каждый момент времени имеется доступ только к одному элементу. Это ограни­чение и приводит к тому, что для последовательных файлов приходится применять другие методы сортировки.

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

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

1. Последовательность a разбивается на две половины b и c.

2. Последовательности b и c сливаются при помощи объединения отдельных элементов в упорядоченные пары.

3. Полученной последовательности присваивается имя a, после чего повторяются шаги 1 и 2; при этом упорядоченные пары сливаются в упорядоченные четверки.

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

Пример. Последовательность

Исходная после-	а=	44 55 12 42 94 18 06 6
довательность
1	b=	44 55 12 42
	с=	94 18 06 67
	а=	44 94' 18 55' 06 12' 42 67
2	Ь=	44 94' 18 55'
	с=	06 12' 42 67
	а=	06 12 44 94' 18 42 55 67'
3	Ь=	06 12 44 94'
	с=	18 42 55 67'
	а=	06 12 18 42 44 55 67 94

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

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

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

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

Вместо двух файлов можно использовать один массив, рассматривая его как последовательность с двумя концами. И вместо того, чтобы сливать элементы из двух файлов, можно брать их с двух концов массива. Та­ким образом общий вид объединения фазы слияния – разбиения можно изобразить, как показано на рис. 3.

Входной массив

Выходной массив

_rV

_К^

_h

/

Слияние

_V.

/

_{J ч.}

/

_j

Разбиение

Рис. 3 Сортировка двух массивов методом простого слияния

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

Процедуру можно упростить, объединив оба массива в один – двойной длины:

A : array [1..2*N] of item;

Пусть индексы i, j указывают два исходных элемента, k, l – два места пересылки. Исходные данные – эле­менты A[1], ... , A[N]. Введем булеву переменную up для указания направления пересылки данных:

up = true – на текущем проходе компоненты A[1], ..., A[N] пере­сылаются "вверх" – в переменные A[N+1], ..., A[2*N] (A[1], ..., A[N] → A[N+1], ..., A[2*N])

up = false – пересылка "вниз" – A[N+1], ..., A[2*N] пересылаются в A[1], ..., A[N]. (A[N+1], ..., A[2*N] → A[1], ..., A[N])

Значение up меняется после каждого прохода.

Кроме того, введем переменную P для длины сливаемых подпоследовательностей. Ее начальное значение

P = 1 и удваивается перед каждым очередным проходом. Для простоты считаем, что N всегда степень двойки. Тогда первая версия программы простого слияния:

PROCEDURE MERGESORT; VAR I, J, K, L, P: INTEGER;

UP: BOOLEAN; BEGIN

UP := TRUE; P := 1;

REPEAT { инициализация индексов }

IF UP THEN

BEGIN I :=1; J :=N; K :=N+1; L :=2*N END ELSE BEGIN K :=1; L :=N; I :=N+1; J:=2*N END; { П.1 - слияние Р-наборов последовательностей I, J в последовательности K, L } UP := NOT UP; P := 2 * P UNTIL P = N; END;

Уточним П.1. Этот проход, обрабатывающий N элементов, состоит из последовательных слияний Р-наборов. После каждого слияния направление пересылки переключается из нижнего в верхний конец выходно­го массива или наоборот (для обеспечения одинакового распределения в обоих направлениях).

Если сливаемые элементы посылаются в нижний конец массива, то индексом пересылки служит k, и k уве­личивается на 1 после каждой пересылки, если в верхний конец массива, то l уменьшается на 1 после каждой пересылки.

Можно упростить операцию слияния, если считать, что место пересылки всегда обозначается через k и бу­дем менять местами k и l после слияния каждого Р-набора. Приращение индекса обозначим через h, где h = 1 или h = -1.

Теперь получим П.1:

H :=1; M := N; REPEAT

Q := P; R := P; M := M - 2 * P;

{ П. 1.1 слияние Q элементов из I и R элементов из J, индекс засылки есть К с приращением H }

H := -H;

{ П. 1.2 обмен значениями K и L; } UNTIL M = 0;

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

WHILE ( Q <> 0 ) AND ( R <> 0 ) DO BEGIN { выбор элемента из I или J }

IF A[I].KEY < A[J].KEY THEN BEGIN { п. 1.1.1 -пересылка элемента из I в K, увеличение I и K; }

Q := Q - 1 END ELSE BEGIN

{ п. 1.1.2 - пересылка элемента из J в K, увеличение J и K; }

R := R - 1; END END;

{ п. 1.1.3. копирование остатка последовательности I; } { п. 1.1.4. копирование остатка последовательности J; }

Детализация пп.1.1.1 и 1.1.2 не требуется; пп. 1.1.3 и 1.1.4 детализируем в процессе записи всей програм­мы; п. 1.2 - тоже.

Перед записью попытаемся устранить ограничение на N (степень двойки). В общем случае будем продол­жать слияние Р-наборов, пока длина остатков входных последовательностей не станет меньше Р. Это влияет на ту часть алгоритма, где определяются значения Q и R - длины последовательностей, которые предстоит слить. Тогда вместо трех операторов

Q := Р; R := Р; М :=М - 2 * Р; используем четыре оператора

IF М >= Р THEN Q := Р ELSE Q := М; М := М - Q;

IF М >= Р THEN R := Р ELSE R := М; М := М - R; М обозначает общее число элементов в двух входных последовательностях, которые сливаются.

Наконец, чтобы обеспечить окончание работы программы, нужно заменить условие Р = N, управляющее внешним циклом, на Р >= N.

Теперь запишем весь алгоритм.

PROCEDURE MERGESORT;

VAR I, J, К, L, Т, Н, М, Р, Q, R: INTEGER;

UP: BOOLEAN; BEGIN UP := TRUE; P := 1; REPEAT H := 1; M := N;

IF UP THEN

BEGIN I := 1; J := N; К := N + 1; L := 2 * N END

ELSE К := 1; L := N; I := N + 1; J := 2 * N END;

REPEAT {}

{}

IF M >= P THEN Q := P ELSE Q := M; M := M - Q;

IF M >= P THEN R := P ELSE R := M; M := M - R;

WHILE ( Q <> 0 ) AND ( R <> 0 ) DO

BEGIN

IF A[I].KEY < A[J].KEY THEN BEGIN

A[K] := A[I]; К := К + H; I := I + 1; Q := Q - 1

END ELSE BEGIN

A[K] := A[J]; К := К + H; J := J + 1; R := R - 1 END

END;

{ копирование остатка серии из j }

WHILE R <> 0 DO BEGIN

A[K] := A[J]; К := К + H; J := J - 1; R := R - 1

END;

{ копирование остатка серии из I }

WHILE Q <> 0 DO BEGIN

A[K] := A[I]; К := К + H; I := I - 1; Q := Q - 1

END;

H := -H; T := К; К := L; L := T

UNTIL M = 0;

UP := NOT UP; P := 2 * P; UNTIL P >= N; IF NOT UP THEN

FOR I := 1 TO N DO A[I] := A[I+N]; END;

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

Поскольку на каждом проходе длина подпоследовательности Р удваивается и сортировка заканчивается, как только Р >= N, она требует \\og₂ Nl проходов. При каждом проходе (по определению) все множество из N элементов копируется ровно один раз. Следовательно, общее число пересылок равно М = N * \\og₂ N~|. Число сравнений С ключей еще меньше, т.к. при копировании остатка последовательности сравнения не производят­ся. Но это не слишком важно, поскольку основное время при работе с внешними устройствами тратится на пересылки (оно на несколько порядков выше, чем время, затрачиваемое на сравнения).

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

Естественное слияние

Алгоритм простого слияния никак не реагирует на то обстоятельство, что данные могут быть уже частич­но упорядочены. На k-м проходе длина всех сливаемых подпоследовательностей меньше или равна 2^к без учета того, что более длинные подпоследовательности уже могут быть упорядочены и их можно было бы сливать. Т.е. можно было бы сразу сливать последовательности длиной да и п в одну последовательность из да + и элементов.

Метод сортировки, при котором каждый раз сливаются две самые длинные возможные подпоследователь­ности, называется естественным слиянием.

Будем называть подпоследовательность G., ..., G ., такую, что G_k < й^₊₁ для к = i,...,J—\,

Я._! > Cl_i, а . > a_J+1, максимальной серией или просто серией. Таким образом сортировка естественным

слиянием сливает не последовательности заранее заданной длины, а максимальные серии. При слиянии двух последовательностей, каждая из которых содержит N серий, возникает одна последовательность, содержащая ровно N серий. Таким образом на каждом проходе общее число серий уменьшается вдвое, и число необходи­мых пересылок элементов в худшем случае равно N * l~log₂ N~|, а в обычном случае даже меньше. Число срав­нений, однако, намного больше, т.к. кроме сравнений, необходимых для упорядочения элементов, требуются еще сравнения соседних элементов каждого файла для определения концов серии.

Рассмотрим теперь алгоритм естественного слияния применительно к последовательному файлу.

Пусть исходная последовательность задана в виде файла С, который в конце работы должен содержать ре­зультат сортировки. Используются два вспомогательных файла А и В. Каждый проход состоит из фазы распре­деления, которая распределяет серии поровну из С в А и В, и фазы слияния, которая сливает серии из А и В в С (рис. 4).

AA A

1-й проход 2-й проход n-й проход

Рис. 4 Фазы сортировки и проходы сортировки

Поэтому алгоритм представляет собой несбалансированную двухфазную трехленточную (трехфайло-вую) сортировку слиянием.

Пример. Файл из 20 чисел.

Исход­ный файл	17 31' 5 59' 13 41 43 67' 11 23 29 47' 3 7 71' 2 19 57' 37 61
после 1-го	5 17 31' 59' 11 13 23 29 41 43 47 67' 2 3 7 19 57 71' 37 61
после 2-го	5 11 13 17 23 29 31 41 43 47 59 67' 2 3 7 19 37 57 61 71
после 3-го прохо­дов	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 57 59 61 67 71

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

Пусть L - переменная для подсчета количества серий в С. Определим глобальные объекты:

TYPE TAPE = FILE OF ITEM; VAR C : TAPE;

Тогда программу можно оформить следующим образом:

PROCEDURE NATURALMERGE; VAR L : INTEGER;

A, B : TAPE; BEGIN REPEAT

REWRITE (A); REWRITE (B); RESET (C);

DISTRIBUTE; { распределение }

RESET (A); RESET (B); REWRITE (C);

L := 0;

MERGE; { слияние }

UNIT L = 1 END;

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

PROCEDURE DISTRIBUTE; { из с в а и в }

BEGIN

REPEAT

COPYRUN (C, A); { переписывание серии }

IF NOT EOF ( C ) THEN COPYRUN (C, B) UNTIL EOF ( C ) END;

PROCEDURE MERGE; { из а и в в с }

BEGIN

REPEAT

MERGERUN; { слияние двух серий }

L := L + 1 UNTIL EOF (B); IF NOT EOF (A) THEN BEGIN

COPYRUN (A, C); L := L + 1 END END;

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

Подчиненные процедуры mergerun и copyrun требуют введения глобальной булевой переменной EOR (end of the run), значение которой показывает, достигнут ли конец серии.

PROCEDURE COPYRUN (VAR X, Y : TAPE);

BEGIN { перепись одной серии из х в y }

REPEAT

COPY(X, Y) { перепись одного элемента }

UNTIL EOR { конец серии }

END;

Вторая подчиненная процедура

PROCEDURE MERGERUN;

BEGIN { слияние двух серий из а и в в с }

REPEAT

IF A^.KEY < B^.KEY THEN BEGIN COPY (A, C);

IF EOR THEN COPYRUN (B, C) END ELSE BEGIN COPY (B, C);

IF EOR THEN COPYRUN (A, C) END UNTIL EOR END;

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

Подчиненная процедура copy пересылает элемент файла Х в файл Y и определяет, достигнут ли конец се­рии. Для этого нужно сохранить ключ последнего прочитанного (переписанного) элемента, чтобы сравнить его со следующим. Это "заглядывание вперед" достигается использованием буферной переменной файла X↑.

PROCEDURE COPY (VAR X, Y : TAPE);

VAR BUF : ITEM;

BEGIN

READ (X, BUF); WRITE (Y, BUF);

IF EOF (X) THEN EOF := TRUE

ELSE EOF := BUF.KEY > X↑.KEY END;

На этом построение процедуры сортировки естественным слиянием закончено.

К сожалению, в некоторых случаях программа производит сортировку неправильно. Например, пусть ис­ходная последовательность:

3 2 5 11 7 13 19 17 32 31 29 37 43 41 47 59 57 61 71 67

Распределяя последовательные серии в А и В, получим:

А = 3' 7 13 19' 29 37 43' 57 61 71'

B = 2 5 11' 17 23 31' 41 47 59' 67

Эти последовательности легко сливаются в одну, после чего сортировка заканчивается. Пример показыва­ет, что простое распределение серий в два файла может дать меньшее число выходных серий, чем входных. Это происходит, когда первый элемент (i+2)-й серии больше последнего элемента i-й серии, что приведет к автома­тическому слиянию двух серий в одну. Поэтому действительные количества выходных серий в А и В могут сильно различаться. Однако наша процедура будет сливать пары серий и заканчиваться, как только будет про­читан один из файлов, теряя при этом остаток другого, например 17 19' 13 57' 23 29' 11 59' 31 37' 7 61' 41 43' 5 67' 47 71' 2 3 13 17 19 23 29 31 37 41 43 47 57 71' 11 59 11 13 17 19 23 29 31 37 41 43 47 57 59 71

Таким образом исходные данные сортируются (и усекаются) за два прохода.

Один из способов исправления - скорректировать операцию распределения так, чтобы число серий на лен­тах было одинаковым.

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

Во втором случае слияние:

PROCEDURE MERGE;

BEGIN

WHILE NOT EOF (A) AND NOT EOF (B) DO

BEGIN MERGERUN; L := L + 1;

END; WHILE NOT EOF (A) DO

BEGIN COPYRUN (A, C); L := L + 1;

END; WHILE NOT EOF (B) DO

BEGIN COPYRUN (B, C); L := L + 1;

END; END; Теперь объединить процедуры и написать вызывающую программу. Добавить печать.

Контрольные вопросы

1. Основные операции при работе с последовательными файлами.

2. Основное отличие сортировки на файле и в ОЗУ.

3. Сортировка последовательных файлов.

4. Сортировка последовательных файлов методом простого слияния.

5. Что такое фаза обработки данных?

6. Трудоемкость сортировки слиянием.

7. Сортировка последовательных файлов методом естественного слияния.

8. Отличие сбалансированного от несбалансированного слияния.