java - 合并排序在更大的输入上运行得更快

Question

我正在为学校进行合并排序(字符串排序)的实证分析，我遇到了一个我无法解释或找不到解释的奇怪现象。当我运行我的代码时，我使用内置的 system.nanotime() 方法捕获运行时间，并且出于某种原因，在特定输入大小下，执行排序例程的时间实际上比 更少输入尺寸更小。

我的算法只是一个基本的归并排序，我的测试代码也很简单:

//Get current system time
long start = System.nanoTime();
//Perform mergesort procedure
a = q.sort(a);
//Calculate total elapsed sort time
long time = System.nanoTime()-start;

我对 900 个字符串进行排序时耗时得到的输出是:3928492ns 对于 1300 个字符串，它是:3541923ns

这两项都是大约 20 次试验的平均值，因此非常一致。在 1300 个字符串之后，执行时间继续按预期增长。我认为可能存在一些峰值输入大小，这种现象最明显。

那么我的问题是:什么可能导致程序速度突然增加？我在想可能会对包含大量数据的数组进行某种优化，尽管数组中的 1300 项并不大。

一些信息:

• 编译器:Java 版本 1.7.0_07
• 算法:基本递归合并排序(使用数组)
• 输入类型:长度为 6-10 个字符的字符串，打乱顺序(随机顺序)

我错过了什么吗？

Answer 1

Am I missing anything?

你正在尝试做一个 microbenchmark ，但您到目前为止发布的代码并不像一个运行良好的示例。为此，请遵循此处所述的规则:How do I write a correct micro-benchmark in Java? .

关于您的代码更快的解释是因为在您的方法进行一些迭代之后，JIT 将被触发并且您的代码的性能将得到优化，因此您的代码变得更快，即使在处理更大的数据时也是如此。

一些建议:

• 使用多个不同大小的数组/列表输入。进行此类分析的最佳值是 100、1000 (1k)、10000 (10k)、100000 (100k)、1000000 (1m) 以及介于这些值之间的随机大小值。当执行需要更长时间的评估时，您将获得更准确的结果。
• 使用不同对象的数组/列表。创建一个 POJO 并使其实现 Comparable接口(interface)，然后执行您的排序方法。如上所述，使用不同的数组值。

---

与你的问题没有直接关系，但执行结果是根据使用的JDK。 Eclipse 只是一个 IDE，可以与不同的 JDK 版本一起工作，例如在我的工作场所，我使用 JDK 6 u30 来处理公司项目，但对于个人项目(如概念验证)，我使用 JDK 7 u40。