运行速度最快的算法竞赛

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上的速度是它的两倍，它在另一台电脑上的速度可能是它的两倍。

在联合国大学，我们会提交作业，这将与“秘密”的输入，但我们可以提交不止一次，以纠正错误。我的第一个提交根本不起作用，但是会记录所有的输入。;)

编辑:较长的答案。

考虑以下程序

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作为输入，第一个在眨眼之间就完成了，第二个花了很长时间，我厌倦了等待。

Answer 2

您可以使用一些在线工具(如SPOJ )进行竞争(这个工具是免费的，支持Java)。这样，您就有一台参考机器来测量程序的执行时间。

Answer 3

对于(1)为什么不只是执行进程的时间？设计这个谜题，以便实际的处理是时间安排的最主要的方面，而不是进程启动，并且花时间经过几次迭代才能获得平均值。

为(2)提供样本输入，但在现场比赛中使用替代输入。