6

コードスニピットを取得して、実行に必要な「ティック」の数を正確に確認できるJavaには何かありますか。私が書いたアルゴリズムが他のものよりも速いことを証明したい.

4

10 に答える 10

6

「ダニ」？いいえ。それぞれ数回実行して、平均結果を比較することをお勧めします。

public class AlgorithmDriver {
    public static void main(String [] args) {
        int numTries = 1000000;
        long begTime = System.currentTimeMillis();
        for (int i = 0; i < numTries; ++i) {
            Algorithm.someMethodCall();
        }
        long endTime = System.currentTimeMillis();
        System.out.printf("Total time for %10d tries: %d ms\n", numTries, (endTime-begTime));
    }
}
于 2011-08-02T23:26:27.413 に答える
4

おそらく、次の 2 つの異なる質問をしているでしょう。

  1. Java 実装の実行時間をどのように測定できますか (ベンチマーク)
  2. アルゴリズムの漸近的な実行時間をどのように証明できますか

これらの最初の場合、ここに投稿されたソリューションは使用しません。それらはほとんど正しくありません。Forst .System.nanoTimeよりも使いやすいでしょうSystem.currentTimeMillis。次に、try catch ブロックを使用する必要があります。3 番目に、メトリックの外で何度も実行されているコードの実行時間の統計を取得して、より完全な全体像を把握できるようにします。漠然と次のように見えるコードを何度も実行します。

long totalTime = 0;
long startTime = System.nanoTime();
try{
   //method to test
} finally {
   totalTime = System.nanoTime() - startTime;
}

ベンチマークを正しく行うことは困難です。たとえば、コードをテストする前に、コードを数分間「ウォームアップ」する必要があります。ベンチマークは早い段階で頻繁に行いますが、ベンチマークを過度に信じてはいけません。特に小さなマイクロ ベンチマークは、ほとんどの場合何らかの形で存在します。

質問を解釈する2番目の方法は、漸近的な実行時間に関するものです。実のところ、これは Java とはほとんど関係がなく、一般的なコンピューター サイエンスです。ここで質問したいのは、入力サイズに関してアルゴリズムの実行時の動作を表す曲線はどれかということです。

まずはBig-Oh記法を理解することです。私は最善を尽くしますが、SOは数学表記をサポートしていません。 は、アルゴリズムの実行時間の上限の一定係数内に無限大に向かうO(f(n))ようなアルゴリズムのセットを示します。形式的には、いくつかの定数とすべての. ビッグ オメガは上限を除いて同じものであり、ビッグ シータはビッグ オーとビッグ オメガの両方を意味します。これは難しいことではありません。nf(n)T(n)O(f(n))n0cn > n0 c*f(n) >= nf(n)f(n)f(n)

「平均的なケース」、最良のケース、最悪のケースなど、さまざまな種類の実行時間について話すことができるため、もう少し複雑になります。たとえば、通常のクイックソートはO(n^2)最悪の場合ですがO(n log n)、ランダム リストの場合です。

だから私は何T(n)を意味するかをスキップしました。基本的には「ティック」の数です。一部のマシン命令 (メモリからの読み取りなど) は、他の命令 (追加など) よりもはるかに時間がかかります。しかし、それらが互いに離れている一定の係数である限り、 の値を変更するだけなので、ビッグ オーの目的のためにそれらをすべて同じものとして扱うことができますc。

漸近境界を証明することはそれほど難しくありません。単純な構造化プログラミングの問題については、数えるだけです

public int square(int n){
   int sum = 0
   for(int i = 0, i < n, i++){
     sum += n
   }
   return sum
}

この例では、sum の初期化、i の初期化、および値を返すための命令がそれぞれ 1 つずつあります。ループnは、比較、加算、インクリメントを行うたびに何度も発生します。したがって、of 2 とof 4 をO(square(n)) = O(3 + 3n)使用すると、これが であることを簡単に証明できます。余分な定数項を削除し、定数の倍数で除算することにより、大きな Oh 式をいつでも安全に単純化できます。n0cO(n)

