4

I have 2 methods in java (for example Factorial calculation) and i have to test these 2 methods to find which one is faster. I have that code as Recursion and as for loop:

They both in the same Class data.

    public long FakultaetRekursiv( int n){
        if(n == 1){
        return 1;
        }
        else{
        return FakultaetRekursiv(n-1) * n;
        }
    }


    public long Fakultaet( int n){
        int x=1;
        for(int i=1; i<=n; i++){
            x= x*i;
        }
        return x;       
    }

I heard currentTimeMillis() could help a little but i dont know how to do exactly. Thanks.

altank52
  • 41
  • 3
  • 1
    You should implement it by looking up the result in an array where all possible values are stored. That is quite sure the fastest implementation of *Fakultaet*. – MrSmith42 Jan 24 '13 at 20:10
  • 1
    Neither of these methods will run long enough to be optimised or to matter. – Peter Lawrey Jan 24 '13 at 20:11
  • 1
    You should change your recursive implementation to check `n==0` instead of `n==1` because *0! == 1* by definition. And maybe throw an Exception for negative n values. – MrSmith42 Jan 24 '13 at 20:12

4 Answers4

8

Micro-benchmarking is hard, use the right tools, for example Caliper. Here is an example that will work for you:

import com.google.caliper.SimpleBenchmark;

public class Benchmark extends SimpleBenchmark {

    @Param({"1", "10", "100"}) private int arg;

    public void timeFakultaet(int reps) {
        for (int i = 0; i < reps; ++i) {
            Fakultaet(arg);
        }
    }

    public void timeFakultaetRekursiv(int reps) {
        for (int i = 0; i < reps; ++i) {
            FakultaetRekursiv(arg);
        }
    }

}

The framework will run tour time*() methods a lot of times, moreover it will inject different arg values and bechmark them separately.

Community
  • 1
  • 1
Tomasz Nurkiewicz
  • 334,321
  • 69
  • 703
  • 674
  • 1
    Make sure you do not ignore the result of the test-method. Once I had the case that my whole method seamed to be removed while optimization because the result was never used in the test loop. – MrSmith42 Jan 24 '13 at 20:09
  • @MrSmith42: +1. This problem is described in caliper documentation and caliper even tries to discover it. I wanted to keep the example short. – Tomasz Nurkiewicz Jan 24 '13 at 20:13
  • thank you so much for your comments guys. i learned a lot from you. But there is little thing that i supposed to use currentTimeMillis() to compare loop or recursive way works faster. Any ideas ? – altank52 Jan 24 '13 at 20:33
3

Always go by the basics ! Just use this to find the time taken by each of the functions

long startTime = System.nanoTime();
methodToTime();
long endTime = System.nanoTime();

long duration = endTime - startTime;
Aakash Anuj
  • 3,773
  • 7
  • 35
  • 47
  • if i try to modify that with my code, i get a "unreachable statement" compiler mistake. how can i modify ? – altank52 Jan 24 '13 at 20:11
3
long start = System.currentTimeMillis();

// your code here 

System.out.println(System.currentTimeMillis() - start + "ms");
isvforall
  • 8,768
  • 6
  • 35
  • 50
  • well, when i want modify my codes with your solution. i reach a compile mistake(unreachable statement). so i made another class `public long getLastRuntime(){ long start = System.currentTimeMillis(); return start; } ` and i changed my new code so `public long FakultaetRekursiv( int n){ if(n == 1){ return 1; } else{ return FakultaetRekursiv(n-1) * n; } System.out.println(System.currentTimeMillis() - getLastRuntime() + "ms"); }` – altank52 Jan 24 '13 at 20:06
  • @altank52 maybe you are paste after `return` statement. Pls, show your code – isvforall Jan 24 '13 at 20:13
  • @altank52 paste `System.out.println(System.currentTimeMillis() - getLastRuntime() + "ms");` before `return` – isvforall Jan 24 '13 at 20:18
  • In here it wont look nicely but sure :`public class Rekursion{ public long getLastRuntime(){ long start = System.currentTimeMillis(); return start; } public long Fakultaet( int n){ int x=1; for(int i=1; i<=n; i++){ x= x*i; } return x; } public long FakultaetRekursiv( int n){ if(n == 1){ return 1; } else{ return FakultaetRekursiv(n-1) * n; } System.out.println(System.currentTimeMillis() - getLastRuntime() + "ms"); } }` – altank52 Jan 24 '13 at 20:18
  • when i paste that before the return statement, i get 0 ms back for whole loop :( – altank52 Jan 24 '13 at 20:24
  • @altank52 try this: `long start = System.currentTimeMillis(); //invoke FakultaetRekursiv here System.out.println(System.currentTimeMillis() - start + "ms");` – isvforall Jan 24 '13 at 20:32
  • we are working now on the Classes not on the demo program. i am sure your advices works on normal Main program(i tried and its work). But in class program that contains methods, i always have problem. – altank52 Jan 24 '13 at 20:39
  • @altank52 Do this invoke(start finish) outside of recursion method – isvforall Jan 24 '13 at 20:54
-1

You can also do it by hand:

The first method can be described with a recurrence relation of F(x) = F(x-1) * x which generates the pattern...

F(x) = F(x-1) * x
= F(x-2)*x*(x-1)
= F(x-3)*x*(x-1)*(x-2)
. . .
= k*n

which is O(n).

Obviously, the second method can be described by O(n) as well, which means they are in the same upper bound. But this can be used as a quick check before implementing timing solutions.

sdasdadas
  • 23,917
  • 20
  • 63
  • 148