3

私が取り組んだプロジェクトでは、2つの異なる検索アルゴリズム（バイナリ検索とシーケンシャル検索）の検索時間のタイミングを調整する必要がありました。アルゴリズムごとに、ソートされた入力とソートされていない入力の両方の時間を記録することになっています。ソートされた入力とソートされていない入力の順次検索の検索時間を比較すると、奇妙なことに遭遇しました。どちらを最初に並べ替えるかによって、その検索時間は2番目よりも大幅に長くなります。したがって、最初にソートされたものを順次検索すると、ソートされていないものを順次検索するよりもはるかに時間がかかります。

これは私には意味がなく、私の混乱の原因です。キーは入力から取得されるため、検索されたキーは、データ入力で（順次検索によって）検出されることが保証されます。

問題を引き起こすコードは次のとおりです。この場合、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: ");

}

シーケンシャルサーチセット（）メソッドは次のとおりです。

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

ご覧のとおり、最初にソートされていないものを検索するため、検索時間が大幅に長くなりました。なぜそうなのか誰かが説明できますか？そしてさらに、どうすればそのような奇妙さを避けることができますか？

4

2 に答える 2

9

これは、VM の「ウォームアップ」が原因です。簡単にまとめると、最新の VM は、一般的なコード パスをネイティブ コードにコンパイルし、実行中に最適化します。したがって、ループの最初の数回の反復では、コードが解釈され、最適化が開始されると、コードよりも桁違いに遅くなります。

これは、Java をプロファイリングする際の一般的な問題であり、一般的な解決策は、測定されたテストを実行する前に、テスト対象のコードを数回 (100 万回) 実行することです。

詳細と提案については、欠陥のあるマイクロベンチマークの解剖学をお読みください。

于 2011-11-07T17:39:58.197 に答える
1

マイクロベンチマークは難しい: http://www.ibm.com/developerworks/java/library/j-jtp02225/index.html

于 2011-11-07T17:39:06.807 に答える