Календарь
Сентябрь
Пн   4 11 18 25
Вт   5 12 19 26
Ср   6 13 20 27
Чт   7 14 21 28
Пт 1 8 15 22 29
Сб 2 9 16 23 30
Вс 3 10 17 24  

Тестирование программ



Скачать: Тестирование программ

Содержание реферата

1. Постановка задачи

2. Алгоритм (метод решения)

3. Внутренняя спецификация программы

4. Комментированный текст программы

5. Внешняя спецификация

6. Руководство пользователя

7. Описание тестов

1. Постановка задачи.

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

2. Алгоритм (метод решения).

Сначала исходный файл разбивается на куски по 10000 чисел, каждый кусок сортируется в памяти и записывается в один из двух временных файлов, причем так, что количество кусков в этих файлах отличается не более чем на 1 (далее - первоначальная сортировка).

Затем, несколько раз выполняется операция "склеивание"(одно выполнение операции "склеивание" мы будем незывать "шаг"), т.е два исходных файла, в которых находились отсортированные куски копируются в два других файла, при этом из двух кусков, находящихся в разных файлах и имеющих одинаковые номера создается один отсортированный кусок. Этот кусок записывается в первый выходной файл если исходные куски имели нечетные номера и во второй, если исходные куски имели четные номера.

3. Внутренняя спецификация программы

При написании программы использовалась среда Borland Pascal 7.0 и встроенный компилятор.

Для ускоренного обмена с диском применялся блоковый ввод-вывод, т.е информация читается и записывается целыми кластерами. Для осуществления этого способа ввода-вывода был написан модуль(Files), с помощью которого ввод-вывод внешне не отличается от обычного.

Схема программы предельно проста: сначала выполняется первоначальная сортировка(процедура firstsort), затем вызываем склеивание(процедура ftrans (in1, in2, out1, out2: workfile);), где пары файлов все время меняются и после каждого запуска процедуры проверяется условие выхода.

Процедура ftrans открывает все файлы, затем выполняет несколько раз процедуру слива одного куска (onestep) и закрывает файлы.

4. Комментированный текст программы

{Модуль Files. Сдесь переписаны все процедуры и функции необходимые для работы с файлами, работающие с блоками. Работа с ними осуществляется также как и с обычными процедурами модуля System.}

unit Files;
interface
const typesize=4;
const bufsize = 2048;
type using=longint;
type buffer = array[1..bufsize] of using;
type pbuffer = ^buffer;
type filemode = (fread, fwrite, closed);
type tfile = record
buf: pbuffer;
mode: filemode;
f: file;
count, leng: integer;
end;
procedure fAssign(var w: tfile; name: string);
procedure fReWrite(var w: tfile);
procedure fReset(var w: tfile);
procedure fPut(var w: tfile; d: using);
procedure fGet(var w: tfile; var d: using);
procedure fClose(var w: tfile);
function fEof(var w: tfile): boolean;

implementation
procedure fAssign(var w: tfile; name: string);
begin
Assign(w.f, name);
w.mode:=closed;
end;

procedure fReWrite(var w: tfile);
begin
if w.mode=closed then
begin
ReWrite(w.f, typesize);
new(w.buf);
w.count:=0;
w.leng:=0;
w.mode:=fwrite;
end;
end;

procedure fReset(var w: tfile);
begin
if w.mode=closed then
begin
Reset(w.f, typesize);
new(w.buf);
BlockRead(w.f, w.buf^, bufsize, w.leng);
w.count:=1;
w.mode:=fread;
end;
end;

procedure fPut(var w: tfile; d: using);
begin
if w.mode=fwrite then
begin
w.count:=w.count+1;
w.buf^[w.count]:=d;
if w.count=bufsize then
begin
BlockWrite(w.f, w.buf^, w.count);
w.count:=0;
end;
end;
end;

procedure fGet(var w: tfile; var d: using);
begin
if (w.mode=fread) then
begin
d:=w.buf^[w.count];
if w.leng=w.count then
begin
BlockRead(w.f, w.buf^, bufsize, w.leng);
w.count:=1;
end else w.count:=w.count+1;
end;
end;

procedure fClose(var w: tfile);
begin
if w.mode=fwrite then BlockWrite(w.f, w.buf^, w.count);
dispose(w.buf);
w.mode:=closed;
Close(w.f);
end;

function fEof(var w: tfile): boolean;
begin
if (w.mode=fread) and (w.leng=0) then fEof:=true
else fEof:=false;
end;

begin
end.
{конец files.pas}
{----------------------------------------------------------------------------}


{Файл sort.pas - сортировка в памяти.}
var k: integer;

function SwapTops(no: integer): integer;
var t: longint;
begin
if (memo^[2*no+1]>memo^[2*no]) then
begin
t:=memo^[no];
memo^[no]:=memo^[2*no+1];
memo^[2*no+1]:=t;
SwapTops:=2*no+1;
end else
begin
t:=memo^[no];
memo^[no]:=memo^[2*no];
memo^[2*no]:=t;
SwapTops:=2*no;
end;
end;

