时间混乱在Java中

Question

对于我参与的项目,我的任务是为两种不同的搜索算法计算搜索时间:二进制搜索和顺序搜索.对于每个算法,我应该记录排序输入和未排序输入的时间.当我比较排序输入与未排序输入的顺序搜索的搜索时间时,我遇到了一些奇怪的事情.根据我先排序的那个,搜索时间将远远大于第二个.因此,如果我在排序的第一个上进行顺序搜索,则会比未排序的顺序搜索花费更长的时间.

这对我来说没有意义,也是我困惑的根源.保证在数据输入中找到所搜索的密钥(通过顺序搜索),因为密钥是从输入中获取的.

这是创建问题的代码.在这种情况下,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;
}

如果我进行测试运行,我得到的平均搜索时间:

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

正如您所看到的,因为我首先搜索未排序的搜索时间,所以搜索时间明显更长.任何人都可以解释为什么会这样吗？而且,我怎么能避免这种怪异？

Answer 1

这是因为虚拟机"正在升温".简要总结一下,现代虚拟机编译本机代码的公共代码路径,并在它们运行时对其进行优化.因此围绕循环的前几次迭代,代码被解释并且比优化开始时的代码慢很多个数量级.

这在分析Java时是一个常见问题,一般的解决方案是在执行测量测试之前将测试代码运行几(百万)次.

有关更多详细信息和建议,请阅读有缺陷的微基准测试的剖析.