VPF::Время выполнения алгоритма. - Форум программистов

Kemix

Дата 21.4.2012, 23:36 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 15
Регистрация: 21.4.2012

Репутация: нет
Всего: нет

Здравствуйте, уважаемое сообщество.
При решение одной задачи возникла следующас проблема:время измерения алгоритма измеряется неверно.
Сама задача:Сравнить 2 сортировки(Сортировка Пузырьком и Шелла) и снять показания времени выполнения и построить график зависимости времени выполнения каждого алгоритма от количества элементов в массиве.
Сам код:http://pastebin.com/pjtKft4D
Беда:время выполнения болтается в одном и том же диапазоне с увеличением количеством элементов.
Заранее спасибо.

Данкинг

Дата 21.4.2012, 23:50 (ссылка)

(нет голосов)

Загрузка ...

Yersinia pestis

Профиль
Группа: Завсегдатай
Сообщений: 8302
Регистрация: 7.11.2006
Где: მოსკოვი

Репутация: 11
Всего: 130

Код вычисления времени показывай.

--------------------

There's nothing left but silent epitaphs.

northener

Дата 22.4.2012, 00:25 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1361
Регистрация: 2.9.2010

Репутация: 12
Всего: 20

Цитата(Данкинг @ 21.4.2012, 23:50

)

Код вычисления времени показывай.

Он показал код по ссылке, но там ... Короче смотреть и вникать страшно. Например такой перл как:

Код


t1:=GetTickCount;
t1:=RDTSC;
sleep(100);
  for i:=1 to t-1 do
    for j:=i+1 to t do
      if A[i] >= A[j] then begin
        tmp := A[i];
        A[i] := A[j];
        A[j] := tmp;
     end;

t2:=GetTickCount;
t2:=RDTSC;

О! Да там ещё и прямая работа с машинными кодами:

Код


 asm
  db $F;
  db $31;

Не знал, что встроенный ассемблер в Дельфи такое допускает.

Это сообщение отредактировал(а) northener - 22.4.2012, 00:41

--------------------

Но только лошади летают вдохновенно.
Иначе лошади разбились бы мгновенно!

Данкинг

Дата 22.4.2012, 01:28 (ссылка)

(голосов:5)

Загрузка ...

Yersinia pestis

Профиль
Группа: Завсегдатай
Сообщений: 8302
Регистрация: 7.11.2006
Где: მოსკოვი

Репутация: 11
Всего: 130

RDTSC какой-то ещё. Это тоже, оказывается, какая-то ассемблерная инструкция, как Яндекс говорит.

Это сообщение отредактировал(а) Данкинг - 22.4.2012, 01:28

--------------------

There's nothing left but silent epitaphs.

bems

Дата 22.4.2012, 10:33 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 3400
Регистрация: 5.1.2006

Репутация: 18
Всего: 88

Kemix, не у всех процов счетчики rdtsc разных ядер синхронны. Рекомендованная обёртка, использующая этот способ когда это возможно, называется QueryPerformanceCounter

Цитата(northener @ 22.4.2012, 00:25

)

Не знал, что встроенный ассемблер в Дельфи такое допускает.

была инструкция на х64, которую в мне не удавалось сформировать иначе как этим способом. Так что хорошо что оно есть

Это сообщение отредактировал(а) bems - 22.4.2012, 11:20

--------------------

Обижено школьников: 8

Kemix

Дата 22.4.2012, 11:56 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 15
Регистрация: 21.4.2012

Репутация: нет
Всего: нет

Цитата(bems @ 22.4.2012, 10:33

)

Kemix, не у всех процов счетчики rdtsc разных ядер синхронны. Рекомендованная обёртка, использующая этот способ когда это возможно, называется QueryPerformanceCounter

Увы, он выкатил отрицательое значение. - http://pastebin.com/iMkeV1i9
Есть ещё предложения?

bems

