4.2.1. Текст программы
Program laba;
uses Sampler;
type ary=array[0..1000] of real;
const PName: String[10] = 'prog.pas';
procedure sort(var a: ary; n: integer);
var done : boolean;
jump,i,j: integer;
procedure swap(var p,q: real);
var hold : real;
begin
hold:=p;
p:=q;
q:=hold
end; { swap }
begin
jump := n;
while jump > 1 do
begin
jump := jump div 2;
repeat
done := true;
for j := 1 TO n - jump dO
begin
i := j + jump;
if a[j] > a[i] then
begin
swap(a[j], a[i]);
done := false
end { if }
end { for }
until done
end { while }
end; { sort }
var list : ary;
begin
Sample(PName,55);
randomize;
for i:=0 to 1000 do
list[i]:=random;
sort(list, 1000);
Sample(PName, 59);
end.
4.2.2. Результат профилировки
----------------------------------------------------------------------
Исх.Поз. Прием.Поз. Общее время(мкс) Кол-во прох. Среднее время(мкс)
----------------------------------------------------------------------
1 : 55 1 : 59 10310.62 1 10310.62
----------------------------------------------------------------------
4.2.3. Текст программы
Program laba;
uses Sampler;
type ary=array[0..1000] of real;
const PName: String[10] = 'prog.pas';
procedure sort(var a: ary; n: integer);
var done : boolean;
jump,i,j: integer;
procedure swap(var p,q: real);
var hold : real;
begin
Sample(PName,14);
hold:=p;
Sample(PName,16);
p:=q;
Sample(PName,18);
q:=hold;
Sample(PName,20);
end; { swap }
begin
Sample(PName,24);
jump := n;
Sample(PName,26);
while jump > 1 do
begin
jump := jump div 2;
Sample(PName,30);
repeat
done := true;
Sample(PName,33);
for j := 1 TO n - jump dO
begin
i := j + jump;
Sample(PName,37);
if a[j] > a[i] then
begin
Sample(PName,41);
swap(a[j], a[i]);
Sample(PName,43);
done := false;
Sample(PName,45);
end { if }
end { for }
until done
end; { while }
Sample(PName,50);
end; { sort }
var list : ary; i:integer;
begin
randomize;
Sample(PName,55);
for i:=0 to 1000 do
list[i]:=random;
Sample(PName,57);
sort(list, 1000);
Sample(PName, 59);
end.
4.2.4. Результат профилировки
----------------------------------------------------------------------
Исх.Поз. Прием.Поз. Общее время(мкс) Кол-во прох. Среднее время(мкс)
----------------------------------------------------------------------
1 : 14 1 : 16 900.41 7509 0.12
----------------------------------------------------------------------
1 : 16 1 : 18 941.42 7509 0.13
----------------------------------------------------------------------
1 : 18 1 : 20 782.11 7509 0.10
----------------------------------------------------------------------
1 : 20 1 : 43 502.52 7509 0.07
----------------------------------------------------------------------
1 : 24 1 : 26 0.03 1 0.03
----------------------------------------------------------------------
1 : 26 1 : 30 0.07 1 0.07
----------------------------------------------------------------------
1 : 30 1 : 33 0.22 9 0.02
----------------------------------------------------------------------
1 : 33 1 : 37 3.60 62 0.06
----------------------------------------------------------------------
1 : 37 1 : 41 2798.60 7509 0.37
1 : 37 1 : 37 13262.20 51143 0.26
1 : 37 1 : 33 9.83 49 0.20
1 : 37 1 : 30 2.69 8 0.34
1 : 37 1 : 50 0.40 1 0.40
----------------------------------------------------------------------
1 : 41 1 : 14 1202.32 7509 0.16
----------------------------------------------------------------------
1 : 43 1 : 45 668.02 7509 0.09
----------------------------------------------------------------------
1 : 45 1 : 37 434.97 7505 0.06
1 : 45 1 : 33 0.25 4 0.06
----------------------------------------------------------------------
1 : 50 1 : 59 0.31 1 0.31
----------------------------------------------------------------------
1 : 55 1 : 57 156.54 1 156.54
----------------------------------------------------------------------
1 : 57 1 : 24 0.33 1 0.33
----------------------------------------------------------------------
Основное узкое место - рандомизация массива.
5. Оптимизация программы
Оптимизация программы будет заключаться в том, что функция swap будет включена в тело процедуры сортировки.
5.1. Программа на языке С