Лабораторная работа №1

Санкт-Петербургский Государственный Электротехнический Университет

(ЛЭТИ)

кафедра МО ЭВМ

Отчет по лабораторной работе №1

Расчет метрических характеристик качества разработки программ по метрикам Холстеда

Выполнил студент группы 1382, ФКТИ

Пухкал И.

Санкт-Петербург 2006

2 Исходные тексты программ

2

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

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

Для каждой из разработанных программ (включая исходную программу на Паскале) определить следующие метрические характеристики (по Холстеду):

1.Измеримые характеристики программ:

•число простых(отдельных)операторов, в данной реализации;

•число простых (отдельных) операндов, в данной реализации;

•общее число всех операторов в данной реализации;

•общее число всех операндов в данной реализации;

•число вхождений j-го оператора в тексте программы;

•число вхождений j-го операнда в тексте программы;

•словарь программы;

•длину программы.

2.Расчетные характеристики программы:

•длину программы;

•реальный, потенциальный и граничный объемы программы;

•уровень программы;

•интеллектуальное содержание программы;

•работа программиста;

•время программирования;

•уровень используемого языка программирования;

•ожидаемое число ошибок в программе.

Для каждой характеристики следует рассчитать как саму характеристику, так и ее оценку.

2. Исходные тексты программ

Pascal

Листинг 1. Быстрая сортировка — нерекурсивный вариант (Pascal).

program prog_pas;

type

TArray = array [1..10] of real ;

5

2 Исходные тексты программ

3

procedure swap(var p,q: real); var hold : real ;

begin hold:=p;

10p:=q;

q:=hold

		end;	{ swap }
	15	procedure qsort(var x: TArray; n: integer);
		var left , right		: array [1..20] of integer ;
		i , j ,sp,mid		: integer ;
		pivot		: real ;
	20	begin
		left [1]:=1;
		right [1]:=n;
		sp:=1;
		while sp>0 do
	25	begin

if left [sp]>=right[sp] then begin sp:=sp−1

end

else begin

30i:=left [sp ]; j:=right[sp ]; pivot:=x[j ]; mid:=(i+j)div 2;

if ( j−i)>5 then begin

35	if (( x[mid]<pivot)and(x[mid]>x[i])) or ((x[mid]>pivot)and(x[mid]<x[i])) then
		begin
	swap(x[mid],x[j ])
	end
	else begin
		if ((x[ i]<x[mid])and(x[i]>pivot)) or ((x[i]>x[mid])and(x[i]<pivot)) then begin
40		swap(x[i ], x[ j ]) ;
	end;
	end;
	end;
	pivot:=x[j ];
45	while i<j do begin
	while x[i]<pivot do begin
		i:=i+1;
	end;
	j:=j−1;
50	while (i<j)and(pivot<x[j]) do begin
		j:=j−1;
	end;
	if	i<j then swap(x[i],x[j ])
	end;	{ while }
55	j:=right[sp ];		{ pivot to i }
	swap(x[i ], x[ j ]) ;
	if i−left[sp]>=right[sp]−i then begin { put shorter part first }
	left [sp+1]:=left[sp ];
	right [sp+1]:=i−1;
60	left [sp]:=i+1
	end
	else begin
	left [sp+1]:=i+1;
	right [sp+1]:=right[sp];
65	right [sp]:=i−1
	end;
	sp:=sp+1		{ push stack }
end;		{ if	}
end	{ while }

70end; { QUICK SORT }

begin

k := 1;

while (not eof(F)) do begin

75 read(F, a[k]); k := k + 1;

end;

m := k − 1;

2 Исходные тексты программ

4

qsort(a , m);

80 for k := 1 to m do begin write(F, a[k]) ;

end; end.

C

Листинг 2. Быстрая сортировка — нерекурсивный вариант (C).

typedef double TArray[20];

void swap(double &p, double &q) { double tmp = p;

5 p = q;

q = tmp;

}