procedure SwapHalf(no: integer);
var t: longint;
begin
if memo^[no]<memo^[2*no] then
begin
t:=memo^[no];
memo^[no]:=memo^[2*no];
memo^[2*no]:=t;
end;
end;

function Reg(no: integer): boolean;
begin
if (2*no)>k then Reg:=true else
if (2*no+1)>k then
begin
SwapHalf(no);
Reg:=true;
end else
if (memo^[2*no]<=memo^[no]) and (memo^[2*no+1]<=memo^[no]) then Reg:=true
else Reg:=false;
end;

procedure HalfReg(no: integer);
var next: integer;
begin
next:=no;
while (not Reg(next)) do next:=SwapTops(next);
end;

procedure RegTree;
var i: integer;
begin
for i:=k downto 1 do HalfReg(i);
end;

procedure SwapLeaves(l1, l2: integer);
var t: longint;
begin
t:=memo^[l1];
memo^[l1]:=memo^[l2];
memo^[l2]:=t;
end;

procedure SortMemo(len: integer);
begin
k:=len;
RegTree;
for k:=len-1 downto 1 do
begin
SwapLeaves(1, k+1);
HalfReg(1);
end;
end;
{конец sort.pas}
{----------------------------------------------------------------------------}
{Основная пограмма}
uses Dos, Files{Подключение модуля, осуществляющего ввод-вывод.};

const memlen=10000;{Размер памяти, разрешенной для использования}

type tmemo = array[0 .. memlen] of longint;
type pmemo = ^ tmemo;{Тип-указатель на основной массив, используемый
программой}

var memo : pmemo;

{$I sort.pas} {Подключение файла, содержащего процедуру сортировки
массива за время n*(log n), не используя дополнительной памяти(сортировка
деревом).}

type workfile = record
main{основной файл},
inf{файл, содержащий длины отсортированных кусков}: tfile;
end;{tfile - тип, определенный в unit Files, который заменяет файловые типы}

var
t1, t2, t3, t4, dest, seur: workfile;
{временные файлы} {входной и выходной файл}


{Инициализация}
procedure Init;
var tmp: string;
begin
tmp:=getenv('TEMP');
fAssign(t1.main, tmp+'\~fsort-1.tmp');
fAssign(t2.main, tmp+'\~fsort-2.tmp');
fAssign(t3.main, tmp+'\~fsort-3.tmp');
fAssign(t4.main, tmp+'\~fsort-4.tmp');
fAssign(t1.inf, tmp+'\~finf-1.tmp');
fAssign(t2.inf, tmp+'\~finf-2.tmp');
fAssign(t3.inf, tmp+'\~finf-3.tmp');
fAssign(t4.inf, tmp+'\~finf-4.tmp');
fAssign(seur.main,ParamStr(1));
fAssign(dest.main,ParamStr(2));
end;


{Первоначальная сортировка}
procedure firstsort(var inp, out1, out2: workfile);
var i, k: longint;
begin
fReset(inp.main);
fRewrite(out1.main);
fRewrite(out2.main);
fRewrite(out1.inf);
fRewrite(out2.inf);
new(memo);
repeat
for i:=1 to memlen do
if fEof(inp.main) then
begin
i:=i-1;
break
end else fGet(inp.main, memo^[i]);
k:=i;
sortmemo(k);
for i:=1 to k do fPut(out1.main, memo^[i]);
fPut(out1.inf, k);
if k=memlen then
begin
for i:=1 to memlen do
if fEof(inp.main) then
begin
i:=i-1;
break;
end
else fGet(inp.main, memo^[i]);
k:=i;
sortmemo(k);
for i:=1 to k do fPut(out2.main, memo^[i]);
fPut(out2.inf, k);
end;
until fEof(inp.main);
dispose(memo);
fClose(inp.main);
fClose(out1.main);
fClose(out2.main);
fClose(out1.inf);
fClose(out2.inf);
end;


{Процедура, копирующая заданное количество эл-тов из одного файла в другой.
Используется при сливании для копирования оставшейся части куска(если другой
кусок иссяк).}
procedure Copy(var inp, out: workfile; c0: longint);
var
c, n: longint;
Done: boolean;
begin
for c:=c0 downto 1 do
begin
fGet(inp.main, n);
fPut(out.main, n);
end;
end;