Дата 22.4.2012, 11:59 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 3400
Регистрация: 5.1.2006

Репутация: 18
Всего: 88

а какой должно быть значение, если ты делаешь Start - Finish?

--------------------

Обижено школьников: 8

Kemix

Дата 22.4.2012, 13:50 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 15
Регистрация: 21.4.2012

Репутация: нет
Всего: нет

Цитата(bems @ 22.4.2012, 11:59

)

а какой должно быть значение, если ты делаешь Start - Finish?

Оу действительно.
Ну вот и финальной код - http://pastebin.com/W0jeNaNp
Единственная заноза - периодически возникают "скачки" при измерении.
Походу измерение времени в Delphi - реально накипешая проблема.
Тут наткнулся на это - http://habrahabr.ru/post/75234/

Qu1nt

Дата 22.4.2012, 14:27 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 602
Регистрация: 13.1.2007

Репутация: 22
Всего: 50

Delphi здесь ни при чём.

Keeper89

Дата 22.4.2012, 14:33 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2580
Регистрация: 26.2.2009

Репутация: 9
Всего: 58

В последних Delphi можно использовать TStopWatch.

--------------------

Cogito, ergo sum

Keeper's blog
CnWizards Downloads

user posted image

bems

Дата 22.4.2012, 14:50 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 3400
Регистрация: 5.1.2006

Репутация: 18
Всего: 88

Цитата(Kemix @ 22.4.2012, 13:50

)

Единственная заноза - периодически возникают "скачки" при измерении.

потому что переключения процессора с потока на поток и разные эффекты кеширования предсказать заранее нельзя. Если тебе нужно измерить сколько времени работал именно твой код, то есть GetThreadTimes, но там вроде разрешение похуже

--------------------

Обижено школьников: 8

Kemix

Дата 22.4.2012, 17:59 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 15
Регистрация: 21.4.2012

Репутация: нет
Всего: нет

Цитата(bems @ 22.4.2012, 14:50

)

Если тебе нужно измерить сколько времени работал именно твой код, то есть GetThreadTimes, но там вроде разрешение похуже

Разрешение??
Может точность измерения похуже?

bems

Дата 22.4.2012, 21:30 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 3400
Регистрация: 5.1.2006

Репутация: 18
Всего: 88

У таймера есть и то и другое.
Не путай их: http://www.transl-gunsmoker.ru/2010/11/blog-post_15.html

--------------------

Обижено школьников: 8

northener

Дата 23.4.2012, 00:40 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1361
Регистрация: 2.9.2010

Репутация: 12
Всего: 20

Цитата(Kemix @ 22.4.2012, 13:50

)

Единственная заноза - периодически возникают "скачки" при измерении.

Заноза сравнительно легко извлекается путём вычисления "среднего" времени выполнения алгоритма при измерении нескольких вызовов вышеупомянутого.

--------------------

Но только лошади летают вдохновенно.
Иначе лошади разбились бы мгновенно!

Kemix

Дата 25.4.2012, 08:01 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 15
Регистрация: 21.4.2012

Репутация: нет
Всего: нет

Цитата(northener @ 23.4.2012, 00:40

)

Т.е. для одного и того же N несколько раз замерять, а потом среднее арифиметическое вычислять? Чтож, подумаю.
Пока препод в коммандировке выкладываю код. Чуть позже доработаю ещё с учётом данных советов.

Код


program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils,
  windows;

const n=10000;

 type
 mas1=array[1..n] of integer;
 mas2=array[1..n*n] of integer;
var a:mas1;
var ft : text;
WaitCal: Int64;
Start, Finish: Int64;
procedure Wait(ns: Integer);
var
  Counter, Freq, WaitUntil: Int64;
begin
  if QueryPerformanceCounter(Counter) then
  begin
    QueryPerformanceFrequency(Freq);
    WaitUntil := Counter + WaitCal + (ns * (Freq div 1000000));
    while Counter < WaitUntil do
      QueryPerformanceCounter(Counter);
  end
  else
    Sleep(ns div 1000);
