运行速度最快的算法竞赛

Question

我想参加像代码高尔夫比赛这样的比赛,但获胜者将拥有最快的算法,而不是最小的代码.

• 测量算法速度的一种公平方法是使用中性虚拟机,如Java的JVM.有没有一种简单的方法可以知道执行的JVM指令总数？(如果条目使用多个线程,那么JVM指令的总数将在所有线程中求和.)

例如,代码

public class simple {
    public static int main(String argc[]) {
        int i;

        i = 3;
        while (i > 0) {
            i--;
        }

    return 0;
    }
}

生成JVM代码

0:  iconst_3
1:  istore_1
2:  iload_1
3:  ifle    12
6:  iinc    1, -1
9:  goto    2
12: iconst_0
13: ireturn

它需要(如果我已经正确计算)18个JVM指令来运行.

• 我希望人们能够在家里办理他们的参赛作品,看看评委会看到什么.显然,如果我将输入提供给程序,最快的解决方案是吐出记忆的预先计算的答案.有没有办法客观地让人们在家里运行程序而不是看到回忆的答案？

• 还有哪些其他问题阻碍了非正式的"最快的代码竞争"的发生？

谢谢!

Answer 1

唯一公平的比较是在一个共同的硬件上最短的完成时间.完成一个程序的时间完全取决于硬件,否则在更多动力机器上花钱的重点是什么？

可以获得可重现结果的最接近的是报告相对速度,例如提供示例程序并按照50%的时间运行的用户程序报告.在一台PC上速度提高一倍的程序可能是另一台PC的两倍.

在uni,我们会提交针对"秘密"输入的分配,但是我们可以多次提交以纠正错误.我的第一次提交根本不起作用,但会记录所有输入.;)

编辑:更长的答案.

考虑以下程序

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);
    }
}

如果你用javap -c查看生成的字节代码,你会看到

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

所以第一个例子比第二个例子长,所以你可能会怀疑第一个例子需要更长的时间.但是,对于'n'是一个有趣的大小的情况,你会不正确.

我在我的机器上运行了FibMain 44,得到了以下结果.

701408733
Iteration took 495 us
701408733
Recursion took 19,174,036 us

这是因为执行迭代所花费的时间与n(在这种情况下为44)成比例,并且它线性增长,但递归所花费的时间与结果成比例(在这种情况下为701408733)并且呈指数增长.

如果你尝试50作为输入,第一个完成眨眼,第二个花了这么长时间,我厌倦了等待.