{Сливает два очередных куска из файлов in1 и in2 и записывает в out.}
procedure onestep(var in1, in2, out: workfile; c01, c02: longint);
var n1, n2, c1, c2, c: longint;
Done: boolean;
begin
Done:=false;
c1:=c01-1;
c2:=c02-1;
c:=0;
fGet(in1.main, n1);
fGet(in2.main, n2);
repeat
if n1<n2 then
begin
fPut(out.main, n1);
c:=c+1;
if c1=0 then
begin
fPut(out.main, n2);
c:=c+1;
Copy(in2, out, c2);
c:=c+c2;
Done:=true;
end else
begin
fGet(in1.main, n1);
c1:=c1-1;
end;
end else
begin
fPut(out.main, n2);
c:=c+1;
if c2=0 then
begin
fPut(out.main, n1);
c:=c+1;
Copy(in1, out, c1);
c:=c+c1;
Done:=true;
end else
begin
fGet(in2.main, n2);
c2:=c2-1;
end;
end;
until Done;
end;


{Процедура осуществляет один шаг(т.е. копирует файлы in1 и in2 в out1 и out2,
при этом склеивая куски)}
procedure ftrans(var in1,in2,out1,out2: workfile);
var c1, c2, c: longint;
begin
fReset(in1.main);
fReset(in2.main);
fReset(in1.inf);
fReset(in2.inf);
fRewrite(out1.main);
fRewrite(out2.main);
fRewrite(out1.inf);
fRewrite(out2.inf);
while (not fEof(in1.inf)) and (not fEof(in2.inf)) do
begin
fGet(in1.inf, c1);
fGet(in2.inf, c2);
onestep(in1, in2, out1, c1, c2);
c:=c1+c2;
fPut(out1.inf, c);
if (not fEof(in1.inf)) and (not fEof(in2.inf)) then
begin
fGet(in1.inf, c1);
fGet(in2.inf, c2);
onestep(in1, in2, out2, c1, c2);
c:=c1+c2;
fPut(out2.inf, c);
end;
end;
if fEof(in1.inf) xor fEof(in2.inf) then
if fEof(in1.inf) then
begin
fGet(in2.inf, c2);
Copy(in2, out2, c2);
fPut(out2.inf, c2);
end else
if fEof(in2.inf) then
begin
fGet(in1.inf, c1);
Copy(in1, out2, c1);
fPut(out2.inf, c1);
end;
fClose(in1.main);
fClose(in2.main);
fClose(in1.inf);
fClose(in2.inf);
fClose(out1.main);
fClose(out2.main);
fClose(out1.inf);
fClose(out2.inf);
end;


{Копирование файла f1 в f2.(Используется при завершении работы для
копирования конечного файла из временной директории в указанную).}
procedure FCopy(f1, f2: tfile);
var t: longint;
begin
write('копирование');
fRewrite(f2);
fReset(f1);
while (not fEof(f1)) do
begin
fGet(f1, t);
fPut(f2, t);
end;
fClose(f1);
fClose(f2);
end;


{Принимает значение True, если файл отсортирован и больше не надо склеивать.
(Условие выхода)}
function Fin: boolean;
begin
fReset(t2.main);
fReset(t4.main);
if fEof(t2.main) then
begin
Fin:=true;
FCopy(t1.main, dest.main);
end else
if fEof(t4.main) then
begin
Fin:=true;
FCopy(t3.main, dest.main);
end else Fin:=false;
fClose(t2.main);
fClose(t4.main);
end;

begin
writeln;
if ParamCount<2 then
begin
writeln('Слишком мало параметров.');
Exit;
end;
write('Инициализация...');
Init;
writeln('готово');
write('Первоначальная сортировка...');
firstsort(seur, t1, t2);
writeln('готово');
ReWrite(dest.main.f);
Close(dest.main.f);
writeln('Склеивание:');
repeat
ftrans(t1, t2, t3, t4);
writeln('шаг');
if (not Fin) then
begin
ftrans(t3, t4, t1, t2);
writeln('шаг');
end;
until Fin;
writeln('готово');
end.
{----------------------------------------------------------------------------}

5. Внешняя спецификация

Для корректной работы программы необходим компьютер AT286, 40K свободной conventional памяти, операционная система MS-DOS 3.0 или более поздняя версия.

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

6. Руководство пользователя

При запуске программы обязательно должна быть определена переменная среды TEMP!

Формат запуска программы:  f_sort[.exe] <входной файл> <выходной файл>

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

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

Причинами ошибок могут служить не соответствие системы требованиям, изложенным в п. 6, недостаточное место на диске, размер(в байтах) исходного файла не кратен 4.

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

7. Описание тестов

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

При тестировании использовались операционные системы MS-DOS 6.22, Windows`95, компьютеры PC AT 486DX4-100, 486SX-25, работающие с локальным винчестером, рабочие станции 486DX-40, 386SX, работающие в сети Novell.

Результаты тестирования(на файле размером 4M) занесены в таблицу: компьютер работа в сети время работы

486DX4-100 нет 3 мин.
486SX-25 нет 7 мин.
486DX-40 да
386SX да



  © Реферат плюс


Поиск

  © REFERATPLUS.RU  

Яндекс.Метрика