再帰関数に直面した場合、再帰関係を解決する必要があります。T(n) = 2*T(n/2) + O(1)閉じた形式のソリューションを見つけたいような関数がある場合。手動で、またはコンピューター代数システムを使用して、これを行う必要がある場合があります。この例では、前方置換を使用して、これが正しい値であることを証明するために、 (表記法を乱用して)T(1) = O(1), T(2) = O(3), T(4) = O(7), T(8) = (15)によく似たパターンを確認できます。O(2n - 1)

 T(n) = 2*T(n/2) + 1
 T(n) = 2*(2(n/2) - 1) + 1
 T(n) = 2*(n-1) + 1
 T(n) = 2n - 2 + 1
 T(n) = 2n - 1

前に見たように、次のように単純化できますO(2n -1)。O(n)

多くの場合、この種の問題で時間を節約するための数学的ツールであるマスター定理を使用できます。ウィキペディアをチェックすると、マスター定理が見つかります。上記の例をプラグアンドプレイすると、同じ答えが得られます。

詳細については、Levitin の「The Design & Analysis of Algorithms」などのアルゴリズムの教科書を参照してください。

于 2011-08-03T00:21:57.950 に答える
2

System.currentTimeMillis()開始時刻と終了時刻を取得するために使用できます。

long start = System.currentTimeMillis();

// your code

long end = System.currentTimeMillis();
System.out.println( "time: " + (end - start) );
于 2011-08-02T23:22:44.030 に答える
1

このアルゴリズムの効率性の証明は、主に今年のデータ構造のレッスンで行う必要がありました。

まず、先に述べたように時間を測定しました。次に、毎回2乗してメソッドの入力数を増やしました（10,100,1000、...）最後に、時間測定値をExcelファイルに入れ、これらの時間値のグラフィックを描画しました。

このようにして、あるアルゴリズムが他のアルゴリズムよりも少し速いかどうかを確認できます。

于 2011-08-02T23:36:46.610 に答える
1

他の人が示唆しているように、現在の時刻をミリ秒で使用しません。ThreadMXBeans が提供するメソッドはより正確です (100% 正確とは言えません)。

実際には、経過したシステム時間ではなく、スレッドが使用した CPU 時間を測定します。これは、基盤となる OS によって実行されるコンテキスト スイッチによって歪められる可能性があります。

Java パフォーマンス テスト

于 2012-09-24T18:45:42.390 に答える
1

System.currentTimeMillis() または System.nanoTime() (それぞれ特性が異なります) を使用して経過時間を測定できます。最後に違いを印刷するだけなので、これは比較的簡単です。

特定の操作をカウントする必要がある場合 (これはアルゴリズムでは一般的です)、最も簡単な方法は、操作が完了したときにカウンターをインクリメントし、完了したらそれを出力することです。 longはこれに適しています。複数の操作には、複数のカウンターを使用します。

于 2011-08-02T23:28:30.300 に答える
0

両方のアルゴリズムが同じマクロ レベルの「ティック」の定義 (たとえば、ツリー内の 1 つのノードをたどる) を持ち、アルゴリズムが他のマクロ レベルのティックよりも少ない数のマクロ レベルのティックで目標を達成することを証明することが目標である場合、その場合、最良の方法は、各実装を計測してそれらのティックをカウントすることです。このアプローチは理想的です。なぜなら、コードの実行を高速化できる低レベルの実装トリックには報われないが、アルゴリズムに関連していないからです。

その余裕はないが、System.currentTimeMillis などを含むここにリストされているアプローチとは対照的に、最小量の CPU リソースを使用して問題を解決するアプローチを計算しようとしている場合は、外部アプローチを使用します: Linux 時間コマンドが理想的です。各プログラムを同じ（大規模な）入力セットで実行し、できれば処理に数分または数時間かかり、time java algo1vsを実行するだけtime java algo2です。

于 2011-08-03T00:02:16.437 に答える
0

私はJavaフレームワークにあまり慣れていませんが、次のようにします：

  1. 両方のアルゴリズムに使用できる一連のテスト ケース (ほとんどがサンプル データ) を定義する
  2. 特定の機能にかかる時間を測定するタイミング メソッドを実装する
  3. for ループを作成し、メソッド A を実行します (たとえば、テスト データ全体で 1000 回繰り返します)。タイミング関数は何度も呼び出されると結果にバイアスがかかる可能性があるため、単一の関数の合計ではなく、ループのタイミングを測定します)
  4. 方法Bについても同じことを行います
  5. 結果を比較して勝者を選ぶ
于 2011-08-02T23:25:03.547 に答える