1

私は、シーケンシャルとバイナリの 2 つの異なる検索アルゴリズムにかかる時間を測定する必要がある割り当てを行っています (効率について指摘すると思います)。検索する約 280 語のターゲット リストと、約 1200 語の検索プール リストがあります。両方のファイルを読み取り、その単語を ArrayLists に保存しました。

これまでに実装した順次アルゴリズムに関連するビットは次のとおりです。

long startTime = System.nanoTime();

//search sorted list for as long as end of list has not been reached and 
//current list item lexicographically precedes target String    
while((compareResult > 0)&&(position != searchPool.size()-1)){

    //update to current position
    position += 1;

    compareResult = target.compareTo(searchPool.get((int)position));

    comparisonCount += 1;

}//end while loop


long endTime = System.nanoTime();

timeElapsed = endTime - startTime; //timeElapsed also a long

この後、比較の回数と経過時間を表示します (ミリ秒単位なので、最初に 100 万で割ります)。

最初のいくつかの数値で返される時間は、約 0.5 ～ 0.7 ミリ秒です。この数値は、0.1 ミリ秒かかる 32 番目のワードまで下方に揺れます。残りの 150 ワードはすべて 0.0 ms かかります。

比較回数と経過時間の間に直接的な相関関係があると予想していました。何がうまくいかないのですか？

余談ですが、compareTo メソッドによって行われた比較の数 (つまり、単語の長さ) が時間に影響を与えている可能性があることに気付きました。結論に達する) さらに下に表示される場合は、まったく時間がかかりません。

4

1 に答える 1

2

JVM は、頻繁に実行されるコード パスを最適化して高速化します。また、アプリケーションによっては、最初の数回の反復で、接続の確立、リソースのロードなどが含まれる場合があります。

したがって、一般的な戦略として、最初のいくつかのサンプルを破棄する必要があります。また、より信頼性の高い結果を得るには、より大きなサンプルの平均として測定してください。

于 2012-02-25T12:13:00.220 に答える