void qsort(TArray &x, int n) {

10int left [21]; int right [21]; left [1] = 1;

right [1] = n; int sp = 1;

15int i = 0; int j = 0; int mid = 0;

	double pivot;
	while (sp) {
20	if	( left [sp] >= right[sp]) {
	}	sp−−;
	else {
		i = left [sp ];
25		j = right [sp ];
		pivot = x[j ];
		mid = ((i+j) / 2);
		if (( j − i) > 5) {
	if	( (( x[mid] < pivot) && (x[mid] > x[i]))	|| (( x[mid] > pivot) && (x[mid] < x[i])) ) {
30	}	swap(x[mid], x[j ]) ;
	else {
		if ( (( x[ i ] < x[mid]) && (x[i] > pivot))	|| (( x[ i ] > x[mid]) && (x[i] < pivot)) ) {
		swap(x[i ], x[ j ]) ;
35		}
		}
		}
		pivot = x[j ];
		while (i < j) {
40		while (x[ i ] < pivot) {
		i++;
		}
		j−−;
		while ((i < j) && (pivot < x[j])) {
45		j−−;
		}
		if ( i < j) {
		swap(x[i ], x[ j ]) ;
		}
50		}
		j = right [sp ];
		swap(x[i ], x[ j ]) ;
		if ( i − left [sp] >= right[sp] − i ) {
		left [sp+1] = left[sp ];
55		right [sp+1] = i − 1;
		left [sp] = i + 1;
		}
		else {
		left [sp+1] = i + 1;
60		right [sp+1] = right[sp ];
		right [sp] = i − 1;
		}

2 Исходные тексты программ

5

sp++;

}

65 }

}

void main() {

70FILE file ; TArray a; int k = 0; int m = 0;

char ch;

75double value = 0; gets( file , k+1, ch); while (ch != EOF) {

fscanf ( file , "%d", &value);

	a[k] = value;
80	k++;
	gets( file , k+1, ch);
	}
	m = k − 1;
	qsort(&a, m);
85	for (k = 0; k <= m; k++) {
	fprintf ( file , "%d", a[k]) ;
	}

return;

}

3 Выполнение работы

6

3. Выполнение работы

3.1.	Измеримые свойства алгоритмов
3.1.1.	Pascal
	Операторы				Операнды
Оператор		Вхождений		Операнд		Число вхо-
						ждений
program		1		prog_pas		1
procedure		1		1		23
swap
procedure		1		2		1
qsort
begin .. end		28		5		1
+ ( .. )
[..]		44		10		1
+		10		20		1
-		8
div		1		p		3
=		1		q		3
:=		27		hold		3
;		47		x		25
<		9		n		2
>=		2		left		9
>		6		right		10
and		5		i		26
or		2		j		19
swap		5		sp		22
if		7		mid		9
while		5		pivot		10
for		1		k		7
not		1		m		3
eof		1		F		3
read		1		a		3
write		1
qsort		1

Число уникальных операторов η1 = 25. Общее число всех операторов N1 = 209. Число уникальных операндов η2 = 23. Общее число всех операн-

дов N2 = 186.

Словарь программы η = 25+23 = 48. Длина программы N = 209+186 = 395.

Теоретическая оценка длины ˆ = 20 log 20+22 log 22 = 86 438+98 107 =

220.138. 115% = 253.159.

N 2 2 . .

3 Выполнение работы				7
3.1.2. C
Операторы				Операнды
Оператор	Вхождений		Операнд		Число вхо-
					ждений
void main	1
void swap	1		0		4
void qsort	1		1		15
=	25		2		1
[...]	46		5		1
{...} (...)	48		20		1
&&	5		21		2
||	2		p		3
;	48		q		3
>=	2		tmp		2
<	9		x		25
>	7		n		2
-	6		left		9
/	1		right		10
++	4		sp		19
--	3		i		24
if	6		j		17
while	4		mid		9
swap	5		pivot		9
+	9		k		9
<=	1		m		3
qsort	1		a		3
gets	2		file		4
fscanf	1		EOF		1
fprintf	1		ch		3
&	1		value		2
for	1

Число уникальных операторов η1 = 26. Общее число всех операторов N1 = 241. Число уникальных операндов η2 = 25. Общее число всех операн-

дов N2 = 181.

Словарь программы η = 26+25 = 41. Длина программы N = 241+181 = 422.

