2

入力配列のサイズを変更しながら、タイマーを使用して実行時間を測定するアルゴリズムの複雑さを測定しようとしています。

現時点で私が持っているコードはかなり単純です:

public void start() {
    start = System.nanoTime();
}

public long stop() {
    long time = System.nanoTime() - start;
    start = 0;
    return time;
}

配列のサイズが非常に大きくなるまでは問題なく動作するように見え、O(n) の複雑さのアルゴリズムであると予想されるものは、O(n^2) のように見えます。これは、CPU のスレッド化が原因であると考えられます。n の値が大きいと、実行中に他のプロセスがより多くの時間を割り込んでいます。

基本的に、アルゴリズムを呼び出してからの経過時間ではなく、プロセスが実行されている時間を測定したいと考えています。Javaでこれを行う簡単な方法はありますか?

4

3 に答える 3

3

実行時間の測定は非常に興味深いものですが、複雑なトピックでもあります。Java で正しく行うには、JVM の仕組みについて少し知っておく必要があります。これは、ベンチマークと測定に関する developerWorks の優れた記事です。それを読んで、それはあなたに大いに役立ちます。

著者は、ベンチマークを実行するための小さなフレームワークも提供しています。このフレームワークを使用できます。前後の 2 つのタイムスタンプだけではなく、CPU の消費時間など、必要なものが正確に得られます。フレームワークは、JVM のウォームアップも処理し、ジャストインタイム コンパイルを追跡します。

このようなEclipse 用のパフォーマンス モニターを使用することもできます。このようなパフォーマンス モニターの問題点は、ベンチマークを実行しないことです。アプリケーションが現在使用している時間、メモリなどを追跡するだけです。しかし、これは実際の測定値ではありません。特定の時点での単なるスナップショットです。

于 2012-05-05T16:42:13.343 に答える
1

ウォールクロック時間ではなく、現在のスレッド (または実際には任意のスレッド) の実際の CPU 時間が必要な場合は、ThreadMXBean を介してこれを取得できます。基本的に、最初にこれを行います：

ThreadMXBean thx = ManagementFactory.getThreadMXBean();
thx.setThreadCpuTimeEnabled(true);

次に、現在のスレッドの経過した CPU 時間を取得したいときはいつでも:

long cpuTime = thx.getCurrentThreadCpuTime();

ThreadMXBean には、任意のスレッドの CPU 時間やその他の情報を取得するための呼び出しもあることがわかります。

タイミングの複雑さに関するその他のコメントも当てはまります。コード片の個々の呼び出しのタイミングは、特に CPU の状態と、JIT コンパイラーがその特定の瞬間に実行することを決定した内容に依存する可能性があります。アルゴリズムの全体的なスケーラビリティ動作は、通常、多くの呼び出しにわたって現れる傾向であり、タイミングの「外れ値」に常に備える必要があります。

また、特定のタイミングがナノ秒 (実際にはミリ秒) で表現されているからといって、そのタイミングが実際にその粒度を持っているわけではないことに注意してください。

于 2012-05-05T16:54:23.993 に答える
1

Java でのベンチマークは難しい問題です。特に、メソッドがますます高度に最適化されるにつれて、JIT が奇妙な影響を与える可能性があるためです。Caliperなどの専用ツールの使用を検討してください。それを使用して、さまざまな入力サイズでパフォーマンスを測定する方法の例は、こちらにあります。

于 2012-05-05T16:40:28.377 に答える