アルゴリズムの実行時間をモデル化するには？

Question

どのアルゴリズム実行時間のモデルが存在しますか？

私たちはすべて、mergesortがbublesortより高速であることを期待しています。また、mergesortはbubblesortのO（n log n）とO（n ）の比較を行います。他のアルゴリズムについては

、あなたは実行時間をモデル化するために、他のどのような方法などポインタ参照、配列の検索、固定サイズの整数に対する算術演算、などの他の操作（比較とスワップ以外）、

がある数えます？

自分自身が知っているのは、ディスクから読み取られ、ディスクに書き込まれたブロックの数を数えることです。私の答えはWhen does Big-O notation fail?です。長い記述があります。

もう1つは、キャッシュミスの数をカウントしています。これは、メモリ階層のすべてのレベルを見ることによってI/Oモデルを拡張します。

分散アルゴリズム（セキュアなマルチパーティ計算など）の場合は、ネットワークを介して送信されるデータの量を計測することが一般的です（通信ラウンドまたはメッセージ数で一般的に測定されます）。

アルゴリズムのパフォーマンスを予測するために、他に興味深いものがいくつありますか（数えられません）？

また、これらのモデルはどれくらい良いですか？私が聞いた限りでは、キャッシュにないアルゴリズムはディスク上のデータのI/O効率的なアルゴリズムと競合しますが、メモリ内のアルゴリズムでは競合しません。

特に：これらのモデルで特定のインスタンスが相対的なパフォーマンスを誤予測していますか？私自身の実験によると、フィボナッチヒープは、データがメモリに収まるのに十分小さい場合、Dijstraの最短パス（バイナリヒープと比較して）を高速化しません。

Answer 1

計算モデルを定義し、各操作のコストを見積もり、そのコストの観点からアルゴリズムを分析する必要があります。もちろん、コストは特定の環境と、アルゴリズムを導入したいマシンの特性によって決まるため、問題は本当にあまりにも一般的です。

アルゴリズムコースでは、各操作のコストが1であると仮定しているため、ループ回数をカウントするだけです。メインメモリで動作するアルゴリズムでは、I/Oからの読み出し/書き込みを除いた各操作は0（読み書き1）などと仮定しています。

これらのモデルは現実と密接な関係にありますか？それはあなたの環境とマシンの現実に依存します。

キャッシュミスによる計算は、コアデュオでは正しくなる可能性がありますが、セルプロセッサでは間違っている可能性があります。たとえば、SPEのメモリの内容を手動で転送する必要があります。

Answer 2

O（n ...）表記を使用して実行時間/空間をモデル化するための基礎が何であれ、正規化された環境を想定しています。どのモデルを指定しても、それを決定するために測定する変数の数に関係なく、正規化された環境にのみ適用されます。だから、ディスクI/Oが競争の激しさに乏しいとき、O（n ...）はそれらの間接費を考慮する必要はないかもしれません。

したがって、O（n）は入力nの正規化された環境での典型的なパフォーマンスをモデル化します。

拡張子は、ディスクの読み込み順がO（n）であること、またはメモリ割り当てがO（n）などであると言うことができます。プレッシャーを加える外部イベント（スケジューリングなど）は、典型的な時間/空間/何かの発生のモデルでは機能しません。

おそらく私はあなたの意見が不足している可能性があります。

Answer 3

私が取り組んでいるリアルタイムプラットフォームでは、最近、大量のデータ（例：MB範囲ではなく、MB範囲）をコピーすることは、実際に私が訓練したよりも早いことがわかります。おそらく、これは今日使用されている大容量のキャッシュや、おそらくは高速のプロセッサ速度と関係があります。しかし、実際には、データコピーを避けるためにコードをあまりにもひどくひどく変えるのは面倒ではありません。

代わりに、私が本当に気を付けなければならないのは、デバイスアクセスとコンテキストスイッチです。それらの数が少ないほど良い。

「ゼロバッファ」デバイスドライバが速度と同期していた日数は終わっています。