Java 中的时序混乱

发布于 2024-12-14 12:17:50 字数 1973 浏览 3 评论 0原文

在我从事的一个项目中，我的任务是计时两种不同搜索算法的搜索时间：二分搜索和顺序搜索。对于每个算法，我应该记录排序输入和未排序输入的时间。当我比较排序输入与未排序输入的顺序搜索的搜索时间时，我发现了一些奇怪的事情。根据我首先排序的那个，搜索时间将明显大于第二个。因此，如果我首先对已排序的内容进行顺序搜索，那么它将比对未排序的顺序搜索花费更长的时间。

这对我来说没有意义，也是我困惑的根源。保证在数据输入中找到所搜索的键（通过顺序搜索），因为键是从输入中获取的。

这是产生问题的代码。在这种情况下，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: ");

}

equentialSearchSet()方法如下：

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

正如你所看到的，因为我首先搜索未排序的，搜索时间明显更长。谁能解释为什么会这样？而且，我怎样才能避免这种奇怪的现象呢？

原文

For a project I worked on, I was tasked with timing the search times for two different search algorithms: binary search and sequential search. For each algorithm, I was supposed to record the time for both sorted input and unsorted input. I came across something weird when I compared the search times for sequential search on the sorted input vs. the unsorted input. Depending on which one I sort first, that search time will be significantly greater than than the second. So if I sequential search on the sorted first, it will take much longer than the sequential search on the unsorted.

This doesn't make sense to me and is the source of my confusion. The keys searched for are guaranteed to be found in the data input (by the sequential search), since the keys are taken from the input.

Here is the code that creates the problem. In this case, the seqOnUnsorted search times would be much greater than seqOnSorted, which it shouldn't be.

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: ");

}

The sequentialSearchSet() method is as follows:

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;
}

Here is 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);
}

and here is the SearchStats constructor:

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

If I do a test run, the average search times I get:

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

As you can see, because I search on the unsorted first, the search time was significantly longer. Can anyone explain why this is so? And furthermore, how I could avoid such weirdness?

分享到QQ

分享到微博