java - 二进制搜索运行时的某些异常

Question

我有一个二分查找的修改版本，它接受一个排序的数组和一个值，并返回一个元素的最小可能索引，该元素等于或大于给定值(如果值为 -1，则为 -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

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

Answer 1

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

-XX:+PrintCompilation

你也可以运行你的程序

-Xint

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

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

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