Реверсирование строк с помощью выбора
Программа SelectSort требует небольшой переделки чтобы стать программой для обращения строк. Единственная модификация, которая требуется – заменит DP 3.2.1 (которая выбирает минимальный из 1) на раздел, который может быть обозначен следующим комментарием:
{Выбрать последний символ в F1,
копировать остаток в F2}
Также в данном случае имеет смысл переименовать переменную Min в Last, чтобы название переменной соответствовало ее использованию в программе.
Повышение быстродействия SelectSort и SelectReverce
Скорость SelectSort и SelectReverce может быть увеличена примерно вдвое, если использовать F1 и F2 симметрично. Выбирать символ из F1 и копировать остаток в F2, затем выбирать символ из F2 и копировать остаток в F1 и т.д. Для того, чтобы определить, из какого файла читать и в какой копировать потребуется переключатель even/odd (четное/нечетное).
На самом деле, существует еще один способ ускорения SelectSort. Мы можем использовать внутренние переменные для того, чтобы хранить не один текущий минимум, а несколько на один проход. Например, с переменными Min1, Min2, Min3, Min4, Min5 пять минимальных хначений может быть найдено и выведено за один проход. Таким образом мы можем ускорить SelectSort примерно в 5 раз.
Используя оба приведенных приема, например с 10 переменными для хранения локальных минимумов и симметричного использования файлов, мы можем увеличить скорость работы программы в 20 раз, т.е. сократить время работы программы, например с 3 часов до 10 минут.
Маркеры текстовых файлов
Текстовые файлы Паскаля организованы в строки и существует способ определения границ строк и конца файла. Это маркеры конца строки, которые появляются в виде одного или двух пробелов в конце каждой строки. Используя введенный нами маркер конца входной последовательности # и располагая данные в одну строку, мы могли игнорировать реальную структуру входного файла. Но если входной файл будет содержать маркеры конца строки или там будет отсутствовать символ #, наши программы не будут работать корректно.
Маркер конца строки
Мы использовали в таблицах выполнения символ / чтобы обозначать маркер конца строки, который не является печатным символом. Мы не использовали в наших программах выражения вида WRITELN(‘/’) чтобы избежать путаницы.
На самом деле, Паскаль-машина в качестве маркера конца строки использует не символ /, а некий специальный символ, который не имеет визуального отображения. Этот символ помещается в конец строки всякий раз, когда выполняется выражение WRITELN.
Но что происходит при чтении маркера конца строки? Рассмотрим следующий код:
REWRITE(F1);
WRITE(F1, ‘#’);
WRITELN(F1);
RESET(F1);
READ(F1, Ch1);
READ(F1, Ch2);
В Ch1 будет помещен символ #, а Ch2 будет иметь значение пробела, как печатного эквивалента символа маркера конца строки.
Если границы строк должны контролироваться программой, необходимо иметь возможность определять их. Не имеет смысла проверять, является ли каждый считанный символ пробелом, на который был заменен маркер конца строки, поскольку пробелы встречаются внутри строк.
В Паскале имеется стандартное слово EOLN, которое может быть использовано как <условие> для проверки маркера конца строки который может быть считан при следующей операции READ. Когда в INPUT в позиции курсора находится маркер конца строки, EOLN принимает значение TRUE, в противном случае EOLN принимает значение FALSE. Аналогичное справедливо для текстовых файлов. При чтении файла F1 EOLN(F1) вернет TRUE, если в позиции курсора находится маркер конца строки.
Предположим, F1 содержит одну строку, в которой имеется один символ A, законченную маркером конца строки. Вот таблица выполнения, которая иллюстрирует поведение EOLN.
| После выполнения | F1 | EOLN(F1) | Ch1 | Ch2 |
| RESET(F1) READ(F1, Ch1) READ(F1, Ch2) | A/ A/ A/_ | FALSE TRUE ? | ? A A | ? ? □ |
С помощью символа □ мы явно указываем символ пробела. Значение ? которое принимает EOLN(F1) после того как считан маркер конца строки, означает, что значение EOLN не определено когда в файле нет больше входных символов. Большинство реализаций Паскаль-машины что-то возвращают в этом случае, но на этот счет не существует какого-либо соглашения или стандарта, поэтому не стоит полагаться на это при разработке программ, поэтому EOLN не может быть использован, когда входная последовательность прочитана полностью.
Маркер конца файла
В Паскале имеется стандартное условие EOF, которое позволяет узнать, есть ли возможность считать еще какие-то данные из файла. EOF принимает значение TRUE, если курсор находится за последним элементом данных (например за маркером конца последней строки в текстовом файле), в иных случаях EOF принимает значение FALSE. Для файла F1 условие записывается как EOF(F1). Например, если F1 содержит одну строку, EOF будет принимать следующие значения:
| Ch | F1 | EOF | |
| READ(Ch) READ(Ch) | ? A ¨ | A/ A/ A/_ | FALSE FALSE TRUE |
Необходимо заметить, что различные реализации Паскаль-машины по разному интерпретируют символ конца строки и стоящие перед ним пробелы. Некоторые реализации, например, удаляют все пробелы, которые встречаются между последним не пробелом и концом строки, символ конца строки также может заменяться или не заменяться на пробел.
Таким образом мы не вполне можем контролировать эту ситуацию, в зависимости от реализации Паскаль-машины, пробелы в конце строки могут пропадать или наоборот появляться.
SR23
<условие> ::= <выражение> <оператор сравнения> <выражение>
| NOT (<уcловие>)
| (<уcловие>) AND (<уcловие>)
| (<уcловие>) OR (<уcловие>)
| EOF
| EOF (<идентификатор>)
| EOLN
| EOLN (<идентификатор>)
CR6
Идентификатором типа TEXT является <идентификатор> описанный в разделе объявлений имеющий <тип> TEXT. Если идентификатор типа TEXT появляется в <выражении WRITE> или в <выражении READ>, он должен стоять первым в <списке идентификаторов> или <списке вывода>. Идентификатор типа TEXT, иной чем INPUT или OUTPUT должен быть описан в <объявлениях>. Только идентификаторы типа TEXT, исключая INPUT и OUTPUT, могут появляться внутри выражений RESET и REWRITE. Только идентификаторы типа TEXT, к которым было применено выражение RESET, могут появляться в <условиях> EOF и EOLN.
Копирование строк
Когда INPUT содержит набор строк, для перемещения через границу строки может использоваться выражение READLN. В результате выполнения выражения READLN , курсор будет перемещен за ближайший маркер конца строки. Если маркер конца строки не встретится, READLN возвратит ошибку. READLN (F1) будет выполняться для файла F1.
READLN(Ch1, Ch2, Ch3)
Будет эквивалентно
READ(Ch1);
READ(Ch2);
READ(Ch3);
READLN
SR12.
<выражение READ> ::= READ(<список идентификаторов>)
| RESET(<идентификатор>)
| READLN(<список идентификаторов>)
Значение условий EOLN и EOF и поведение выражений READ и READLN определены только для ситуаций, когда они выполняются до прохождения соответствующих их границ. Например значение EOF не определено за границами файла. Поэтому важно правильно использовать операторы чтения файла и определения границ, например по шаблону, предлагаемому следующей программой:
PROGRAM CopyLines (INPUT, OUTPUT);
{Копирует INPUT в OUTPUT сохраняя структуру строк}
VAR
Ch: CHAR;
BEGIN {CopyLines}
WHILE NOT EOF
DO
BEGIN {Копировать одну строку}
WHILE NOT EOLN
DO
BEGIN {Копировать один символ}
READ(Ch);
WRITE(Ch);
END;
READLN;
WRITELN
END
END. {CopyLines}
Внешнее выражение WHILE защищает внутренний код от ситуации выхода за конец файла. Внутреннее выражение WHILE защищает его оператор READ от чтения маркера конца строки. После того как внутренний WHILE скопировал строку, с помощью READLN курсор перемещается за маркер конца строки, а в OUTPUT создается маркер конца строки с помощью WRITELN. Детали в следующей таблице выполнения:
| Ch | INPUT | EOF | EOLN | OUTPUT | |
| WHILE NOT EOF WHILE NOT EOLN READ(Ch) WRITE(Ch) WHILE NOT EOLN READLN WRITELN WHILE NOT EOF WHILE NOT EOLN READ(Ch) WRITE(Ch) WHILE NOT EOLN READLN WRITELN WHILE NOT EOF | ? A B | A/B/ A/B/ A/B/ A/B/ A/B/_ | FALSE FALSE FALSE FALSE TRUE | FALSE TRUE FLASE TRUE ? | _ A_ A/_ A/B_ A/B/_ |
Ранее мы использовали в качестве маркера конца последовательности символ # и копирование файлов выполняли по примерно следующему образцу:
READ(F1, Ch);
WHILE Ch <> ‘#’
DO
BEGIN
WRITE(F2, Ch);
READ(F1, Ch)
END
Если мы используем маркер конца строки, то получаем следующий образец:
WHILE NOT EOLN(F1)
DO
BEGIN
READ(F1, Ch)
WRITE(F2, Ch);
END
Второй вариант более соответствует структуре текстовых файлов и более естественно реализует операцию копирования.
BubleSort
SelectSort сортируя файлы длины N выполянет порядка 2N2 выражений READ/WRITE. Возможна ли более быстрая сортировка? IFSort и MinSort достаточно эффективны при сортировке строк фиксированной длины, делая работу в один проход и выполняя порядка 2N выражений READ/WRITE. Поскольку 2N2 всегда больше 2N при всех N > 1, вероятно существуют пути сортировать быстрее чем SelectSort. Новый алгоритм сортировки также нам позволит попрактиковаться в работе с границами файлов с помощь EOF.
Если INPUT уже отсортирован, SelectSort все равно потребует 2N2 выражений READ/WRITE. Это наблюдение предлагает нам сделать проверку, не имеем ли мы дело с уже отсортированными данными.
BEGIN {Проверяем F1 на отсортированность}
Sorted := ‘Y’;
RESET(F1);
IF NOT EOLN(F1)
THEN
BEGIN
READ(F1, Ch1);
WHILE NOT EOLN(F1)
DO
BEGIN
READ(F1, Ch1);
IF Ch2 < Ch1
THEN
Sorted := ‘N”;
Ch1 := Ch2;
END
END
END
Программа перемещает по файлу окно в два символа и если в файле есть фрагмент, который не отсортирован, Sorted будет присвоено ‘N’. Почему бы не использовать этот эффект для сортировки?
F1 копируется в F2, но когда Ch2 < Ch1, эти два символа копируются в F2 в обратном порядке. Таким образом, после некоторого количества проходов по файлу не останется пар символов стоящим в обратном порядке.
Эта идея послужила основой для алгоритма BubleSort, названного так, потому что изменение позиций сортируемых символов напоминает всплывание пузырьков.
DP4
PROGRAM BubbleSort(INPUT,OUTPUT);
{Сортирует первую строку INPUT в OUTPUT}
VAR
Sorted, Ch, Ch1, Ch2: CHAR;
F1, F2: TEXT;
BEGIN {BubbleSort}
{Копируем INPUT в F1}
Sorted := 'N';
WHILE Sorted ='N'
DO
BEGIN
{Копируем F1 в F2,проверяя отсортированность
и переставляя первые соседнии символы по порядку}
{Копируем F2 в F1}
END;
{Копируем F1 в OUTPUT}
END.{BubbleSort}
DP 4.1
BEGIN { Копируем F1 в F2,проверяя отсортированность
и переставляя первые соседнии символы по порядку}
Sorted := 'Y';
RESET(F1);
REWRITE(F2);
IF NOT EOF(F1)
THEN
BEGIN
READ(F1, Ch1);
WHILE NOT EOLN(F1)
DO { По крайней мере два символа остается для Ch1,Ch2 }
BEGIN
READ(F1, Ch2);
{ Выводим min(Ch1, Ch2) в F2, записывая
отсортированные символы }
END;
WRITELN(F2, Ch1) { Выводим последний символ в F2 }
END
END
DP 4.1.1
{ Выводим min(Ch1, Ch2) в F2, записывая
отсортированные символы }
IF Ch1 <= Ch2
THEN
BEGIN
WRITE(F2,Ch1);
Ch1 := Ch2
END
ELSE
BEGIN
WRITE(F2, Ch2);
Sorted := 'N'
END
DP4.2
BEGIN { Копируем INPUT в F1 }
REWRITE(F1);
WHILE NOT EOLN
DO
BEGIN
READ(Ch);
WRITE(F1, Ch);
END;
WRITELN(F1)
END;
Разделы
DP4.4 { Копируем F2 в F1 } и DP4.3 { Копируем F1 в OUTPUT }
выполняются аналогично DP 4.2
Проанализируем трудоемкость алгоритма. Допустим для файла длины N минимальный элемент данных находится в позиции m.
В процессе сортировки этот элемент перемещается на первую позицию в файле за m итераций. В случае если он расположен на последней позиции, потребуется N итераций. Аналогично с остальными элементами. Таким образом, максимальное количество итераций для BubbleSort может составить N2 (как минимум N). Реально количество проходов для упорядочивания одного символа будет определяться максимальной дистанцией любого символа в INPUT от его окончательного расположения. В случае с фалами со случайно размещенными символами, это число будет составлять значительную долю от N, и общее количество итераций будет также составлять значительную долю от N2.
Является ли BubbleSort более быстрым алгоритмом сортировки, чем SelectSort? При работе с последовательностями близкими к отсортированным – да. В случае с фалами со случайно размещенными символами, BubbleSort не будет иметь значительных преимуществ перед SelectSort.
Заключение
Переменные CF Pascal могут принимать значения, которые представлены одним символом или последовательностью символов (файл) в зависимости от того, объявлены они как CHAR или TEXT. Переменные типа TEXT позволяют организовать хранение данных практически неограниченного размера. Но для работы с файловыми переменными требуется жесткая дисциплина. Они должны быть подготовлены к записи с помощью выражения REWRITE и закрыты с помощью выражения WRITELN, подготовлены для чтения с помощью выражения RESET. Символы считываются из файла точно в том порядке, в каком они были записаны.
SelectSort – программа сортировки общего назначения, которая может сортировать файлы неограниченного размера. Но программы из семейства MinSort c ограниченной функциональностью рассмотренные в части 3 работают быстрее. Программа BubbleSort, но ее скорость нестабильна и зависит от сортируемых данных. В некоторых случаях она работает эффективнее, чем SelectSort, в других – примерно также.
Для хорошего тестирования программ необходимы знания о слабых местах программы. Наилучшие тесты, направленные на исследование сомнительных мест, чтобы с их помощью заручиться уверенностью что идеи, заложенные в проект программы, работают, и при разработке не было сделано ошибок. Но подготовить тесты идеально исследующие программу крайне сложно, поэтому на практике используются некоторые систематические формы тестирования, которые также бывают полезны и не требуют большой изобретательности. Метод структурированного тестирования требует, чтобы тест был подготовлен таким образом, чтобы каждая строка программы выполнилась как минимум один раз.
Текстовые файлы могут быть организованы в строки, границы строк могут быть обработаны с помощью выражений EOLN – определение границы строки; READLN – для перемещения курсора за маркер конца строки, WRITELN – для записи маркера конца строки. Конец данных в файле может быть определен с помощью оператора EOF. Схема процедуры чтения или копирования файла значительно проще, когда используются естественные маркеры конца файла и функции EOLN и EOF, чем искусственно введенный символ конца последовательности #.