JDK クラス メソッドの複雑さを測定する (または既存の測定値を取得する) 確立された方法はありますか? javap時間の複雑さとその程度を表します。Arrays.sort()特に、コレクションの操作方法の複雑さに興味があります。
たとえば、2 つの実装のパフォーマンスを比較しようとしています。1 つは使用しており、もう 1 つは使用Arrays.sort()していません。そのjavap逆アセンブルは、より多くのステップ (2 倍) を返しませんが、逆アセンブリがArrays.sort()ステップを除外するかどうかはわかりません。IOW、javapあるメソッドには、そのメソッド内またはそのメソッドのために呼び出されたメソッドの再帰的測定が含まれていますか?
また、Javaコード自体を変更して再コンパイルせずに、特定の基本Javaメソッドが特定のパラメータで呼び出されたときに実行されたループ反復の回数を見つける方法はありますか? たとえば、Arrays.sort('A', 'r', 'T', 'f')?の反復回数を測定します。
javap実際の速度を少しでも表すこと は期待できません。
Javadoc はアルゴリズムの複雑さを指定していますが、一定の要素に関心がある場合、実際のベンチマークを使用しない限り、一定の要素を現実的に比較する方法はまったくありません。
プリミティブ配列で が呼び出されたときに何が行われたかについての情報を取得することはできませんが、呼び出し回数をカウントArrays.sortするカスタムを渡すことで、オブジェクト配列を並べ替えるときに行われた比較の回数をカウントできます。Comparator(つまり、オブジェクト配列は別のソート アルゴリズム、特に安定したアルゴリズムでソートされ、プリミティブ配列はクイックソート バリアントでソートされます。)
からの出力を使用して、命令javapを見つけたいループが発生する場所を特定できます。gotoこの投稿では、その識別の包括的な説明を提供します。
投稿から:
ループの開始/終了のインストルメンテーションを検討する前に、開始、終了、後続の定義を調べる必要があります。ループには 1 つのエントリ ポイントしかありませんが、通常は break ステートメント (場合によってはラベル付き)、return ステートメント、および/または例外 (明示的にキャッチされるかどうかにかかわらず) が原因で、複数の出口ポイントや複数のサクセサがある場合があります。調査しているインストルメンテーションの種類に関する詳細は提供されていませんが、コードを挿入する場所を検討する価値は確かにあります (それが必要な場合)。通常、各 exit ステートメントの前、または各後続ステートメントの代わりに、いくつかのインストルメンテーションを実行する必要があります (この場合、元のステートメントを移動する必要があります)。
Arrays.sort()プリミティブの場合、調整されたクイックソートを使用します。マージソートを使用します（ただしObject、これは実装に依存します）。
From:配列
たとえば、sort(Object[]) で使用されるアルゴリズムはマージソートである必要はありませんが、安定している必要があります。