Сортировка и использованием циклического выполнения.

ТЕКСТОВЫЕ ФАЙЛЫ И ЦИКЛИЧЕСКОЕ ВЫПОЛНЕНИЕ

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

Текстовые файлы

Вводится новый тип данных CF Pascal, файл типа TEXT, он используется для хранения данных. Текстовые файлы могут хранить последовательности с любым количеством символов.

Новые идеи: файлы типа TEXT, использование файлов для хранения рабочих данных, REWRITE, RESET.

Операции над файлами.

INPUT и OUTPUT – стандартные идентификаторы именующие файлы которые можно читать и записывать; данные в этих файлах являются последовательностями символов.

В CF Pascal также есть переменные, данные которых являются последовательностями символов – файлы типа TEXT. Другое имя типа данных TEXT – FILE OF CHAR. Текстовые файлы могут быть созданы, туда можно записывать данные, считывать данные, они могут хранить несколько символов, чего не скажешь про переменные типа CHAR. Файлы описываются в разделе VAR c использованием стандартного слова TEXT. Например:

VAR

Ch: CHAR;

Chars: TEXT;

После того как переменная типа TEXT была создана, она должна быть приготовлена для записи с использованием выражения REWRITE, в данном случае:

REWRITE(Chars)

Или файл может быть приготовлен для чтения, возможно после записи данных, используя выражение RESET.

RESET(Chars)

Если для файла было выполнено выражение REWRITE и нет промежуточных выражений RESET, файл открыт для записи и выражения WRITE могут ссылаться на него, например:

