9

コンピュータ サイエンスの専門家なら誰でも、O(n log n)理論的には HeapSort が最悪のケースで、QuickSort が最悪のケースであることを知っているでしょうO(n^2)。ただし、実際には、適切に実装された (優れたヒューリスティックを使用した) QuickSort は、すべてのデータ セットで HeapSort よりも優れたパフォーマンスを発揮します。一方で、最悪のケースはほとんど観察されず、他方では、CPU キャッシュ ライン、プリフェッチなどは、多くの単純なタスクに大きな違いをもたらします。また、たとえば、QuickSort は で事前に並べ替えられたデータを (適切なヒューリスティックを使用して) 処理できますがO(n)、HeapSort はO(n log n)既存の構造を利用しないため、常に でデータを再編成します。

私の玩具プロジェクトであるcaliper-analyzeでは、最近、ベンチマーク結果からアルゴリズムの実際の平均的な複雑さを推定する方法を検討しています。特に、Lawson と Hanson の NNLS フィッティングを異なる多項式で試しました。

ただし、まだうまく機能していません。使用可能な結果が得られる場合もあれば、そうでない場合もあります。より大きなベンチマークを実行すること、特により多くのパラメーターを試すことが役立つかもしれないと私は考えています。

次の結果は、ランダム性が 10% の SAW パターンで Double オブジェクトを並べ替えたものです。n は、この実行では最大 500 にすぎなかったため、実際の使用を代表するものではありません...数値は、サイズに対する実行時の推定依存性です。出力は手作業で編集され、手動で並べ替えられているため、ツールが現在提供しているものは反映されていません!

BubbleSortTextbook       LINEAR: 67.59  NLOG2N:  1.89  QUADRATIC: 2.51
BubbleSort               LINEAR: 54.84                 QUADRATIC: 1.68
BidirectionalBubbleSort  LINEAR: 52.20                 QUADRATIC: 1.36
InsertionSort            LINEAR: 17.13  NLOG2N:  2.97  QUADRATIC: 0.86
QuickSortTextbook                       NLOG2N: 18.15
QuickSortBo3             LINEAR: 59.74                 QUADRATIC: 0.12
Java                     LINEAR:  6.81  NLOG2N: 12.33
DualPivotQuickSortBo5                   NLOG2N: 11.28
QuickSortBo5             LINEAR:  3.35  NLOG2N:  9.67

この特定の設定では (多くの場合、まったく満足のいく結果が得られません)、結果は既知の動作とほぼ一致することがわかります。バブル ソートは非常にコストがかかり、QuickSort の優れたヒューリスティックの方がはるかに優れています。ただし、たとえば、3 つのヒューリスティックの中央値を使用するO(n + n^2)QuickSort は推定値になりますが、他の QuickSorts は次のように推定されます。O(n + n log n)

だから今、私の実際の質問に：

  • どの実装を予測するために、ベンチマーク データから実行時の複雑さの分析を実行するアルゴリズム/アプローチ/ツールを知っていますか?
  • これに関する科学記事を知っていますか (実装の平均的な複雑さの推定)?
  • ここでより正確な見積もりを得るのに役立つロバストなフィッティング方法を知っていますか? たとえば、NNLS の正規化されたバージョン。
  • 合理的な見積もりを得るために必要なサンプル数の経験則を知っていますか? (特に、どのような場合にツールが推定値を提示することを控えるべきか?)

もう一度強調しておきますが、私は理論上の複雑さや形式的な分析には興味がありません。私は、 （理論的には同一のアルゴリズムの）実装が実際の CPU のベンチマーク データでどのように機能するかを確認することに興味があります...一般的な範囲の数値要因は、漸近的な動作よりも重要です。(そして、いいえ、長い目で見れば、時間の複雑さと並べ替えだけではありません。しかし、私はインデックス構造やその他のパラメーターに興味があります。また、間違っていなければ、キャリパーはたとえばメモリ消費量も測定できます)さらに、私はJavaで作業しています。私はmatlabの世界に住んでいないので、Matlabビルトインを呼び出すだけのアプローチは役に立ちません。

時間があれば、より多くのデータ ポイントを取得できるように、これらのベンチマークのいくつかをより多くのサイズで再実行してみます。多分それはうまくいくでしょう...しかし、より小さなデータセットからでもより良い推定値を得るために使用できる、より堅牢な回帰方法があると思います. さらに、サンプルが小さすぎてまったく予測できない場合を検出したいと思います!

4

1 に答える 1

2

実際の複雑さが必要な場合は、それを測定することをお勧めします。測定せずにプログラムがどのように実行されるかを推測しようとすることは、非常に信頼できません。

同じプログラムでも、別のマシンではまったく異なる動作をすることがあります。たとえば、あるアルゴリズムは、あるマシンでは速くても、別のマシンでは遅くなる場合があります。

マシンが他に何をしているかに応じて、プログラムが遅くなる可能性があるため、見栄えは良いがキャッシュなどのリソースを大量に使用するアルゴは、それらのリソースを共有する必要がある場合に遅くなり、他のプログラムを遅くする可能性があります。

マシン上でアルゴを単独でテストすると、実際のプログラムで使用するよりも最大 2 倍から 5 倍速くなります。

合理的な見積もりを得るために必要なサンプル数の経験則を知っていますか? (特に、どのような場合にツールが推定値を提示することを控えるべきか?)

90% や 99% などのパーセンタイルを決定するには、1/(1-p)^2 が必要です。つまり、99% タイルの場合、ウォームアップ後に少なくとも 10,000 サンプルが必要です。99.9% タイルの場合、100 万が必要です。

于 2013-07-05T21:40:02.110 に答える