CODEWITHSUNDEEP
performancedelphiloopsrecursion
NaN
NaN

Reputation: 9104

How can I measure the difference of speed of code between loop and recursive method?

Let's say we have to create a calculator, and the first function it has is Fatorial. We can write it as a recursive function or use a loop to get the result. We all know that recursion is more slow because of it's exponential nature. But how to prove it by code and not by counting lines?

I have tried to calculate the amount of milliseconds spent, but with my i7 it is always zero between the initial time and when the code stops.

How can I measure the difference of speed of code between loop and recursive method?

type
  TJanela = class(TForm)
    Instrucao: TLabel;
    Entrada: TEdit;
    Botao: TButton;
    procedure Calcular(Sender: TObject);
  end;

var
  Janela: TJanela;
  Val, Fat, Start, TimeRecursive, TimeLoop: Int64;

function FR(N: Int64): Int64; // Fatorial Recursivo
function FL(N: Int64): Int64; // Fatorial em Loop

implementation

{$R *.dfm}

procedure TJanela.Calcular(Sender: TObject);
begin
  Val := StrToInt(Entrada.Text);
  Start := StrToInt(FormatDateTime('nnsszzz',Now));
  Fat := FR(Valor);
  TimeRecursive := StrToInt(FormatDateTime('nnsszzz',Now)) - Start;
  Start := StrToInt(FormatDateTime('nnsszzz',Now));
  Fat := FL(Valor);
  TimeLoop := StrToInt(FormatDateTime('nnsszzz',Now)) - Start;
  if Val > 25 then
    ShowMessage('Delphi can't calculate above [ 25! ]')
  else
    ShowMessage(' [ ' +
                IntToStr(Val) + '! ] is equal to [ ' +
                FormatFloat('###,###,###,###,###,###',Fat) + ' ]'#13#13+
                'Recursive: [ ' + IntToStr(TimeRecursive) + ' ] ms;'#13+
                'Loop: [ ' + IntToStr(TimeLoop) + ' ] ms;');
end;

function FR(N: Int64): Int64;
begin
  if N <= 1 then
    Result := 1
  else
    Result := N * FR(N - 1);
end;

function FL(N: Int64): Int64;
var
  I: Integer;
begin
  for I := 2 to N - 1 do
    N := N * I;
  if N = 0 then
    Result := 1
  else
    Result := N;
end;

Now that David came with the answer, I asked a question on Mathematics so they can help me to come out with two equations to determine the proximate time a given factorial will spend on the computer in both methods.

Upvotes: 3

Views: 506

Answers (3)

Glen Morse
Glen Morse

Reputation: 2593

if its just for testing, could you put a TimeGetTime() instead of GetTime() before the loop and one after. then just save the value in a list box to see how long it takes.

if that is too slow try QueryPerformanceCounter/QueryPerformanceFrequency

Upvotes: 0

David Heffernan
David Heffernan

Reputation: 613013

You are using quite a low resolution timer and a single evaluation of the factorial function is too fast to even register.

You could use a higher resolution timer, but by far the easiest approach is to time something that takes longer. Instead of timing a single call to factorial, time a thousand, or a million.

If you are actually interested in implementing a fast factorial function, for integer inputs, then you should use a lookup table.

For what it is worth, I think that TStopWatch in the Diagnostics unit is more convenient for timing than the date/time functions.

Upvotes: 8

Ken White
Ken White

Reputation: 125708

Use a profiler. Recent versions of Delphi include limited functionality versions of AQTime, but a search for profiler Delphi here turns up Profiler and Memory Analysis Tools for Delphi here at StackOverflow.

Profilers allow you to evaluate your code in several different ways, including the precise amount of time spent executing various parts of it. You can use the results to determine which takes more (or less) time.

Upvotes: 5

Related Questions