二進制搜索運行時的某些異常

Question

我有一個二進制搜索的修改版本，它以排序順序和值的形式接收數組，並返回等於或大於給定值的最小可能索引（或-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"); 
} 

和下面分別的observtions： -

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 ininputs 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

在運行microbenchmark之前，您是否讓虛擬機「熱身」？在實際記錄任何結果之前，嘗試運行此代碼幾千次，看看是否有所作爲。您可以添加以下命令行參數，看看有什麼得到由JIT編譯：

-XX:+PrintCompilation 

您還可以

-Xint 

運行您的程序關閉所有熱點的優化，並嘗試得到一個蘋果爲蘋果比較。

如果這不是問題 - 我懷疑簡單地調用你的方法有一些不變的代價。嘗試線性增加輸入大小並查看是否可以通過這種方式繪製任何關聯。很難說當你從10跳到160.

最後，你可能想包括一個標誌，當啓用時將記錄代碼執行的行爲（例如＃比較等），看看你是否做任何不必要的工作

Answer 2

可能是熱點做它的魔法。反轉運行的順序（先大）來驗證。

Answer 3

爲了分析這個，我會輸出算法正在搜索的實際數組。由於它看起來每次運行的數組都不相同，所以難以比較，因爲訪問的標記數完全取決於數組和搜索項的內容。