java - 运行最快的算法竞赛

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 指令来运行。

我希望人们能够在家中运行他们的参赛作品，并看看评委会看到什么。显然，如果我向程序提供输入，最快的解决方案是吐出记忆的、预先计算的答案。有什么方法可以客观地让人们在家里运行程序并且看不到记忆的答案？
还有哪些其他问题阻止了非正式的“最快代码竞争”的发生？

谢谢！

score 5 · Accepted Answer

唯一公平的比较是在普通硬件上的最短完成时间。完成一个程序的时间完全取决于硬件，否则花钱购买更强大的机器又有什么意义呢？

最接近可重现结果的是报告相对速度，例如，提供示例程序并根据用户程序在 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 作为输入，第一个在眨眼间完成，第二个需要很长时间，我已经厌倦了等待。

score 2 · Accepted Answer

您可以使用SPOJ等几种在线工具进行比赛（这个是免费的并且支持 Java）。这样你就有了一台参考机器来测量程序的执行时间。

score 1 · Accepted Answer

对于（1）为什么不只是时间执行过程？设计拼图，使实际处理是迄今为止最重要的计时方面，而不是流程启动，并在几次迭代中对其计时以获得平均值。

对于 (2) 提供示例输入，但在现场比赛中使用替代输入。

score 1 · Accepted Answer

至于（2），编程竞赛（只计算正确性）中通常使用的解决方案是提供少量有限的示例输入，但在评审系统上使用更全面的测试集。

至于（3），使用的JVM指令的数量不一定是衡量速度的好方法。对于每条指令，某些实现可能需要更长或更短的时间；我什至还没有开始讨论抖动和其他优化。

score 1 · Accepted Answer

您可能必须使用实时 JVM，以便您可以公平地控制垃圾收集器。如果一个竞争者仅仅因为垃圾收集器在他们的运行过程中启动而显示更长的运行时间，那将是不公平的。

score 0 · Accepted Answer

您可以实现一个自动评分器类型的测试站点，人们可以在其中提交他们的代码并收到一封电子邮件，其中包含他们的性能结果，也许还有一个关于最高速度结果的指示。他们不会得到输入，但会得到官方 JVM 将产生的结果。为了防止滥用，修复类加载器以防止加载任何类型的传出连接类型的东西，并将性能测试器限制为每天每个地址提交一次，或其他策略。

score 0 · Accepted Answer

唯一明智的衡量标准是在某些真实硬件上的时间。编译器优化时间，而不是执行指令的计数，因此计数指令会破坏许多优化并使其中一些优化变得悲观。不仅指令需要不同的时间量，而且由于例如内存访问而导致的执行延迟也会有很大差异。

score 0 · Accepted Answer

您可以通过查看FastCode了解很多关于此类比赛所需的内容，尤其是在管理不同的硬件配置以及基准测试和验证程序方面。

score 0 · Accepted Answer

为什么不让 VJM 更进一步，实现一个完整的基于 Linux 的 VM？时钟周期应该是相同的（我猜这取决于 VM 的实现方式）。

例如，您可以创建一个基于 8088 的 VM，该 VM 具有 256K RAM 和 5 meg 磁盘空间运行 MINUX。不管代码执行“多快”，无论 8088 是在 Pentium Dual Core 还是一些旧的 Power PC 上实际实现的，CPU 周期数都不会保持不变（相对于 8088）。

一旦建立了虚拟硬件，语言选择就可以成为“最快算法”竞赛解决方案的一部分。

score 0 · Accepted Answer

我也认为计算指令的数量是一个很好的衡量标准。

我看到的唯一缺点是如果 JVM 指令太强大。我不知道 JVC，但可能有对字符串的本机支持。附加字符串可能只会导致一条指令。（不要这么想。）

我只是使用普通的旧time命令。这测量了执行时间，而不是实时，这确实消除了后台进程的几乎所有影响。

java - 运行最快的算法竞赛

10 回答 10

Related

Reference