Java中的時序混淆

對於我所從事的項目，我的任務是對兩種不同搜索算法的搜索時間進行計時：二進制搜索和順序搜索。對於每種算法，我都應該記錄排序輸入和未排序輸入的時間。當我比較排序後輸入與未排序輸入的順序搜索的搜索時間時，我發現有些奇怪。根據我首先排序哪一個，搜索時間將顯着大於第二個。因此，如果我在排序的第一個順序搜索，它將比未排序的順序搜索花費更長的時間。Java中的時序混淆

這對我來說沒有意義，並且是我混亂的根源。搜索到的密鑰保證可以在數據輸入中找到（通過順序搜索），因爲密鑰是從輸入中獲取的。

下面是產生問題的代碼。在這種情況下，seqOnUnsorted搜索時間將大大超過seqOnSorted，這不應該是。

public void sequentialSearchExperiment(){ 
    seqOnUnsorted = sequentialSearchSet(keys, unsortedArray); 
    writeOutExperimentResults(seqOnUnsorted, seqOnUnsortedFilename, "Sequential Sort on Unsorted: "); 

    seqOnSorted = sequentialSearchSet(keys, sortedArray); 
    writeOutExperimentResults(seqOnSorted, seqOnSortedFilename, "Sequential Sort on Sorted: "); 

}

的sequentialSearchSet（）的方法如下：

public SearchStats[] sequentialSearchSet(int[] keys, int[] toSearch){ 
    SearchStats[] stats = new SearchStats[keys.length]; 

    for (int i = 0; i < keys.length; i++){ 
     stats[i] = sequentialSearch(keys[i], toSearch); 
    } 

    return stats; 
}

這裏是sequentialSearch（）：

public SearchStats sequentialSearch(int key, int[] toSearch){ 

    long startTime = System.nanoTime(); // start timer 

    // step through array one-by-one until key found 
    for (int i = 0; i < toSearch.length; i++){ 
     if (toSearch[i] == key){ 
      return new SearchStats(key, i, System.nanoTime() - startTime); 
     } 
    } 

    // did not find key 
    return new SearchStats(key, -1, System.nanoTime() - startTime); 
}

和這裏是SearchStats構造：

public SearchStats(int keySearchedFor, int indexOfFound, long searchTime){ 
    this.keySearchedFor = keySearchedFor; 
    this.indexOfFound = indexOfFound; 
    this.searchTime = searchTime; 
}

如果我做一個測試RU n，我得到的平均搜索時間爲：

sequential search on sorted: 21,080 ns 
sequential search on unsorted: 2,137,465 ns

正如您所看到的，因爲我先搜索未排序的搜索，搜索時間明顯更長。任何人都可以解釋爲什麼這樣嗎？而且，我怎樣才能避免這種怪異？

來源

2011-11-07 jtan

嘗試反覆運行測試，直到您沒有看到任何性能改進。通常情況下，方法/循環需要在完全優化之前運行10000次。搜索'-XX：CompileThreshold ='選項以獲取更多詳細信息。 –

這是由於VM 「熱身」。作爲一個簡短的總結，現代虛擬機編譯通用代碼路徑到本地代碼並在運行時優化它們。因此，圍繞循環的前幾次迭代中，代碼正在被解釋，並且比優化後的代碼慢許多個數量級。

這是分析Java時的常見問題，一般的解決方案是練習測試代碼在執行前幾（百萬）次或者測得的測試。

欲瞭解更多詳情和建議，請閱讀Anatomy of a flawed micro-benchmark。

來源

2011-11-07 17:39:58

+1。此外，最好不要在熱身後的單圈循環中運行，而要進行多次運行並取平均值。這應該可以減少超出你的控制範圍的東西的可能影響，就像操作系統中的其他進程優先考慮和佔用CPU時間一樣。總的來說，最好用profiler來檢查這種事情，所以你只能得到實際分配給JVM的時間的方法時間。 –

謝謝！這解釋了一切。 – jtan

微基準測試是很難：http://www.ibm.com/developerworks/java/library/j-jtp02225/index.html

來源

2011-11-07 17:39:06 ptyx

Java中的時序混淆

回答

相關問題