3

次の数の入力に対して次の時間で実行されるCプログラムがあります。

23           0.001s            
100          0.001s

これの公式を見つけようとしましたが、うまくいきませんでした。私が見る限り、時間が 2 倍になる場合とそうでない場合があるため、この式を見つけることができませんでした。

何かご意見は？

ノート

1) これを CPU 時間 (user+sys) で測定しています。

2) 私のプログラムはクイックソートを使用しています

2) 私のプログラムの漸近的なランタイム分析/複雑さは O(NlogN) です

4

2 に答える 2

2

これをプロットすると、「キャッシュの崖」にぶつかっているように見えます-データが十分に大きいため、すべてがCPUキャッシュレベルに収まるわけではなく、安価なレベルと高価なレベルの間でデータを交換する必要があります

低レベルでの違いは、精度による可能性が高いです - タイマーブロック内のループを増やすと、滑らかになるかもしれません

通常、キャッシュの崖にぶつかったときのパフォーマンスは、O*Q をプロットするようなものです

ここで、O は平均実行時間です -- あなたの場合は Nlog(N)

Q は、各キャッシュに割り当てられたサイズを渡すと増加するステップ関数です。Q=L1 サイズ以下は 1、L1 サイズ以上は 10、L2 サイズ以上は 100 など (数字は例のみ)

実際、O(1) 関数をプロットし、パフォーマンスの崖で使用されるメモリを探して、キャッシュ サイズを検証する人がいます。

           ___
 _____-----
  L1 | L2 | L3
于 2013-11-14T20:39:08.930 に答える