Теоретическая оценка длины ˆ = 26 log 26+25 log 25 = 238 308. 115% =

274.054.

N 2 2 .

3 Выполнение работы					8
3.1.3. Assembler
Операторы				Операнды
Оператор		Вхождений		Операнд	Число вхо-
					ждений
proc		2
push		14		word ptr[bp +	2
				4]
mov		93		word ptr[bp +	2
				6]
fld		15		qword ptr[bp	2
				- 8]
fstp		5		word ptr[bp -	3
				56]
fwait		13		word ptr[bp -	3
				98]
pop		14		word ptr[bp -	19
				2]
ret		2		word ptr[bp -	16
				4]
call		4		word ptr[bp -	9
@swap$qrdt1				6]
sub		5		word ptr[bp -	5
				58]
xor		1		word ptr[bp -	6
				100]
inc		4		qword ptr[bp	8
				- 14]
shl		87		word ptr[bp -	20
				16]
lea		15		bp	8
add		24		sp	6
cmp		7		di	30
dec		4		si	14
cwd		1		ax	104
idiv		1		bx	101
fcomp		10		dx	35
fstsw		10		1	87
sahf		10		8	1
jmp @2@870		2		qword	16
				ptr[bx+si]
jmp @2@422		2		cx	8
jmp @2@702		1		0	3
jmp @2@506		1		5	1
jmp @2@562		1		2	1
jmp @2@450		1		qword ptr[di]	2
jmp @2@814		1		qword ptr[si]	2
jl @2@114		1		word ptr[bx]	14
jl @2@786		1

3 Выполнение работы					9
	Операторы				Операнды
	Оператор	Вхождений		Операнд		Число вхо-
						ждений
	jg @@0	1
	jae @2@198	1
	jae @2@282	1
	jae @2@338	1
	jae @2@422	1
	ja @2@254	1
	ja @2@394	1
	ja @2@562	1
	jbe @2@282	1
	jbe @2@422	1
	jb @2@478	1
	jge @2@646	1
	jge @2@702	1
	jge @@1	1
	jl @2@114	1
	jl @2@786	1
	je @@2	1

Число уникальных операторов η1 = 47. Общее число всех операторов N1 = 370. Число уникальных операндов η2 = 29. Общее число всех операн-

дов N2 = 528.

Словарь программы η = 66. Длина программы N = 898.

Теоретическая оценка длины ˆ = 47 log 47+29 log 29 = 401 947. 115% =

462.239.

N 2 2 .

3.2. Расчетные характеристики программы

Число операндов потенциального языка — 10 (сортировка массива из 10 элементов).

Объем программы

		V = N log2 η
		V (2 + η2 ) log2(2 + η2 )
	Характеристика	Pascal			С				Asm
	V	2206.060		2393.763					5427.866
	V			43.020
Уровень программы
				L =		V
						V
		ˆ			2η2
		L =			η1 · N2

4 Протоколы

10

Характеристика

Pascal

С

Asm

L

0.020

0.018

0.008

ˆ

0.010

0.011

0.006

L

Интеллектуальное содержание программы

ˆ

I = L · V

Характеристика

Pascal

С

Asm

I

22.061

26.326

43.423

Работа и расчет времени

E =

V 2

V

T =

E

=

E

St

18

Tˆ = η1 · N2 ·

ˆ

N log2 η

2 · Stη2

Характеристика

Pascal

С

Asm

E

113 126.470

133 145.588

684 837.966

T

11 312.647

13 314.559

68 483.796

ˆ

12 428.262

12 722.994

103 950.205

T

Уровень языка

λ = L · V

Характеристика

Pascal

С

Asm

λ

0.861

0.774

0.344

Число ошибок

B =

E

=

E

Eкрит

3000

ˆ

(V )2

B =

Eкрит · λ

Характеристика

Pascal

С

Asm

B

0.735

0.798

1.809

ˆ

0.717

0.797

1.793

B

4. Протоколы

Pascal

Statistics for module pas.lxm

=====================================

The number of different operators

: 23

The number of different operands

: 24

The total number of operators

: 233

The total number of operands

: 184