2

我正在为学校进行合并排序（排序字符串）的实证分析，我遇到了一个我无法解释或找不到解释的奇怪现象。当我运行我的代码时，我使用内置的 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 个字符长，无序（随机顺序）

我错过了什么吗？

4

1 回答 1

0

我错过了什么吗？

您正在尝试做一个microbenchmark，但到目前为止您发布的代码并不像一个运行良好的示例。为此，请遵循此处所述的规则：如何在 Java 中编写正确的微基准测试？.

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

一些建议：

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

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

于 2013-10-25T14:48:47.233 回答