Работа со строками слов (стр. 6 )

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

Шаг	Разделенные строки	Склеенные строки
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
Слияние
1	w·c	aot	r
2	c	aot	rw
3	c	ot	rw·a
4	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