end;

procedure prosmotr(a:mas1);
var
  i: Integer;
begin
  for i := 1 to 10 do
   write(' ',a[i]);
   writeln;
end;
 { Заполнение массива числами по возрастанию }
  procedure FillInc( var A : mas1);
    var
      i : longint;
    begin
      for i := 1 to n do
        A[i] := i;
    end;

  { Заполнение массива числами по убыванию }
  procedure FillDec( var A : mas1);
    var
      i : longint;
    begin
      for i := 1 to n do
        A[i] := n-i;
    end;

  { Заполнение массива случайными числами }
  procedure FillRand( var A : mas1);
    var
      i :longint;
    begin
    randomize;
      for i := 1 to n do
        begin
          A[i] := random(21) mod n;
        end;
    end;
{Сортировка пузырьком}
procedure sortbuble(a:mas1; t:longint);
var i,j:integer;
 tmp:integer;
begin
QueryPerformanceCounter(Start);
  for i:=1 to t-1 do
    for j:=i+1 to t do
      if A[i] >= A[j] then begin
        tmp := A[i];
        A[i] := A[j];
        A[j] := tmp;
     end;

QueryPerformanceCounter(Finish);
writeln(ft, t,';',Finish-Start);
writeln;
end;
{Сортировка Шелла}
procedure shell_sort(a:mas1; var v:longint);
var ii, m, x, s, p, t, k, r, i, j : Integer;
begin
QueryPerformanceCounter(Start);
  t := Trunc(Ln(n) / Ln(2));
 repeat
    t := t - 1;
    k := (1 shl t) - 1;
    p := v mod k;
    s := v div k;
   if p = 0 then
      p := k
   else
      s := s + 1;
   for i := 1 to k do {берём и длинные, и короткие подпоследовательности}
   begin
     if i = p + 1 then
        s := s - 1; {для коротких — уменьшаем длину}
     for j := 1 to s - 1 do {метод ПрВст с шагом k}
       if a[i + (j - 1) * k] > a[i + j * k] then
       begin
          x := a[i + j * k];
          m := i + (j - 1) * k;
         while (m > 0) and (a[m] > x) do
         begin
            a[m + k] := a[m];
            m := m - k;
         end;
          a[m + k] := x;
       end;
   end;
 until k = 1;
 QueryPerformanceCounter(Finish);
writeln(ft, v,';',Finish-Start);
end;
var i:longint;
begin
assign(ft, 'log.txt');
append(ft);
writeln('Sravnenie pusirka i shella');
writeln(ft,'uporyad');
FillRand(a);
write('UCX:');
prosmotr(a);
write(ft,'sortirovka pusirkom ');
for i := 1 to 10000 do begin
sortbuble(a,i);
end;
write(ft,'Shell');
for i := 1 to 10000 do begin
shell_sort(a,i);
end;
writeln;
writeln('RANDOM');
writeln(ft,'RANDOM');
FillRand(a);
write('UCX:');
prosmotr(a);
write(ft,'sortirovka pusirkom ');
for i := 1 to 10000 do begin
sortbuble(a,i);
end;
writeln(ft,'Shell');
for i := 1 to 10000 do begin
shell_sort(a,i);
end;
writeln(ft,'Ubivanie');
FillDec(a);
write('UCX:');
prosmotr(a);
write(ft,'sortirovka pusirkom ');
for i := 1 to 10000 do begin
sortbuble(a,i);
end;
writeln(ft,'Shell');
for i := 1 to 10000 do begin
shell_sort(a,i);
end;
write('GOTOVO');
readln;
end.

UPD:Ничего не потребовалось редактировать, приняли так. Всем спасибо за помощь.

Это сообщение отредактировал(а) Kemix - 12.5.2012, 19:18

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Delphi: Для новичков \| Следующая тема »