326
7. Заметки о тестировании программ
End.
Создаем систему тестов. В текущий директорий записываем
файлы с каждым тестом (имена i.tst, где i — номер теста) и ре-
зультирующие файлы (имена i.ans, где i — номер теста).
файла
2.tst
3.tst
5.tst
Тест
2 5 45 45 3 5 10 10 20 0
файла
2.ans
3.ans
5.ans
Результат
7 91 8
20 20
Переименование входных файлов в файл с именем input.txt
и пятикратный запуск программы при очевидных результатах утомительно и не очень удобно. Требуется минимальная авто- матизация процесса тестирования программ. Ниже приведен текст программы. Следует набрать и сохранить его в файле
Checker.dpr (текущий директорий), а затем откомпилировать,
используя среду Delphi. После этого запустите программу Chec-
ker.exe. Её входными параметрами (они задаются в командной строке) являются: имя исполняемого файла (рассмотренный выше пример следует откомпилировать в текущий директорий,
например, с именем количество тестов; ограничение по времени (в секундах). Вид командной строки — Checker.exe
ту.ехе 5 2 (5 тестов, 2 секунды на тест). Результат очевиден.
Итак, имея программу Checker, мы значительно упрощаем про- цесс отладки решений.
{$apptype
приложение.*}
uses
var
:
{* Установки для
функции
*}
:
Информация
о созданном
*}
TickCount : Longint;{* Количество миллисекунд.*}
:
тестируемой
программы. *}
PightAnswer :
Программа разработана студентом 4-го курса факультета информатики Вят- ского государственного педагогического университета Московкиным Алек- сеем Александровичем.
7. Заметки о тестировании программ 327FileName : String;{*Имя тестируемойпрограммы.*}Feedback : тестирования.*}TestCount : тестов.*} : Integer;{*Ограничениепо времени.* } : Boolean;{*Индикатор окончаниялимита времени. *}ExitCode : Cardinal;{*Код завершениятестируемой программы. *}i -.Integer;beginFileName :=
ParamStr ; { *Первый параметр - имя *}TestCount := StrToInt -количество тестов.*}TimeLimit := ограничение времени. *}for i:=l to TestCount do begin входной тест в *} :=
*} :=StartUpInfoSInf ;=
{ *Сделать окнопроцесса *}CreateProcessfalse,{*3апуск тестируемой программы. *} or ;TickCount := время.*}IsTimeLimit := true;While ((TickCount+TimeLimit*1000) >=
GetTickCount)and IsTimeLimit doif пока программазакончит работу или истечет *}IsTimeLimit := false;if IsTimeLimit then begin {*Если истекзакончить работу *}
328 7. Заметки о тестировании программ
:=
limit
лимита времени. *}
end
else begin
;
{*Получить код завершения программы. *}
if ExitCode<>0 then FeedBack := 'Run-time error!'
{*Если код завершения не равен нулю, то
ошибка времени
* }
else begin
;=
RightAnswer
{*3агрузить файл с ответами тестируемой
*}
Загрузить файл с правильными
* }
if
TextoRight Answer
then
Feedback := 'Wrong answer . . .' {*Если они
не совпадают, то тест не
*}
else FeedBack ;=
все в порядке.*}
end;
end;
;
входной тест.*}
'+FeedBack);
(*Выдать результат теста.*}
end;
ненужный
файл. *}
writeln
...');{*Выдать сообщение об
окончании. *}
Readln;
end.
7.3. Тестирование программы решения задачи (на примере)
Рассмотрим следующую задачу. Даны два квадратных кле- точных поля. Размер клетки 1*1. Клетки поля закрашены в бе- лый или черный цвет. Совпадающая часть квадратов — это
7. Заметки о тестировании программ329множество клеток, имеющих одинаковый цвет. Она разбивает- ся на какое-то количество связных областей. Найти площадь наибольшей связной области совпадающей части квадратов.
Пример1-й квадрат
2-йквадрат
Результат связная область
(окрашен в черный цвет) имеет площадь 4
Пример.
Photol.txt4 0100 1000 1110 1101
Photo2.txt4 0111 1011 0010 0001 4
Описание квадратов хранится в текстовых файлах. Символ во входных файлах соответствует черной клетке, символ '0' — белой. В выходном файле должно быть одно целое число,
равное площади наибольшей связной области общей части.
Ограничения. Размер поля
N в интервале от 2
до 1000. Время работы — не более 5 секунд.
Анализ и решение задачи. В идейном плане задача очень простая. Её суть сводится к следую- щему:
If2 квадратаThen результата>: =
1Else результата>: =
0,а затем найти связную область с наибольшей пло- щадью.
Проработав
этот учебник до данной страницы,
программное решение представленное ниже, пи- шется за считанные минуты.
Структуры данных.
Size =
квадрата. *}Dx: Array .4] Of Integer =
(0, -1, 0, массивы Dx, Dyиспользуются в волновом алгоритме обходасвязной области. *}Dy: 4] Of Integer = (-1, 0, 1, 0)Type Array Of Byte;{*Для хранения результирующего *}1)
330 7. Заметки о тестировании программ
Helper = Array [1..Size*Size] Of Integer;
тип для хранения очереди
при обходе в ширину. *}
Var
PhotoM :
квадрат. *}
Ох,Оу: Helper;
Result,
Integer;
Напомним логику волнового алгоритма (п. 3.2).
Function
: Byte):
совпавшей части
*}
Var i,
nx,
up : Integer;
Begin
:= k;
:= p; dn := 1 ; up := 1;
{ *3аносим координаты первой клетки
в
*}
PhotoM [k,p]:=0;
Repeat
For
4 Do Begin
nx
Ox [dn] + dx [i]; ny
Oy [dn] + dy [i];
If (nx>0) And (ny>0) And (nx<=N) And (ny<=N)
And
Then
в очередь. *}
PhotoM [nx, ny]
0;
(up) ; Ox [up] := nx;
Oy [up] := ny;
End;
End;
Inc
к очередному элементу
очереди. *}
Until dn>up;{*Пока очередь не пуста.*}
Get := up; {*Количество элементов в очереди равно
площади общей части. *}
End;
Процедура ввода данных.
Procedure
Var photol,
Text;
char2 : Char;
x,y : Integer;
Begin
Assign (photol,
Reset
файлы. *}
Assign (photo2,
;
7. Заметки о тестировании программ 331
For у := 1
N Do Begin
For х ;= 1
N Do Begin
Read
char2);
PhotoM
"закраска" совпадает, то ...*}
End;
ReadLn (photol); ReadLn (photo2);
End;
End;
Главная процедура.
Procedure Solve;
Var i, j , t
Begin
For
1 To N Do
For
1 To N Do
If (PhotoM[i,j]=l) Then Begin
t:=Get(i,j) ;
If t>Result Then
наибольшей связной области. *}
End;
End;
Вывод результата.
Procedure
Var f: Text;
Begin
Assign (f ,
; Write
(f, Result);
End;
Основная программа.
Begin
Solve;
WriteAnswer;
End.
Итак, часть тестов, вне всякого сомнения, проходит, и есть база для проведения экспериментов. Изменение значения кон- станты Size до требований задачи (даже до значения 200) при- водит к сообщению Error 22: Structure too large.
хватает
332
7. Заметки о тестировании программоперативной памяти. Напомним, что в среде Турбо Паскаль для задачи выделяется порядка 64 Кбайт*.
Размерность задачи такова, что результирующее клеточное поле хранить в оперативной памяти можно только с использо-
ванием динамических структур, битовых записей, или ещё ка- ким-нибудь оригинальным способом. А требуется ли хранить?
Возможна построчная обработка поля. Пусть обработана стро- ка. При обработке следующей строки возможны ситуации: об- ласть 1 продолжается в следующей строке; область 2 закончи- лась; области 3 и 4 «сливаются» в одну; область 5 только начинается. Единственная небольшая сложность — правильно отслеживать изменение значений площади при слиянии облас- тей. Основные процедуры этого варианта программы приводят- ся ниже по тексту.
Const Size =
поля.*}Answer =
Array Ofответов (ячейки с площадями). *}PhotoLine = Array Of Integer;{*Дляобработки строки поля. *}OldLine, NewLine : - NewLine - новая строки. *} : ячейка, для поискасвободного номера связной области. *}ProcedureBeginFillChar( OldLine,wrlnd := 1;End; , 0); , 0);В настоящее время происходит отказ от среды Турбо Паскаль на олим- пиадах по программированию. В новых таких жестких ограничений по оператив- ной памяти, как правило,
Автор считает, что ограничения - один из «двигателей»
развития. Вспомним 1 -й и 2-й этапы развития технологий программирования. Ограниче- ния по ресурсам ЭВМ являлись мощнейшим рычагом создания эффективных алгорит- мов и их исследования.
Заметки о тестировании программ 333
Result :
TempRes : Answer;
file2 : Text;
Procedure Change
Integer);
номера устаревших связных областей
на новое
*}
Var i : Integer;
Begin
For i ;= 1 To Size Do Begin {*Выполняется при
слиянии двух связных областей. *}
If NewLine[i] = Dellnd Then
;= Newlnd;
If
= Dellnd Then
:= Newlnd;
End;
End;
Procedure
предыдущей и
новой строк. Находим, какие связные области
сливаются или дают "потомство". *}
Var i -.Integer;
char2 :Char;
Begin
FillChar ( NewLine,
0);
For i := 1 To Size Do Begin
Read(filel, charl); Read(file2, char2);
charl = char2 Then Begin {*Правило одинаковой
*}
If (NewLine
= 0) Or (i = 1) Then Begin
{*Новая связная область. *}
While
Do
If wrInd
( wrind ) Else wrind
:= 1;
:= wrind
End
Else
:=
дополнение к связной области. *}
If
Then
или
*}
TempRes
[i] ]
TempRes
[ OldLine [i] ] +
[ NewLine [i] ];
{*Сложение значений
*)
If
Then Begin
*)
NewLine [i] ] := 0;
{*Уничтожение устаревшего описания
связной
*)
334 7. Заметки о тестировании программEnd Else NewLine [i] :=
OldLine [i] ; *}End; ( ] );EndElse := 0;End;ReadLn ReadLn (file2);End;Procedure Solve;Var i, j : Integer;BeginAssign (filel, Reset (filel); Reset (file2);For i 1
To Size Do Begin строки. *}For j := 1 To Size DoIf [j]<>0) And > Result)Then ResultOldLine ;=
строку считаемстарой. *}End; ;End;Продолжим тестирование решения. Вопросы с оперативной памятью решены. Остались временные ограничения — 5 се- кунд на работу программы с одним тестом. С этой целью необ- ходимо разработать достаточно полную систему тестов. Один тест максимального размера еще не говорит о том, что выполняются требования за- дачи. Один из файлов (для простоты) можно заполнить единицами (первая вспомо- гательная программа). А затем? Напрашивается создание фай- лов максимального размера по принципам, приведенным на рисунке, и, конечно,
файла со случайными значениями, а это еще четыре вспомогательные программы (не ручным же спосо- бом заполнять файлы). Этим, вероятно, не исчерпываются все возможности, но ограничимся приведенными тестами — их до- статочно для нашего изложения. Затем необходимо организо- вать учет времени решения задачи одним из способов, описан-
7. Заметки о тестировании программ 335ным выше (лучше,
естественно, вторым).
Что выясняется? Ока- зывается, только на од- ном из тестов времен- ное ограничение не выполняется, а именно на тесте со следующей структурой —
«на
Почему именно на этом тесте? Вернемся к решению. Ответ просматривается — частота слияния связных областей на тесте значительно возрастает, что вызывает работу процедуры
Chan-ge , е. лишний цикл (подсчитайте — сколько раз выполняется процедура
Change для области 1000*1000, заполненной по принципу «зубьев»). Можно ли без принципиальных измене- ний на идейном уровне и в программной реализации добиться выполнения требований задачи? Оказывается, да! Используем идею косвенной адресации. Исключим, точнее изменим, проце- дуру
Change из решения. В процедуре просматривался весь массив с целью поиска существующих «родственников». Изме- ним смысловую нагрузку элемента массива. Она будет содер- жать:
• или данные о площади;
• или ссылку (информацию) на ту ячейку, в которой запи- сано значение площади при слиянии связных областей;
• или ссылку на ссылку при многократном слиянии связ- ных областей.
Как их отличить друг от друга? Стандартный прием — отри- цательное значение является признаком косвенной адресации.
Исключение многократного просмотра длинных цепочек (при слиянии большого количества связных областей) осуществля-
ется одноразовым прохождением по цепочке, после которого во всех ячейках указывается адрес конечной ячейки со значением площади. Еще один момент рассматриваемой идеи требует упо- минания. В предыдущем варианте признаком свободного номе- ра связной области являлось значение элемента в мас- сиве
TempRes. В данном варианте этот массив используется для косвенной к ячейкам со значением площади, поэто- му требуется введение дополнительного массива с элементами логического типа для этой цели, назовем его
Used.Type = Array Of дляхранения информации об использованных номерахсвязных областей. *}Var Заметки о тестировании программПри этом предположении поиск свободного номера связной области выглядит следующим образом.
Procedure Used необходим,значение Used[i], равное False, говорит о том,что значение i -
свободный номер связнойобласти. *}BeginWhile DoIf wrInd
(
) Else
:= 1;
TempRes [ wrlnd ] ;= 0;
End;
Ключевая функция поиска номера ячейки, указывающей на значение площади. При выходе из рекурсии изменяем значе- ния
Function
ind : Integer
итоговый номер, указывающий на значение
площади. *}
Begin
If TempRes [ ind ] > 0 Then FindLast ;= ind
Else Begin
TempRes [ ind ] ;= -FindLast (
( TempRes
[ind] ) ) ;
FindLast := Abs ( TempRes [ ind ] ) ;
End;
End;
Процедура сравнения соседних строк претерпит незначите-
льные изменения. Приведем её для сравнения с предыдущей.
Procedure
Var i : Integer;
char2 : Char;
Begin
FillChar ( NewLine,
0) ;
For i := 1 To Size Do Begin
charl); Read(file2,
2) ;
If charA = charB Then Begin
If
= 0) Or (i = 1) Then Begin
NextWrlnd;{*Новый вариант поиска
свободного номера связной области. *}
newLine [i] := wrlnd;
End Else
:= NewLine [i-1];
If
And
Then
7. Заметки о тестировании программ 337
If [ ] > 0 Then Begin(*Простое *}площади. *} NewLine [i] ] := -
OldLine [i]; ячейку со значениемплощади в ячейку ссылочного типа. *} := OldLine [i]End Else NewLine [i] := FindLast ( OldLine[i] ); {*При слиянии со связнойобластью, которая при данномзначении i помечена ячейкойссылочного типа, находим ячейку созначением площади этой связнойобласти. *} ( TempRes [ NewLine [i] ] );Used [NewLine [i] ] := True ;End;End; ;End;