Ebs (Event Based Sampling)

Address Line Clockticks Source

1

2 " void swap (float arr[], int i, int j)"

01:0030 3 2 {

4 float hold;

01:0048 5 hold = arr[i];

01:0054 6 arr[i]= arr[j];

01:0066 7 arr[j]= hold;

01:0072 8 }

9

10 " void sort(float a[], int n)"

01:0090 11 1 {

12 " int done, jump, i;"

01:00A8 13 jump = n;

01:00AE 14 while (jump > 1)

15 {

01:00B4 16 jump = jump / 2;

17 do {

01:00BF 18 1 done = 1;

01:00C6 19 for (int j = 0; j < (n - jump); j++)

20 {

01:00E3 21 i = j + jump;

01:00EC 22 if (a[j] > a[i])

23 {

01:0105 24 " swap(a, i, j);"

01:0119 25 done = 0;

26 }

01:0120 27 }

01:0122 28 } while(! done) ;

01:0128 29 }

01:012A 30 }

31

32

33 int main()

01:0140 34 34 {

35 float array[10000];

01:0162 36 37 for(int i = 0; i < 10000; i++)

37 {

01:0189 38 57 array[i] = 10000-i;

01:01AD 39 41 }

01:01AF 40 " sort(array, 8);"

41

42

01:01C0 43 return 0;

01:01C2 44 }

45

Так как операторы ввода/вывода занимают большую часть времени выполнения программы, операторы вывода были удалены, а ввод был заменен автоматической генерацией массива.

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

5. Профилирование программы sort.Pas tbs (Time Based Sampling)

Address Line Clockticks Source

1 program Project1;

2

3 {$APPTYPE CONSOLE}

4

5 uses

6 SysUtils;

7

8 type Tarr = array [1..10000] of real;

9

10 var j: integer;

11 procedure sort(var a: Tarr; n: integer);

12

13 var done : boolean;

14 " jump,i,j: integer;"

15

16 " procedure swap(var p,q: real);"

17 var hold : real;

18

01:7178 19 begin

01:717E 20 hold:=p;

01:7189 21 p:=q;

01:7193 22 q:=hold

01:719E 23 end;

24

01:71A4 25 begin

01:71B0 26 jump:=n;

01:71B7 27 while jump>1 do

28 begin

01:71BE 29 jump:=jump div 2;

30 repeat

01:71CD 31 done:=true;

01:71CF 32 for j:=1 to n - jump do

33 begin

01:71E1 34 i:=j+jump;

01:71E7 35 2 if a[j]>a[i] then

36 begin

01:71F2 37 " swap(a[j],a[i]);"

01:71FD 38 done:=false

39 end

40 end

01:71FF 41 until done

42 end

01:7211 43 end;

44

45 var mass: Tarr;

01:7280 46 begin

47

01:7298 48 for j:=1 to 10000 do mass[j]:= 10000-j;

01:72BE 49 " sort(mass, 100000);"

01:72CD 50 end.

51