1

並べ替えられた順序と値で配列を受け取り、指定された値以上の要素の可能な限り最小のインデックスを返すバイナリ検索の修正バージョンがあります（値が最大）

上記のアルゴリズムを実行すると、すべてが正常に機能し、メソッドは期待どおりに機能します。ただし、ランタイムを測定するために、さまざまな入力サイズで実行しました。

   for(int i=1;i<=20;i++){  
  int size=10*(i*i*i*i);
 int[] array=createRandomSortedArray(size);
 long startTime=System.nanoTime();
 int index=findSmallestIndex(array, needle);
 long et=System.nanoTime()-startTime;
 System.out.println("To find "+needle+" in "+size+" inputs "+" execution time is "+et+" nanoseconds");
}

そして、以下は観察でした：-

To find 50 in 10 inputs  execution time is 5775 nanoseconds
To find 50 in 160 inputs  execution time is 1925 nanoseconds  
To find 50 in 810 inputs  execution time is 4330 nanoseconds
To find 50 in 2560 inputs  execution time is 5293 nanoseconds
To find 50 in 6250 inputs  execution time is 3849 nanoseconds
To find 50 in 12960 inputs  execution time is 3368 nanoseconds
To find 50 in 24010 inputs  execution time is 3849 nanoseconds
To find 50 in 40960 inputs  execution time is 11548 nanoseconds
To find 50 in 65610 inputs  execution time is 9143 nanoseconds
To find 50 in 100000 inputs  execution time is 4812 nanoseconds
To find 50 in 146410 inputs  execution time is 4812 nanoseconds
To find 50 in 207360 inputs  execution time is 11549 nanoseconds  
To find 50 in 285610 inputs  execution time is 8661 nanoseconds
To find 50 in 384160 inputs  execution time is 8661 nanoseconds
To find 50 in 506250 inputs  execution time is 11549 nanoseconds 
To find 50 in 655360 inputs  execution time is 11067 nanoseconds 
To find 50 in 835210 inputs  execution time is 11549 nanoseconds
To find 50 in 1049760 inputs  execution time is 11549 nanoseconds 
To find 50 in 1303210 inputs  execution time is 11067 nanoseconds
To find 50 in 1600000 inputs  execution time is 12030 nanoseconds

10入力の実行時間は、連続する160入力サイズよりも大幅に長いことがわかります。確認するために、ループの外側で10個の入力を単独で実行したところ、次の結果が得られました。

To find 50 in 10 inputs  execution time is 962 nanoseconds

どうしてこんなことに？なぜこの異常が存在するのですか？実行時間が前の小さい入力サイズよりも遅い他のステップもいくつかあります。

4

3 に答える 3

2

マイクロベンチマークを実行する前に VM を「ウォームアップ」しましたか? 実際に結果を記録する前に、このコードを数千回実行してみて、違いが生じるかどうかを確認してください。次のコマンド ライン引数を追加して、JIT によってコンパイルされる内容を確認できます。

-XX:+PrintCompilation

プログラムを実行することもできます

-Xint

Hotspot の最適化をすべてオフにして、りんごの比較のためにりんごを取得しようとします。

これが問題ではない場合 - メソッドを単に呼び出すには一定のコストがかかると思います。入力サイズを直線的に増やしてみて、その方法で相関関係を描画できるかどうかを確認してください。10 から 160 にいつジャンプするかを判断するのは困難です。

最後に、有効にすると、不要な作業を行っているかどうかを確認するためにコードが実行している動作 (例: 比較の数など) をログに記録するフラグを含めることができます。

于 2012-04-10T04:49:48.050 に答える
1

Hotspot が魔法をかけているのかもしれません。それを確認するために、実行の順序を逆にします (最初に大きい)。

于 2012-04-10T04:47:18.173 に答える
0

これを分析するために、アルゴリズムが検索している実際の配列を出力します。各実行の配列は同じではないように見えるため、訪問したインデックスの数は配列の内容と検索項目に完全に依存しているため、比較するのは困難です。

于 2012-04-10T04:49:32.193 に答える