1

我有一个二进制搜索的修改版本，它以排序顺序和一个值接收数组，并返回等于或大于给定值的元素的最小可能索引（如果值大于最大限度）

运行上述算法后，一切正常，并且该方法按预期工作。但是，我在不同的输入大小上运行它来测量运行时间。

   for(int i=1;i<=20;i++){  
  int size=10*(i*i*i*i);
 int[] array=createRandomSortedArray(size);
 long startTime=System.nanoTime();
 int index=findSmallestIndex(array, needle);
 long et=System.nanoTime()-startTime;
 System.out.println("To find "+needle+" in "+size+" inputs "+" execution time is "+et+" nanoseconds");
}

以下是观察结果：-

To find 50 in 10 inputs  execution time is 5775 nanoseconds
To find 50 in 160 inputs  execution time is 1925 nanoseconds  
To find 50 in 810 inputs  execution time is 4330 nanoseconds
To find 50 in 2560 inputs  execution time is 5293 nanoseconds
To find 50 in 6250 inputs  execution time is 3849 nanoseconds
To find 50 in 12960 inputs  execution time is 3368 nanoseconds
To find 50 in 24010 inputs  execution time is 3849 nanoseconds
To find 50 in 40960 inputs  execution time is 11548 nanoseconds
To find 50 in 65610 inputs  execution time is 9143 nanoseconds
To find 50 in 100000 inputs  execution time is 4812 nanoseconds
To find 50 in 146410 inputs  execution time is 4812 nanoseconds
To find 50 in 207360 inputs  execution time is 11549 nanoseconds  
To find 50 in 285610 inputs  execution time is 8661 nanoseconds
To find 50 in 384160 inputs  execution time is 8661 nanoseconds
To find 50 in 506250 inputs  execution time is 11549 nanoseconds 
To find 50 in 655360 inputs  execution time is 11067 nanoseconds 
To find 50 in 835210 inputs  execution time is 11549 nanoseconds
To find 50 in 1049760 inputs  execution time is 11549 nanoseconds 
To find 50 in 1303210 inputs  execution time is 11067 nanoseconds
To find 50 in 1600000 inputs  execution time is 12030 nanoseconds

我看到 10 个输入的执行时间明显高于其连续的 160 个输入大小。为了验证事情，我在循环外单独运行了 10 个输入的执行，结果如下

To find 50 in 10 inputs  execution time is 962 nanoseconds

为什么呢？为什么会存在这种异常？还有其他几个步骤，运行时间比之前的较低输入大小慢。

4

3 回答 3

2

在运行微基准测试之前，您是否让虚拟机“预热”？在实际记录任何结果之前尝试运行此代码数千次，看看是否有区别。您可以添加以下命令行参数以查看 JIT 编译的内容：

-XX:+PrintCompilation

你也可以运行你的程序

-Xint

关闭所有热点优化并尝试获取苹果进行苹果比较。

如果这不是问题 - 我怀疑简单地调用您的方法会产生一些恒定的成本。尝试线性增加输入大小，看看是否可以通过这种方式绘制任何相关性。很难说你什么时候从 10 跳到 160。

最后，您可能希望包含一个标志，启用后将记录代码正在执行的行为（例如比较次数等），以查看您是否做了任何不必要的工作。

于 2012-04-10T04:49:48.050 回答
1

可能是热点在发挥它的魔力。颠倒运行顺序（先大）以验证这一点。

于 2012-04-10T04:47:18.173 回答
0

为了分析这一点，我将输出算法正在搜索的实际数组。由于看起来每次运行的数组并不相同，因此很难比较，因为访问的索引数量完全取决于数组的内容和搜索项。

于 2012-04-10T04:49:32.193 回答