WRITE(Chars, Ch, ‘#’);

WRITELN(Chars, Ch, Ch)

Если для файла было выполнено выражение RESET, без промежуточных выражений REWRITE, файл открыт для чтения и выражения READ могут ссылаться на него, например:

READ(Chars, Ch);

Чтение и запись файлов типа TEXT, объявленных в программе, во всех отношениях подобны чтению из INPUT и записи в OUTPUT. Значением файла открытого для чтения или записи может быть строка символов и курсор. Выражение REWRITE размещает курсор на первой позиции строки символов, где символы отсутствуют, аналогично OUTPUT после выполнения заголовка программы. Выражение RESET не изменяет данные файла и перемещает курсор в позицию первого символа, если таковой имеется, аналогично тому как инициализируется INPUT при выполнении заголовка программы.

OUTPUT всегда открыт для записи и может присутствовать в выражении WRITE. Выражения

WRITE(Ch)

и

WRITE(OUTPUT, Ch)

С точки зрения выполнения идентичны. Аналогично, INPUT всегда открыт для чтения и может быть использовано следующее выражение:

READ(Input, Ch)

Синтаксис и семантика файлов.

Для включения файловых операций в синтаксические и контекстные правила CFPascal, необходимы следующие изменения в синтаксических правилах 7, 12 и 13 и новое правило 29.

SR7.

<объявления> ::= VAR <список идентификаторов>: <тип>

| <объявления>;<список идентификаторов>:<тип>

SR12.

<выражение READ> ::= READ(<список идентификаторов>)

| RESET(<идентификатор>)

SR13.

<выражение WRITE> ::= WRITE(<список вывода>)

| WRITELN(<список вывода>)

| WRITELN

| REWRITE(<идентификатор>)

SR29.

<тип> ::= CHAR | TEXT

Соответствующее контекстное правило:

CR6.

Идентификатором типа TEXT является <идентификатор> описанный в разделе объявлений имеющий <тип> TEXT. Если идентификатор типа TEXT появляется в <выражении WRITE> или в <выражении READ>, он должен стоять первым в <списке идентификаторов> или <списке вывода>. Идентификатор типа TEXT, иной чем INPUT или OUTPUT должен быть описан в <объявлениях>. Только идентификаторы типа TEXT, исключая INPUT и OUTPUT, могут появляться внутри выражений RESET и REWRITE.

Переменные объявленные как TEXT должны быть подготовлены до того как к ним будут применены выражения READ и WRITE. Первой операцией должны быть REWRITE, которая делает готовит файл для записи. До REWRITE файл имеет неопределенное значение, как неинициализированная переменная типа CHAR. REWRITE может быть применено к фай Лу несколько раз, после чего каждый раз значением файловой переменной становится пустая строка. Последнее операцией примененной к файлу должно быть выражение WRITELN, после чего файл готов к применению выражения RESET, которое готовит файл для чтения. Символы, записанные в определенном порядке после REWRITE, будут считаны в том же порядке после RESET. Файл не может быть прочитан до того как туда что-либо будет записано, такая ситуация вызовет ошибку. Однако марке конца строки, который записывает в файл финальный WRITELN, будет прочитан как пробел. При выполнении следующего выражения READ программа выдаст ошибку. Операция RESET может быть применена к файлу несколько раз.

Копирование файлов

Типичная операция над файлами копирует один файл в другой. Программа CopyTwice копирует INPUT в OUTPUT через промежуточный рабочий файл Chars. Первый шаг – копирование INPUT в Chars, второй шаг – копирование Chars в OUTPUT.

DP 1

PROGRAM CopyTwice (INPUT, OUTPUT);

{Копирует символы, предшествующие # из INPUT в OUTPUT

Программа выдаст ошибку, если в INPUT отсутствует #}

VAR

Ch: CHAR;

Chars: TEXT; {Рабочий файл}

BEGIN {CopyTwice}

{Копировать INPUT в Chars}

{Копировать Chars в OUTPUT}

END. {CopyTwice}

DP 1.1

BEGIN {Копировать INPUT в Chars}

REWRITE(Chars); {Готовим Chars для записи}

READ(INPUT, Ch);

WHILE Ch <> ‘#’

DO

BEGIN

WRITE(Chars, Ch);

READ(INPUT, Ch)

END;

WRITELN(Chars, ‘#’) {Закрыть Chars маркером конца строки}

END

DP 1.2

BEGIN {Копировать Chars в OUTPUT}

RESET(Chars); {Готовим Chars для чтения}

READ(Chars, Ch);

WHILE Ch <> ‘#’

DO

BEGIN

WRITE(OUTPUT, Ch);

READ(Chars, Ch)

END;

WRITELN(OUTPUT)

END

Без маркера конца входной последовательности, который DP 1.1 помещает в конец промежуточного файла, DP 1.2 не сможет остановить свое выполнение.

Собираем разделы проекта.

DP 1A

PROGRAM CopyTwice (INPUT, OUTPUT);

{Копирует символы, предшествующие # из INPUT в OUTPUT}

VAR

Ch: CHAR;

Chars: TEXT; {Рабочий файл}

BEGIN {CopyTwice}

BEGIN {Копировать INPUT в Chars}

REWRITE(Chars); {Готовим Chars для записи}

READ(INPUT, Ch);

WHILE Ch <> '#'

DO

BEGIN

WRITE(Chars, Ch);

READ(INPUT, Ch)

END;

WRITELN(Chars, '#') {Закрыть Chars маркером конца строки}

END

BEGIN {Копировать Chars в OUTPUT}

RESET(Chars); {Готовим Chars для чтения}

READ(Chars, Ch);

WHILE Ch <> '#'

DO

BEGIN

WRITE(OUTPUT, Ch);

READ(Chars, Ch)

END;

WRITELN(OUTPUT)

END

END. {CopyTwice}

Выполнение:

INPUT: ABCD#

OUTPUT: ABCD

INPUT: 1#ABCD

OUTPUT: 1

INPUT: Four score and seven years ago#

OUTPUT: Four score and seven years ago

[восемьдесят семь лет назад]

Комментарий, описывающий поведение программы CopyTwice

{Копирует символы, предшествующие # из INPUT в OUTPUT

Программа выдаст ошибку, если в INPUT отсутствует #}

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

Используйт е имена переменных в комментариях только после того как они были объявлены.

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

Частичная таблица выполнения показывает содержимое файлов во время выполнения.

Разделение файлов.

Рассмотрим задачу разделения INPUT на четные и нечетные символы и дальнейшего распечатывания последовательности нечетных и последовательности четных символов. Переключатель может отслеживать четность или нечетность очередного символа, который будет копироваться в файлы Odds или Evens соответственно. Далее эти два файла могут быть скопированы в OUTPUT. Программа Split реализует эту стратегию.

DP 2

PROGRAM Split (INPUT, OUTPUT);

{Копирует INPUT в OUTPUT, сначала все нечетные, потом все четные.

Программа выдаст ошибку, если в INPUT отсутствует #}

VAR

Ch: CHAR;

Odds, Evens: TEXT;

BEGIN {Split}

{Разбить INPUT на Odds и Evens}

{Копировать Odds в OUTPUT}

{Копировать Evens в OUTPUT}

END. {Split}

Реализуем переключатель, который записывает положение следующего символа который будет считан.

DP 2.1

BEGIN {Разбить INPUT на Odds и Evens}

REWRITE(Odds);

REWRITE(Evens);

Next := ‘O’;

READ(INPUT, Ch);

WHILE Ch <> ‘#’

DO

{Записывать Ch в файлы выбранный с помощью Next,

переключить Next, читать Ch}

WRITELN(Odds, ‘#’);

WRITELN(Evens, ‘#’);

END

DP 2.1.1

BEGIN {Записывать Ch в файлы выбранный с помощью Next,

переключить Next, читать Ch}

IF Next = ‘O’

THEN

BEGIN

WRITE(Odds, Ch);

Next := ‘E’;

END

ELSE

BEGIN

WRITE(Evens, Ch);

Next := ‘O’;

END;

READ(INPUT, Ch);

END

DP 2.2 {Копировать Odds в OUTPUT} и DP 2.3 {Копировать Evens в OUTPUT} аналогичны DP 1.2 для программы CopyTwice где необходимо заменит Chars на Odds и Evens.

Сортировка и использованием циклического выполнения.

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

Новые идеи: Проверка сортированости, сортировка по выбору, пузырьковая сортировка.

Программа SelectSort

Сортировка строки символов с помощью набора выражений IF, использовавшаяся ранее требует программу, которая растет с размером сортируемой строк и требует тем больше переменных, чем больше строка. Теперь может быть разработана простая программа которая может сортировать строки любой длины. Сортируемая строка сохраняется в текстовом файле используя только одну переменную вне зависимости от того какой длины строка. Идея MinSort – найти и записать минимальную переменную в строке, минимальную переменную остатка строки и т.д. до тех пор пока вся строка не будет выведена. Это будет работать, если мы сможем копировать один файл в другой параллельно с нахождением минимума и многократно использовать созданный промежуточный файл с исключенным найденным минимальным символом.

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

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

{Копировать INPUT в F1 }

WHILE {в F1 имеются данные}

DO

BEGIN

{Печатать минимальный из F1}

{Копировать остальные из F1 в F2}

{Копировать F2 в F1}

END

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

Вот проект, основанный на этих идеях:

DP 3

PROGRAM SelectSort (INPUT, OUTPUT);

{Сортирует символы, предшествующие # из INPUT в OUTPUT.

Программа выдаст ошибку, если в INPUT отсутствует #}

VAR

Ch, Min: CHAR;

F1, F2: TEXT;

BEGIN {SelectSort}

{Копировать INPUT в F1 и эхо в OUTPUT}

{Сортировать F1 в OUTPUT используя стратегию SelectSort}

END. {SelectSort}

DP 3.1

BEGIN {Копировать INPUT в F1 и эхо в OUTPUT}

REWRITE(F1);

WRITE(OUTPUT, ‘INPUT DATA:’);

READ(INPUT, Ch);

WHILE Ch <> ‘#’

DO

BEGIN

WRITE(F1, Ch);

WRITE(OUTPUT, Ch);

READ(INPUT, Ch)

END;

WRITELN(OUTPUT);

WRITELN(F1, ‘#’)

END

DP 3.2

BEGIN {Сортировать F1 в OUTPUT используя стратегию SelectSort}

WRITE(OUTPUT, ‘SORTED DATA:’);

RESET(F1);

READ(F1, Ch);

WHILE Ch <> ‘#’

DO { Ch <> ‘#’ и Ch1 – первый символ F1}

BEGIN

{Выбираем минимальный из F1 b копируем остаток F1 в F2}

WRITE(OUTPUT, Min);

{Копируем F2 в F1}

RESET(F1);

READ(F1, Ch)

END;

WRITELN(OUTPUT);

END

Комментарий состояния (суждение) в части DO

{ Ch <> ‘#’ и Ch1 – первый символ F1}

в DP 3.2 будет необходим в DP 3.2.1, которая реализует первую подзадачу в операторе BEGIN части DO. Первая часть суждения в части DO является TRUE, потому что Ch <> ‘#’ является условием выполнения части DO. Вторая часть суждения является TRUE, потому что эта точка может быть достигнута либо сверху, либо после успешного выполнения цикла, в любом случае последние два выполненных оператора будут:

RESET(F1);

READ(F1, Ch)

Таким образом, Ch должна содержать первый символ F1. Без этого анализа было бы трудно предположить, какое начальное значение присвоить Min в 3.2.1.

DP 3.2.1

BEGIN {Выбираем минимальный из F1 b копируем остаток F1 в F2}

REWRITE(F2);

Min := Ch;

READ(F1, Ch);

WHILE Ch <> ‘#’

DO { Ch <> ‘#’ и Ch1 – первый символ F1}

BEGIN

{Выбираем минимальный из (Ch, Min)

копируем второй символ в F2}

READ(F1, Ch)

END;

WRITELN(F2, ‘#’);

END

DP 3.2.2

BEGIN {Копируем F2 в F1}

RESET(F2);

REWRITE(F1);

READ(F2, Ch);

WHILE Ch <> ‘#’

DO

BEGIN

WRITE(F1, Ch);

READ(F2, Ch)

END;

WRITELN(F1, ‘#’);

END

DP 3.2.1.1

BEGIN {Выбираем минимальный из (Ch, Min)

копируем второй символ в F2}

IF Ch < Min

THEN {Ch – минимальный из (Ch, Min)}

BEGIN

WRITE(F2, Min);

Min := Ch;

END

ELSE {Min – минимальный из (Ch, Min)}

WRITE(F2, Ch);

END

Для того, чтобы достичь уверенности в DP 3.2 мы седлаем 4 частичных таблицы выполнения для ее поведения (исключая начальные выражения WRITE для аннотированного вывода). Эти таблицы исследуют варианты, в которых в F1 отсутствуют символы кроме #, когда в F1 один символ и когда в F1 два символа сортированные и нет. В каждом случае Min присваивается минимальный из двух символов из F1 и остальные символы копируются в F2.

Таблица выполнения для DP 3.2, символы в F1 отсутствуют

Таблица выполнения для DP 3.2, в F1 один символ

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

В строку финальных значений

Изучая таблицу можно сделать вывод, что единственный символ в F1 присваивается Min и добавляется в OUTPUT вне зависимости от изначальных значений F2, Ch и Min.

Таблица выполнения для DP 3.2, в F1 два символа в обратном порядке

DP 3.2.2 в этой таблице выполнения был пропущен.

Когда выполнение достигает строчки RESET(F1) минимальное значение из F1 добавляется к OUTPUT и оставшаяся задача сокращается к сортировке файла с одним символом как в предыдущей таблице. Поскольку значения F2, Ch и Min в данном случае несущественны, единственный символ в F1 (в данный момент C) присваивается Min и добавляется к OUTPUT. Поэтому уже на этом этапе мы можем предположить, что таблица выполнения для этого случая будет завершена следующей комбинацией:

Что собственно и выяснилось при завершении таблицы выполнения.

Поэтому мы можем упростить таблицу выполнения для двухсимвольного файла, используя таблицу выполнения для файла с одним символом.

Таблица выполнения для DP 3.2, в F1 два символа в обратном порядке

Варианты, показанные в пяти таблицах выполнения, позволяют нам спрогнозировать варианты, когда F1 содержит более 2 символов. На каждом шаге минимальный из F1 помещается в Min, и остаток копируется в F2. Если это символ встречается в F2 несколько раз, то только первый помещается в Min. Другие вхождения этого символа копируются в F2 вместе с остальными.

Для поддержки анализа SelectSort может быть собрана для тестирования. Возможно проект не слишком большой для того, чтобы собрать все сразу, но идея сначала собрать части 3, 3.1, 3.2, 3.2.1 нам кажется более удачной. Раздел 3.2.2 заменим выражением, которое выводит единственный символ # в F1, в результате чего будет выполняться только одна итерация.

DP 3A

PROGRAM SelectSort (INPUT, OUTPUT);

{Сортирует символы, предшествующие # из INPUT в OUTPUT.

Программа выдаст ошибку, если в INPUT отсутствует #}

VAR

Ch, Min: CHAR;

F1, F2: TEXT;

BEGIN {SelectSort}

BEGIN {Копировать INPUT в F1 и эхо в OUTPUT}

REWRITE(F1);

WRITE(OUTPUT, 'INPUT DATA:');

READ(INPUT, Ch);

WHILE Ch <> '#'

DO

BEGIN

WRITE(F1, Ch);

WRITE(OUTPUT, Ch);

READ(INPUT, Ch)

END;

WRITELN(OUTPUT);

WRITELN(F1, '#')

END

BEGIN {Сортировать F1 в OUTPUT используя стратегию SelectSort}

WRITE(OUTPUT, 'SORTED DATA:');

RESET(F1);

READ(F1, Ch);

WHILE Ch <> '#'

DO { Ch <> '#' и Ch1 - первый символ F1}

BEGIN

BEGIN {Выбираем минимальный из F1, копируем остаток F1 в F2}

REWRITE(F2);

Min := Ch;

READ(F1, Ch);

WHILE Ch <> '#'

DO { Ch <> '#' и Ch1 - первый символ F1}

BEGIN

{Выбираем минимальный из (Ch, Min)

копируем второй символ в F2}

READ(F1, Ch)

END;

WRITELN(F2, '#');

END

WRITE(OUTPUT, Min);

{Для тестирования создаем пустой F1}

REWRITE(F1);

WRITELN(F1, ‘#’);

{вместо …}

{Копируем F2 в F1}

RESET(F1);

READ(F1, Ch)

END;

WRITELN(OUTPUT);

END

END. {SelectSort}

Выполнение:

INPUT: XBZA#

OUTPUT: INPUT DATA:XBZA#

SORTED DATA:X

Тест работает как и ожидалось: первый символ из INPUT помещается в OUTPUT, как будто в файле он один.

Когда мы соберем программу полностью, нам останется протестировать код находящий минимум и копирующий файлы. Если была проблема в предыдущем коде, она должна проявиться при выводе сортированной последовательности в OUTPUT.

Поскольку содержимое промежуточных фалов пропадает, имеет смысл распечатывать его чтобы упростить тестирование.

DP 3B

PROGRAM SelectSort (INPUT, OUTPUT);

{Сортирует символы, предшествующие # из INPUT в OUTPUT.

Программа выдаст ошибку, если в INPUT отсутствует #}

VAR

Ch, Min: CHAR;

F1, F2: TEXT;

BEGIN {SelectSort}

BEGIN {Копировать INPUT в F1 и эхо в OUTPUT}

REWRITE(F1);

WRITE(OUTPUT, 'INPUT DATA:');

READ(INPUT, Ch);

WHILE Ch <> '#'

DO

BEGIN

WRITE(F1, Ch);

WRITE(OUTPUT, Ch);

READ(INPUT, Ch)

END;

WRITELN(OUTPUT);

WRITELN(F1, '#')

END

BEGIN {Сортировать F1 в OUTPUT используя стратегию SelectSort}

WRITE(OUTPUT, 'SORTED DATA:');

RESET(F1);

READ(F1, Ch);

WHILE Ch <> '#'

DO { Ch <> '#' и Ch1 - первый символ F1}

BEGIN

BEGIN {Выбираем минимальный из F1, копируем остаток F1 в F2}

REWRITE(F2);

Min := Ch;

READ(F1, Ch);

WHILE Ch <> '#'

DO { Ch <> '#' и Ch1 - первый символ F1}

BEGIN

BEGIN {Выбираем минимальный из (Ch, Min)

копируем второй символ в F2}

IF Ch < Min

THEN {Ch - минимальный из (Ch, Min)}

BEGIN

WRITE(F2, Min);

Min := Ch;

END

ELSE {Min - минимальный из (Ch, Min)}

WRITE(F2, Ch);

END;

READ(F1, Ch)

END;

WRITELN(F2, '#');

END

WRITE(OUTPUT, Min);

BEGIN {Копируем F2 в F1}

RESET(F2);

REWRITE(F1);

READ(F2, Ch);

WHILE Ch <> '#'

DO

BEGIN

WRITE(Ch) {Тестирование}

WRITE(F1, Ch);

READ(F2, Ch)

END;

WRITELN('#(F1)'); {Тестирование}

WRITELN(F1, '#');

END

RESET(F1);

READ(F1, Ch)

END;

WRITELN(OUTPUT);

END

END. {SelectSort}

Выполнение:

INPUT: CEDAR#

OUTPUT: INPUT DATA: CEDAR #

SORTED DATA: A(Min) EDCR#(F1)

C(Min) EDR#(F1)

D(Min) ER#(F1)

E(Min) R#(F1)

R(Min) #(F1)

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

Конечная версия программы SelectSort получается удалением отладочных операторов WRITE из DP 3B.

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

Структурное тестирование

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

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

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

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

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

Для примера рассмотрим тест для DP 3A с входными данными XBZA. Очевидно, что все выражения будут выполнены, единственные части которые могут быть пропущены – операторы внутри выражений WHILE, для которых условие на входе равно FALSE.

Тестовый запуск программы 3B со входными данными CEDAR# проанализировать несколько более сложно. Для всех выражений WHILE выполняются части DO, но не понятно выполняются ли части THEN и ELSE внутри DP 3.2.1.1 В любом случае символ записан в F2, но это не дает нам информации, каким путем шло выполнение внутри оператора IF.

Часть THEN выполняется когда меняется текущий минимум, это происходит при первом проходе для CEDAR#, когда С заменяется на A при четвертой итерации для 3.2.1.1. С другой стороны, часть ELSE выполняется когда текущий минимум не меняется и это случается на второй итерации, когда C меньше чем E. Таким образом, CEDAR является адекватным структурным тестом. Анализ также показывает, что XHB# не может быть адекватным структурным тестом, поскольку часть ELSE для 3.2.1.1 не может быть достигнута.

Анализ SelectSort

В противоположность семейству IFSort и MinSort, размеры которых существенно растут с ростом размеров сортируемых строк, SelectSort может сортировать строки любого размера. Будучи по размеру не более, чем IFSort4 или MinSort6, SelectSort может сортировать строки в сотни и тысячи символов. Однако, время выполнения для SelectSort будет зависеть от длины входной строки. Количество шагов в данном случае может быть точно определено. Первое, сосредоточимся на выражениях WHILE, которые появляются в DP 3.1, 3.2, 3.2.1, 3.2.2. Исключая другие детали программы, выражения WHILE в SelectSort могут быть пронумерованы.

Предположим, что имеется N входных символов. Выражение WHILE номер 1 требует N итераций. Второе выражение WHILE также потребует N итераций, потому что F1 укорачивается на 1 символ при каждой итерации. Количество итерации для третьего и четвертого выражений WHILE зависит от номера итерации для выражения WHILE номер 2.

На первой итерации WHILE номер 2, WHILE номер 3 требует N итераций, а WHILE номер 4 – N-1 итераций. На второй итерации для WHILE номер 2, WHILE номер 3 требует N-1 итераций, а WHILE номер 4 – N-2 итераций и т.д. Таким образом, количество итераций будет следующим:

Далее, посчитаем выражения READ и WRITE для каждого блока WHILE

Следовательно, количество выражений READ/WRITE выполняемых SelectSort, будет следующим:

Nrw = 2N + N + 2(N + (N-1) + … + 1) + 2((N-1) + (N-2) + … + 0)

= 5N + 4((N-1) + …+ 1)

= 5N + 4N(N-1)/2

= 5N + 2N² – 2N

= 2N²+3N

Количество выражений READ/WRITE для входных последовательностей различной длины

Очевидно, что количество итераций Nrw в основном определяется составляющей 2N². Мы можем сказать, что количество операций ввода-вывода для данной программы порядка 2N². Т.е. 1000-строка будет сортироваться примерно в 100 раз дольше, чем 100-строка, и т.д. Время работы программы может быть довольно большим для еще более длинных строк.

12
• Далее ⇒