 |
CheckIfSorted(Txt, Sorted)
|
|
|
|
Процедура CheckIfSorted устанавливает Sorted в ‘Y’, если в файле существует только одна серия (т.е. если за первым встреченным символом # сразу же следует символ конца строки).
Design Part 2.3
PROCEDURE CheckIfSorted(VAR FileIn: TEXT; VAR Sorted: Char);
{присвоить переменной Sorted значение ‘Y’ если Txt отсортирован, иначе - ‘N’ }
VAR
Ch, EndRun: CHAR;
BEGIN {CheckIfSorted}
RESET(FileIn);
IF EOLN(FileIn)
THEN {пустой файл отсортирован по определению}
Sorted:= ‘Y’
ELSE
{установить Sorted=’Y’, если в файле есть всего одна серия, и ‘N’ в противном случае}
END {CheckIfSorted}
И, наконец, для того, чтобы начать процесс разделения-слияния, Txt разделяется на односимвольные серии, разделенные символом #. С этой целью мы добавляем новую переменную Ch символьного типа к локальным переменным процедуры MergeSort1.
Design Part 2.4
BEGIN {разделить n символов в Txt на n серий единичной длины, разделенные символом ‘ #’ }
...
END
На этом процедура MergeSort1 будет закончена.
Задание 13. Проведите сборку процедуры MergeSort1, написав самостоятельно недостающие разделы проекта.
(20 баллов)
Задание 14. Составьте набор тестовых данных, которые бы структурными тестами следующих частей программы:
а) MergeRuns
б) SplitIntoRuns
в) CheckIfSorted
г) MergeSort1
(10 баллов за каждое подзадание)
Задание 15. Часть г) предыдущего упражнения включает в себя все остальные части. Какое преимущество в тестировании их по отдельности, если, в конце концов, они будут протестированы вместе?
(10 баллов)
Задание 16. Дайте формальное доказательство того, что CheckIfSorted делает то, что должна делать.
(20 баллов)
Задание 18. Рассмотрите разделение и слияние серий на три файла вместо двух.
а) Объясните, как процедура, подобная MergeSort1 будет сортировать с использованием трех файлов.
|
|
|
б) Объясните, почему такая сортировка будет быстрее, показав на примере.
в) Повторите пункт b) для четырех файлов.
(15 баллов за каждое подзадание)
Задание 19. Придумайте быстрый способ реверсирования файла, рассмотрев в качестве примера файл, отсортированный в обратном порядке и рассмотрите его сортировку при помощи MergeSort1. Используя этот пример, разработайте проект для реверсирования произвольного файла путем разделения и слияния.
(40 баллов)
Задание 20. Модифицируйте MergeSort1 таким образом, чтобы получить преимущество от серий, существующих в изначальной строке еще до сортировки, и от серий, которые могут случайно образоваться во время каждой склейки. Как может это помочь при сортировке строк, символы которых расположены в случайном порядке.
(20 баллов)
Задание 21. Модифицируйте процедуру MergeSort1 так, чтобы ее действие оставалось прежним, но скройте информацию о том, что она сравнивает символы. Сделайте это, путем замещения всех прямых символьных операций типа:
if Ch1 < Ch2 …
на операторы вызова процедуры:
BEGIN
Compare(Ch1, Ch2, Result);
IF Result = ‘<’ …
END
Текст этих процедур будет тривиальным. (Такое изменение программы, чтобы она вела себя по-прежнему, но использовала структуру, легко приспосабливаемую к будущим изменениям, называется профилактическим. См. следующие 2 задания).
(15 баллов)
Задание 22. Измените MergeSort1 таким образом, чтобы она сортировала слова вместо символов. Используйте схему предыдущего упражнения, но теперь напишите процедуры, которые вы бы вставили с соответствующими аргументами типа TEXT в качестве слов.
(20 баллов)
Задание 23. Измените MergeSort1 таким образом, чтобы она сортировала строки вместо символов (см. предыдущее упражнение).
(20 баллов)
10.3 Улучшение MergeSort.
Процедура MergeSort демонстрирует гораздо лучший алгоритм сортировки, нежели SelectSort, но она может быть еще улучшена, чтобы получить преимущество от случайно возникающих серий.
|
|
|
Каждый раз после выполнения MergeSort размер каждой серии удваивается. Таблица показывает размеры серий после каждого выполнения процедуры MergeRuns:
| Слияние | Размер серии |
| k | 2k |
Txt считается отсортированным в том случае, когда в нем остается всего одна серия. Для n символов это произойдет, когда выполнены будет k слияний, а 2k>=n. Поскольку при каждом слиянии необходимо прочитать и записать все n символов файла и необходимы k слияний, то количество операций чтения и записи, выполняемых этой программой – n * log2n. Интересно сравнить MergeSort с SelectSort, которая сортирует файл длиной m символов за m*m операций чтения/записи. Чтобы сравнение было честным, предположим, что SelectSort работает с файлом длиной n, а MegreSort1 работает с файлом длиной 2n (процедура MergeSort изначально удваивает размер файла за счет маркеров #. Количество таких маркеров уменьшается по ходу выполнения сортировки, но принятие длины равной 2n – более чем честно по сравнению с SelectSort). Результаты сравнения показаны в таблице:
| Длина файла n | Количество операций чтения/записи | |
| SelectSort n2 | MergeSort 2n * long22n | |
| 10 000 | 1 520 | |
| 1 000 000 | 22 000 | |
| 100 000 000 | 840 000 |
MergeSort1 может быть улучшена с использованием преимущества частей файла, который уже отсортированы. С меньшим количеством более длинных серий, потребуется меньше вызовов процедуры MergeRuns/ Конечно, если файл изначально был отсортирован в обратном порядке, все серии будут иметь длину 1 символ, но этот случай будет происходить очень редко. Маркеры серий теперь уже не являются необходимыми, поскольку на границе серий предыдущий считанный символ будет больше, чем следующий.
Пример улучшенной сортировки показан ниже. Точки показаны лишь для пометки границы серий, и в действительности не существуют.
| Шаг | Разделенные строки | Склеенные строки | |
| wrcaot | |||
| Разделение | w·c | r·aot | |
| Слияние | rw·acot | ||
| Разделение | rw | acot | |
| Слияние | acortw |
Первое разделение сохранило серию aot, потому что эти символы уже находятся в порядке возрастания. В результате понадобилось только две операции слияния вместо трех.
|
|
|
Довольно трудно проанализировать эффект от использования естественных серий в склеенных файлов, потому что прирост зависит от того, как отклоняются серии от худшего случая – от файла отсортированного в обратном порядке. Однако, даже в худшем случае количество операций чтения/записи уменьшится с 2n*log22n до n*log2n, что примерно в 6 раз лучше при n = 1000. Проект улучшенной процедуры MergeSort2, использующей существующие серии практически тот же самый, что и для MergeSort1, за исключением того, что не нужно больше вставлять маркеры #:
Design Part 3
PROCEDURE MergeSort2(VAR Txt: TEXT);
VAR
Temp1, Temp2: TEXT;
Sorted: CHAR;
BEGIN
CheckIfSorted(Txt, Sorted);
WHILE Sorted = ‘N’
DO
BEGIN
SplitIntoRuns(Txt, Temp1, Temp2);
MergeRuns(Temp1, Temp2, Txt);
CheckIfSorted(Txt, Sorted)
END
END
Каждый раздел проекта процедуры MergeSort может быть повторно использована (они пронумерованы соответственно номерам из раздела 10.2).
Раздел проекта 2.2.1 должна быть модифицирована для обеспечения нового метода копирования серий попеременно в Result1 и Result2. Путем прохождения двухсимвольного окна (LastCh и Ch) по файлу FileIn, конец одной серии и начало другой встречается тогда, когда значению LastCh предшествует значению Ch.
Design Part 3.2.1
BEGIN {копируем серии попмременно в Result1 и Result2}
Switch:= ‘1’;
Ch:= ‘#’;
WHILE NOT EOLN(FileIn)
DO
BEGIN
LastCh:= Ch;
READ(FileIn, Ch);
{если конец серии, то переключаем переменную Switch на другой файл};
{копируем Ch в Result1, если Switch=’1’, в противном случае – в Result2}
END
END
В переменную Ch заносится произвольное значение # до входа в цикл WHILE, так что окно существует уже при встрече первого символа.
Слияние серий является более сложным, чем их разделение, поскольку они больше не отмечены явно. Если первый символ следующей серии файла меньше чем оставшиеся символы текущей серии другого файла, то границы серии могут быть нарушены. Решением этой проблемы будет продолжение считывания символов из той же серии так долго, насколько это возможно. Если последний добавленный символ к склеенной серии меньше любого из символов в голове склеиваемых серий, то обе серии все еще содержат символы для обработки. Однако, если этот символ больше, чем один символ в голове одной серии (но не другой), то первая серия закончилась, а вторая еще содержит символы для обработки. В качестве примера рассмотрим подробно результаты первой операции слияния:
|
|
|
| Шаг | Разделенные строки | Склеенные строки | |
| wrcaot | |||
| Разделение | w·c | r·aot | |
| Слияние | |||
| w·c | aot | r | |
| c | aot | rw | |
| c | ot | rw·a | |
| ot | rw·ac | ||
| … |
После первого шага слияния символ r, добавленный к склеенной строке меньше, чем w первой разделенной строки, поэтому эта серия еще не была закончена; однако r больше, чем a второй разделенной строки, поэтому серия во второй строке уже окончена.
Более систематический анализ этой ситуации может быть совершен с использованием таблицы анализа отношений между последним символом, добавленным к склеиваемой серии m, следующим символом s в Temp1 и следующим символом t в Temp2.
| s < t | s ≥ t | |
| m ≤ s m ≤ t | t > s ≥ m обе серии продолжаются следующий символ – в Temp1 | s ≥ t ≥ m обе серии продолжаются следующий символ – в Temp2 |
| m ≤ s m > t | t > s ≥ m > t невозможное условие | s ≥ m > t серия в Temp2 закончилась следующий символ – в Temp1 |
| m > s m ≤ t | t ≥ m > s серия в Temp1 закончилась следующий символ – в Temp2 | s ≥ t ≥ m > s невозможное условие |
| m > s m > t | m > t > s обе серии закончились следующий символ – в Temp1 | m > s ≥ t обе серии закончились следующий символ – в Temp2 |
Этот анализ приводит нас к измененному проекту процедуры MergeRuns. Наиболее очевидное изменение в том что символ Ch должен быть инициализирован меньшим значением из In1 и In2, так чтобы могли быть применены проверки.
Design part 3.1
PROCEDURE MergeRuns(VAR In1, In2, Result: TEXT);
{объединяем серии из In1 и In2 в Result}
VAR
Ch, Ch1, Choice: CHAR;
BEGIN {MergeRuns}
{инициализируем параметры файлов}
READ(In1, Ch1);
READ(In2, Ch2);
{если ни один из файлов In1 и In2 не пустой, то Ch:= min(Ch1, Ch2)};
WHILE NOT EOF(In1) AND NOT EOF(In2)
DO
BEGIN {объединяем серии из In1 и In2 в Result}
{устанавливаем в переменной Choice значение ‘1’ для чтения из In1
‘2’ – для чтения из In2};
{Заменяем Ch переменной Ch1 либо Ch2 в зависимости от значения Choice и получаем
новое значение для переменной Ch1 либо Ch2}
END;
{копируем последнюю серию из In1 либо In2 в Result};
{сбрасываем параметры файлов}
END {MergeRuns}
Design Part 3.1.5
BEGIN {если ни один из файлов In1 и In2 не пустой, то Ch:= min(Ch1, Ch2)}
...
END
Design Part 3.1.1
BEGIN {устанавливаем в переменной Choice значение ‘1’ для чтения из In1 ‘2’ – для чтения из In2}
...
END
Design Part 3.1.2
BEGIN {Заменяем Ch переменной Ch1 либо Ch2 в зависимости от значения Choice и получаем
новое значение для переменной Ch1 либо Ch2}
|
|
|
...
END
Design Part 3.1.3
BEGIN {копируем последнюю серию из In1 либо In2 в Result}
IF NOT EOF(In1)
THEN {копируем последнюю серию из In1 (если такая существует} в Result}
BEGIN
WRITE(Result, Ch1);
CopyOpen(In1, Result)
END
ELSE
BEGIN
WRITE(Result, Ch2);
CopyOpen(In2, Result)
END
END
Последнее, что осталось изменить – это процедуру CheckIfSorted, чтобы учесть тот файт, что символ # более не используется в качестве разделителя серий.
Design Part 3.3
PROCEDURE CheckIfSorted(VAR FileIn: TEXT; VAR Sorted: Char);
{устанавливаем Sorted в Y, если FileIn содержит одну серию и N в противном случае}
VAR
Ch, LastCh: CHAR;
BEGIN {CheckIfSorted}
RESET(FileIn);
Sorted:= ‘Y’;
IF NOT EOLN(FileIn)
THEN
READ (FileIn, LastCh);
WHILE NOT EOLN(FileIn) AND (Sorted = ‘y’)
DO
BEGIN
Read(FileIn, Ch);
IF Ch < LastCh
THEN
Sorted:= ‘N’;
LastCh:= ‘Ch’
END
END {CheckIfSorted}
Задание 24. Проведите сборку процедуры MergeSort2, написав недостающие разделы проекта.
(25 баллов)
Задание 25. В процедурах MergeSort1 и MergeSort2 есть несколько отличий между разделами проектов 2.1.2 и 3.1.3, которые играют очень похожую роль в различных версиях MergeRuns. Объясните причину этих отличий.
(15 баллов)
Задание 26. При анализе слияния естественных серий без граничных маркеров, была дана таблица для определения того, закончилась серия или нет, основанная на значениях символов считанных из разделенных файлов и только что добавленного символа. Докажите каждое утверждение из этой таблицы, относящееся к окончанию серий.
(30 баллов)
10.4 Резюме
Строки слов бросают программисту серьезный вызов. Хотя это очень простая структура строк и подстрок, при их обработке могут возникнуть задачи, которые для корректного решения требуют всей мощи хорошего проектирования и тщательного анализа.
Задача удаления лишних пробелов из файла была использована для демонстрации описания задачи с использованием BNF-нотации и метода раздельного тестирования, основанного на таком описании.
Сортировка путем разделения и слияния файлов является гораздо более эффективной техникой, нежели SelectSort. Она выполняет сортировку файла длины n за количество операций чтения-записи порядка n*log2n
|
|
|
