Лабораторная работа №1
.pdfСанкт-Петербургский Государственный Электротехнический Университет
(ЛЭТИ)
кафедра МО ЭВМ
Отчет по лабораторной работе №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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|