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

Question

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.

This blog post -- http://blog.barrkel.com/2008/08/anonymous-methods-in-testing-profiling.html -- shows how you can profile code using anonymous methods. — Nick Hodges, Feb 09 '13 at 14:49

David Heffernan · Accepted Answer · 2013-02-09T11:53:34.063

8

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.

edited Feb 09 '13 at 11:53

answered Feb 09 '13 at 08:10

David Heffernan

601,492
42
1,072
1,490

It works! I added "for I := 1 to 1000000 do" before "Factorial(N)" and the result was 145ms for Recursive and 81ms for Loop approach. Thanks! – NaN Feb 09 '13 at 12:53
1

Try a lookup table. Should be a lot faster still. – David Heffernan Feb 09 '13 at 12:54
In the loop method I got 3ms in 0! and 84 in 20! In recursive method I got 3ms in 0! and 145ms in 20! – NaN Feb 10 '13 at 15:47
Now I am trying to come out with a equation to register the results beyond. – NaN Feb 10 '13 at 15:49
I cannot understand what point you are trying to make with those comments. – David Heffernan Feb 10 '13 at 15:50
The difference between 84 ms and 145 basically tells you nothing. Try some more tests which should take 10 and 100 times longer. Once you have a string of tests you can see a trend. – Pieter B Feb 11 '13 at 13:15
You don't need a profiler. Just time something that takes longer to run. Try for at least 5 seconds. – David Heffernan Feb 11 '13 at 13:36

score 5 · Answer 2 · edited May 23 '17 at 12:25

5

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.

edited May 23 '17 at 12:25

Community

1
1

answered Feb 09 '13 at 02:50

Ken White

123,280
14
225
444

NOTE: AQTime has been known to cause abnormal issues in the IDE in Delphi XE2 Update 4 - There was an issue of randomly breaking the code completion features. Refer to a question of mine: http://stackoverflow.com/questions/10037719/complete-class-at-cursor-not-working – Jerry Dodge Feb 09 '13 at 05:36
Also codesite is pretty simple to set up and will give you time tools – Glen Morse Feb 09 '13 at 06:29
1

If you use a profiler you need to be very careful that the act of profiling does not change the time taken to run the code under profile. – David Heffernan Feb 09 '13 at 08:26

score 0 · Answer 3 · answered Feb 10 '13 at 04:11

0

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

answered Feb 10 '13 at 04:11

Glen Morse

2,437
8
51
102

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

3 Answers3