Дисциплина МПО
Кафедра МОЭВМ
ОТЧЕТ
по лабораторной работе № 1
Расчёт метрических характеристик качества разработки программ по метрикам Холстеда
Процедура сортировки методом «пузырька».
Вариант №6
Выполнили : Воробьёв А.В.
Группа № 4305
Проверила : Выговская А.С.
«Выполнено» «____» _______ ____
Подпись преподавателя __________________
Санкт-Петербург
2008
Цель работы
Для заданного варианта программы обработки данных, представленной на языке Паскаль, разработать вычислительный алгоритм и варианты программ его реализации на языках программирования Си и Ассемблер. Добиться, чтобы программы на Паскале и Си были работоспособны и давали корректные результаты (это потребуется в дальнейшем при проведении с ними измерительных экспериментов). Для получения ассемблерного представления программы можно либо самостоятельно написать код на ассемблере, реализующий заданный алгоритм, либо установить опцию "Code generation/Generate assembler source" при компиляции текста программы, представленной на языке Си. При этом в ассемблерном представлении программы нужно удалить директивы описаний и отладочные директивы, оставив только исполняемые операторы.
В заданных на Паскале вариантах программ обработки данных важен только вычислительный алгоритм, реализуемый программой. Поэтому для получения более корректных оценок характеристик программ следует учитывать только вычислительные операторы и по возможности исключить операторы, обеспечивающие интерфейс с пользователем и выдачу текстовых сообщений.
В сути алгоритма, реализуемого программой, нужно разобраться достаточно хорошо для возможности внесения в программу модификаций, выполняемых в дальнейшем с целью проведения измерений и улучшения характеристик качества программы.
Для измеряемых версий программ в дальнейшем нужно будет исключить операции ввода данных с клавиатуры и вывода на печать, потребляющие основную долю ресурса времени при выполнении программы. Поэтому можно уже в этой работе предусмотреть соответствующие преобразования исходной программы.
Для каждой из разработанных программ (включая исходную программу на Паскале) определить следующие метрические характеристики (по Холстеду):
1. Измеримые характеристики программ:
- число простых(отдельных)операторов, в данной реализации;
- число простых (отдельных) операндов, в данной реализации;
- общее число всех операторов в данной реализации;
- общее число всех операндов в данной реализации;
- число вхождений j-го оператора в тексте программы;
- число вхождений j-го операнда в тексте программы;
- словарь программы;
- длину программы.
2. Расчетные характеристики программы:
- длину программы;
- реальный, потенциальный и граничный объемы программы;
- уровень программы;
- интеллектуальное содержание программы;
- работа программиста;
- время программирования;
- уровень используемого языка программирования;
-ожидаемое число ошибок в программе.
Для каждой характеристики следует рассчитать как саму характеристику, так и ее оценку.
Расчет оценок программ выполнить двумя способами:
1) вручную или с помощью одного из доступных пакетов математических вычислений DERIVE, MATHCAD или MATLAB.
2) с помощью программы автоматизации расчета метрик Холстеда.
Результаты расчетов представить в виде таблиц с текстовыми комментариями.
Исходный текст на языке Паскаль
Программа 6. Процедура сортировки методом «пузырька».
procedure {bubble} sort(var a: ary; n: integer);
{ adapted from 'Introduction to PASCAL',
R.Zaks, Sybex, 1980 }
var no_change : boolean;
j : integer;
procedure swap(p,q: real);
var hold : real;
begin
hold:=p;
p:=q;
q:=hold
end; { swap }
begin { procedure sort }
repeat
no_change:=true;
for j:=1 to n-1 do
begin
if a[j]>a[j+1] then
begin
swap(a[j],a[j+1]);
no_change:=false
end
end { for }
until no_change
end; { procedure sort }
Общие сведения
Сортировка методом пузырька
Основная идея сортировки (например, по возрастанию) методом пузырька очень простая. Предположим, что у нас N элементов в массиве и индекс каждого элемента лежит в промежутке от 1 до N.
Первый шаг сортировки методом пузырька
Сравниваем первый и второй элементы массива. Если первый элемент больше, чем второй, то меняем их местами.
Сравниваем второй и третий элементы массива. Если второй элемент больше, чем третий, то меняем их местами.
...
Cравниваем предпоследний (N-1) и последний (N) элементы массива. Если предпоследний элемент больше, чем последний, то меняем их местами.
В результате самым последним элементом в массиве у нас окажется самый большой элемент.
Повторяем вышеуказанные действия для части массива, начиная с 1 позиции до N-1.
Второй шаг сортировки методом пузырька
Сравниваем первый и второй элементы массива. Если первый элемент больше, чем второй, то меняем их местами.
Сравниваем второй и третий элементы массива. Если второй элемент больше, чем третий, то меняем их местами.
...
Cравниваем элемент N-2 и элемент N-1 массива. Если (N-2)-й элемент больше, чем элемент N-1, то меняем их местами.
В результате предпоследний элемент в массиве у нас тоже будет на своем, "отсортированном" месте.
Последующие шаги сортировки методом пузырька
Повторяем вышеуказанные действия для части массива, начиная с 1 позиции до N-2, а потом для диапазона 1..N-3 и так далее до диапазона 1..2.
После завершения последнего шага наш массив будет отсортирован по возрастанию.
В предложенной нам программе, все шаги сортировки выполняются над всем массивом.
Тексты программ
На этапе отладки, в программе использовался диалог с пользователем и вывод информации на экран. В финальной версии, в соответствие с требованиями к лабораторной работе, данные функции были удалены.
Pascal
program lab1;
type ary = array [1..10] of real;
procedure sort(var a: ary; n: integer);
var no_change : boolean;
j : integer;
procedure swap(var p,q: real);
var hold : real;
begin
hold:=p;
p:=q;
q:=hold
end;
begin
repeat
no_change:=true;
for j:=1 to n-1 do
begin
if a[j]>a[j+1] then
begin
swap(a[j],a[j+1]);
no_change:=false
end
end
until no_change
end;
var mass: ary; i: integer;
begin
for i:=1 to 10 do mass[11-i]:= i;
sort(mass, 10);
end.
C
typedef float ary[10];
void swap(float &p;,float &q;)
{
float hold = p;
p = q;
q = hold;
}
void sort(ary a, int n)
{
int change;
do {
change = 0;
for (int j=0; j {
if (a[j] > a[j+1])
{
swap(a[j],a[j+1]);
change=1;
}
}
}
while (change);
}
void main()
{
ary mass;
for (int i=0; i<10; i++) mass[9-i] = i+1;
sort(mass,10);
}
Assembler
;
; void swap(float &p;,float &q;)
;
assume cs:_TEXT
@swap$qrft1 proc near
push bp
mov bp,sp
sub sp,4
push si
push di
mov si,word ptr [bp+4]
mov di,word ptr [bp+6]
;
; {
; float hold = p;
;
fld dword ptr [si]
fstp dword ptr [bp-4]
;
; p = q;
;
fld dword ptr [di]
fstp dword ptr [si]
;
; q = hold;
;
fwait
mov ax,word ptr [bp-2]
mov dx,word ptr [bp-4]
mov word ptr [di+2],ax
mov word ptr [di],dx
;
; }
;
pop di
pop si
mov sp,bp
pop bp
ret
@swap$qrft1 endp
;
; void sort(ary a, int n)
;
assume cs:_TEXT
@sort$qpfi proc near
push bp
mov bp,sp
sub sp,4
push si
push di
mov di,word ptr [bp+4]
@2@30:
;
; {
; int change;
; do {
; change = 0;
;
mov word ptr [bp-2],0
;
; for (int j=0; j ;
xor si,si
jmp short @2@170
@2@86:
;
; {
; if (a[j] > a[j+1])
;
mov bx,si
mov cl,2
shl bx,cl
fld dword ptr [bx+di]
mov bx,si
inc bx
mov cl,2
shl bx,cl
fcomp dword ptr [bx+di]
fstsw word ptr [bp-4]
fwait
mov ax,word ptr [bp-4]
sahf
jbe short @2@142
;
; {
; swap(a[j],a[j+1]);
;
mov ax,si
inc ax
mov cl,2
shl ax,cl
mov dx,di
add dx,ax
push dx
mov ax,si
mov cl,2
shl ax,cl
mov dx,di
add dx,ax
push dx
call near ptr @swap$qrft1
pop cx
pop cx
;
; change=1;
;
mov word ptr [bp-2],1
@2@142:
inc si
@2@170:
mov ax,word ptr [bp+6]
dec ax
cmp ax,si
jg short @2@86
;
; }
; }
; }
; while (change);
;
cmp word ptr [bp-2],0
jne short @2@30
;
; }
;
pop di
pop si
mov sp,bp
pop bp
ret
@sort$qpfi endp
;
; void main()
;
assume cs:_TEXT
_main proc near
push bp
mov bp,sp
sub sp,42
push si
;
; {
; ary mass;
; for (int i=0; i<10; i++) mass[9-i] = i+1;
;
xor si,si
jmp short @3@114
@3@58:
mov ax,si
inc ax
mov word ptr [bp-2],ax
fild word ptr [bp-2]
mov bx,9
sub bx,si
mov cl,2
shl bx,cl
lea ax,word ptr [bp-42]
add bx,ax
fstp dword ptr [bx]
fwait
inc si
@3@114:
cmp si,10
jl short @3@58
;
; sort(mass,10);
;
mov ax,10
push ax
lea ax,word ptr [bp-42]
push ax
call near ptr @sort$qpfi
pop cx
pop cx
;
; }
;
pop si
mov sp,bp
pop bp
ret
end
Выполнение работы
Измеримые свойства алгоритмов
Pascal
|
Операторы |
Операнды | ||||
|
№ |
Оператор |
Число вхождений |
№ |
Операнд |
Число вхождений |
|
1 |
() или begin end |
5 |
1 |
1 |
6 |
|
2 |
+ |
2 |
2 |
10 |
3 |
|
3 |
- |
2 |
3 |
11 |
1 |
|
4 |
; |
17 |
4 |
a |
5 |
|
5 |
:= |
8 |
5 |
i |
4 |
|
6 |
> |
1 |
6 |
j |
6 |
|
7 |
[] |
5 |
7 |
n |
2 |
|
8 |
for |
2 |
8 |
p |
3 |
|
9 |
if |
1 |
9 |
q |
3 |
|
10 |
program |
1 |
10 |
true |
1 |
|
11 |
repeat |
1 |
11 |
false |
1 |
|
12 |
sort |
2 |
12 |
no_change |
4 |
|
13 |
swap |
2 |
13 |
mass |
3 |
|
14 |
type |
1 |
14 |
lab1 |
1 |
|
15 |
array |
1 |
15 |
hold |
3 |
|
|
|
|
16 |
ary |
1 |
|
|
Итого: |
51 |
|
Итого: |
47 |
C
|
Операторы |
Операнды | ||||
|
№ |
Оператор |
Число вхождений |
№ |
Операнд |
Число вхождений |
|
1 |
() или {} |
7 |
1 |
0 |
3 |
|
2 |
+ |
3 |
2 |
1 |
5 |
|
3 |
- |
2 |
3 |
9 |
1 |
|
4 |
; |
16 |
4 |
10 |
3 |
|
5 |
= |
8 |
5 |
a |
5 |
|
6 |
> |
1 |
6 |
i |
5 |
|
7 |
[] |
5 |
7 |
j |
7 |
|
8 |
++ |
2 |
8 |
p |
3 |
|
9 |
< |
2 |
9 |
q |
3 |
|
10 |
do while |
1 |
10 |
n |
2 |
|
11 |
for |
2 |
11 |
mass |
3 |
|
12 |
if |
1 |
12 |
hold |
2 |
|
13 |
main |
1 |
13 |
change |
4 |
|
14 |
sort |
2 |
|
|
|
|
15 |
swap |
2 |
|
|
|
|
16 |
typedef |
1 |
|
|
|
|
17 |
ary[] |
1 |
|
|
|
|
18 |
& |
2 |
|
|
|
|
|
Итого: |
59 |
|
Итого: |
46 |
Assembler
|
Операторы |
Операнды | ||||
|
№ |
Оператор |
Число вхождений |
№ |
Операнд |
Число вхождений |
|
1 |
jmp @2@170 |
1 |
1 |
bp |
12 |
|
2 |
jbe @2@142 |
1 |
2 |
sp |
9 |
|
3 |
jg @2@86 |
1 |
3 |
si |
23 |
|
4 |
jne @2@30 |
1 |
4 |
cs |
3 |
|
5 |
jmp @3@114 |
1 |
5 |
di |
10 |
|
6 |
jl @3@58 |
1 |
6 |
ax |
22 |
|
7 |
call ptr @sort$ |
1 |
7 |
dx |
8 |
|
8 |
callptr @swap$ |
1 |
8 |
cl |
10 |
|
9 |
assume |
3 |
9 |
bx |
10 |
|
10 |
push |
12 |
10 |
cx |
4 |
|
11 |
mov |
32 |
11 |
[bp+4] |
2 |
|
12 |
sub |
4 |
12 |
[bp+6] |
2 |
|
13 |
fld |
3 |
13 |
[bp-4] |
4 |
|
14 |
fstp |
2 |
14 |
[bp-2] |
6 |
|
15 |
fwait |
3 |
15 |
[di+2] |
1 |
|
16 |
pop |
12 |
16 |
[bx+di] |
2 |
|
17 |
ret |
3 |
17 |
[bp-42] |
2 |
|
18 |
end |
1 |
18 |
10 |
2 |
|
19 |
xor |
2 |
19 |
9 |
1 |
|
20 |
shl |
5 |
20 |
4 |
2 |
|
21 |
inc |
5 |
21 |
42 |
1 |
|
22 |
fcomp |
1 |
22 |
2 |
5 |
|
23 |
fstsw |
1 |
|
|
|
|
24 |
sahf |
1 |
|
|
|
|
25 |
add |
3 |
|
|
|
|
26 |
dec |
1 |
|
|
|
|
27 |
cmp |
3 |
|
|
|
|
28 |
fild |
1 |
|
|
|
|
29 |
lea |
2 |
|
|
|
|
30 |
, |
51 |
|
|
|
|
|
Итого: |
159 |
|
Итого: |
141 |
Расчетные характеристики программы
|
|
Pascal |
C |
Assembler |
Формула |
|
Число уникальных операторов (n1): |
15 |
18 |
30 |
|
|
Число уникальных операндов (n2): |
16 |
13 |
22 |
|
|
Общее число операторов (N1): |
51 |
59 |
159 |
|
|
Общее число операндов (N2): |
47 |
46 |
141 |
|
|
словарь программы (n): |
31 |
31 |
52 |
n= n1+ n2 |
|
Экспериментальная длина программы (Nэ): |
98 |
105 |
300 |
Nэ= N1+ N2 |
|
| ||||
|
Теоретическая длина программы (  ):
|
122,60 |
123,16 |
245,31 |
 1 log21 + 2 log22
|
|
Объём программы (V): |
485,51 |
520,19 |
1710,13 |
V = Nэ log2 n |
|
Потенциальный объём (V*): |
15,51 |
15,51 |
15,51 |
V* = (2+ 2*) log2( 2+ 2*) (2=4 – количество параметров) |
|
Граничный объем (Vгр ) |
25,85 |
25,85 |
25,85 |
|
|
Уровень программы (L): |
0,032 |
0,030 |
0,009 |
L = 
|
|
Сложность программы (S): |
31,30 |
33,54 |
110,26 |
|
|
Оценка уровня программы (L^): |
0,045 |
0,031 |
0,010 |
|
|
Интеллект программы (I): |
22,04 |
16,33 |
17,79 |
  (N1+N2) log2(1+2)
|
|
Работа по программированию (Е): |
15198 |
17446 |
188561 |
E = 
|
|
Время программирования (T): |
1520 |
1745 |
18856 |
T=  (S=10 – число страудовских «моментов» в секунду)
|
|
Ожидание времени кодирования (T^): |
1338 |
1943 |
13443 |
|
|
Уровень языка программирования (): |
0,495 |
0,462 |
0,141 |
= LV* |
|
Ожидаемое число ошибок (В): |
0,16 |
0,17 |
0,57 |
B= V / 3000 |
Протоколы
Вычисления проводились при ETA=4 (две процедуры по два параметра)
Pascal
Table:
====================================
Operators:
| 1 | 5 | ()
| 2 | 2 | +
| 3 | 2 | -
| 4 | 21 | ;
| 5 | 7 | =
| 6 | 1 | >
| 7 | 5 | []
| 8 | 2 | for
| 9 | 1 | if
| 10 | 1 | program
| 11 | 1 | repeat
| 12 | 2 | sort
| 13 | 2 | swap
| 14 | 1 | type
Operands:
| 1 | 6 | 1
| 2 | 3 | 10
| 3 | 1 | 11
| 4 | 5 | a
| 5 | 1 | ary
| 6 | 1 | false
| 7 | 3 | hold
| 8 | 3 | i
| 9 | 5 | j
| 10 | 1 | lab1
| 11 | 3 | mass
| 12 | 2 | n
| 13 | 4 | no_change
| 14 | 3 | p
| 15 | 3 | q
| 16 | 1 | true
Summary:
=====================================
The number of different operators : 14
The number of different operands : 16
The total number of operators : 53
The total number of operands : 45
Dictionary ( D) : 30
Length ( N) : 98
Length estimation ( ^N) : 117.303
Volume ( V) : 480.875
Potential volume ( *V) : 15.5098
Limit volume (**V) : 25.8496
Programming level ( L) : 0.0322532
Programming level estimation ( ^L) : 0.0507937
Intellect ( I) : 24.4254
Time of programming ( T) : 828.299
Time estimation ( ^T) : 629.555
Programming language level (lambda) : 0.50024
Work on programming ( E) : 14909.4
Error ( B) : 0.201923
Error estimation ( ^B) : 0.160292
C
Table:
====================================
Operators:
| 1 | 6 | ()
| 2 | 3 | +
| 3 | 2 | ++
| 4 | 4 | ,
| 5 | 2 | -
| 6 | 20 | ;
| 7 | 2 | <
| 8 | 8 | =
| 9 | 1 | >
| 10 | 5 | []
| 11 | 1 | _[]
| 12 | 2 | __&
| 13 | 1 | dowhile
| 14 | 2 | for
| 15 | 1 | if
| 16 | 1 | main
| 17 | 2 | sort
| 18 | 2 | swap
| 19 | 1 | typedef
Operands:
| 1 | 3 | 0
| 2 | 5 | 1
| 3 | 3 | 10
| 4 | 1 | 9
| 5 | 5 | a
| 6 | 4 | change
| 7 | 2 | hold
| 8 | 5 | i
| 9 | 7 | j
| 10 | 3 | mass
| 11 | 2 | n
| 12 | 3 | p
| 13 | 3 | q
Summary:
=====================================
The number of different operators : 19
The number of different operands : 13
The total number of operators : 66
The total number of operands : 46
Dictionary ( D) : 32
Length ( N) : 112
Length estimation ( ^N) : 128.816
Volume ( V) : 560
Potential volume ( *V) : 15.5098
Limit volume (**V) : 25.8496
Programming level ( L) : 0.027696
Programming level estimation ( ^L) : 0.0297483
Intellect ( I) : 16.659
Time of programming ( T) : 1123.31
Time estimation ( ^T) : 1202.84
Programming language level (lambda) : 0.429559
Work on programming ( E) : 20219.5
Error ( B) : 0.247396
Error estimation ( ^B) : 0.186667
Выводы
В результате выполнения лабораторной работы заданный алгоритм сортировки был реализован на различных языках программирования (Pascal, C, Assembler). Для созданных программ были оценены метрические характеристики (измеримые и расчетные) по Холстеду.
Расчеты, проведенные вручную согласуются с результатами полученными с помощью автоматизированных средств. Данные для программы на языке Assembler, выглядят правдоподобно.
Программы на языках Си и Паскаль не слишком отличаются по своим метрическим характеристикам. Это объясняется схожестью данных языков программирования. Метрические характеристики программы на языке Ассемблера значительно уступают по сравнению с программами на Паскале и Си (Уровень ошибок больше, работа по программированию и время кодирования значительно больше, сложность программы вдвое больше). Это объясняется низким уровнем языка Ассемблера.