StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The only fair comparison is the shortest completion time on a common piece of hardware. The time to complete a program is entirely hardware dependent otherwise what would be the point of spending money on more power machines? </p> <p>The closest you can get to reproducible results is report a relative speed, e.g. provide a sample program and report in term of the users program running in say 50% of the time. A program which is twice as fast on one PC will likely to be twice as fast on another.</p> <p>At uni, we would submit assignments which would run against "secret" inputs, however we could submit more than once to correct errors. My first submission didn't work at all but would log all the inputs. ;)</p> <p>EDIT: A longer answer.</p> <p>Consider the following program</p> <pre><code>public class FibMain { public static void main(String... args) { { long start = System.nanoTime(); System.out.println(iteration_fib(Integer.parseInt(args[0]))); long time = System.nanoTime() - start; System.out.printf("Iteration took %,d us%n", time / 1000); } { long start = System.nanoTime(); System.out.println(recursive_fib(Integer.parseInt(args[0]))); long time = System.nanoTime() - start; System.out.printf("Recursion took %,d us%n", time / 1000); } } public static long iteration_fib(int n) { long t1 = 1; long t2 = 1; while (n-- > 2) { long t = t2; t2 += t1; t1 = t; } return t2; } public static long recursive_fib(int n) { if (n <= 2) return 1; return recursive_fib(n - 1) + recursive_fib(n - 2); } } </code></pre> <p>If you look at the generated byte code with javap -c you see</p> <pre><code>public static long iteration_fib(int); Code: 0: lconst_1 1: lstore_1 2: lconst_1 3: lstore_3 4: iload_0 5: iinc 0, -1 8: iconst_2 9: if_icmple 25 12: lload_3 13: lstore 5 15: lload_3 16: lload_1 17: ladd 18: lstore_3 19: lload 5 21: lstore_1 22: goto 4 25: lload_3 26: lreturn public static long recursive_fib(int); Code: 0: iload_0 1: iconst_2 2: if_icmpgt 7 5: lconst_1 6: lreturn 7: iload_0 8: iconst_1 9: isub 10: invokestatic #13; //Method recursive_fib:(I)J 13: iload_0 14: iconst_2 15: isub 16: invokestatic #13; //Method recursive_fib:(I)J 19: ladd 20: lreturn </code></pre> <p>So the first example is longer that the second so you might suspect the first one takes longer. However, you would be incorrect for cases where 'n' is an interesting size.</p> <p>I ran FibMain 44 on my machine and got the following result.</p> <pre><code>701408733 Iteration took 495 us 701408733 Recursion took 19,174,036 us </code></pre> <p>This is because the time taken to perform iteration is proportional to n (in this case 44) ad it grows linearly however the time taken for recursion is proportional to the result (in this case 701408733) and that grows exponentially.</p> <p>If you try 50 as input the first completes in a blink, the second takes so long I got bored of waiting.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload