algorithm - アルゴリズムの実行時間をモデル化する方法は?

Question

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

私たちは皆、mergesort が bublesort よりも高速であることを期待しており、mergesort は O(n log n) の比較を行うのに対して、bublesort の場合は O(n ² ) を行うことに注意してください。

他のアルゴリズムでは、ポインター逆参照、配列ルックアップ、固定サイズの整数の算術演算など、(比較とスワップ以外の) 他の操作をカウントします。

実行時間をモデル化する他の方法はありますか?

私自身が知っているのは、ディスクから読み取られ、ディスクに書き込まれたブロックの数を数えることです。Big-O表記が失敗するのはいつですか?に対する私の回答を参照してください。長い説明のために。

もう 1 つは、キャッシュ ミスの数を数えることです。これは、メモリ階層のすべてのレベルを調べることで、I/O モデルを拡張します。

分散アルゴリズム (安全なマルチパーティ計算など) の 3 つ目は、ネットワークを介して送信されたデータの量をカウントすることです (通常、通信のラウンドまたはメッセージ数で測定されます)。

アルゴリズムのパフォーマンスを予測するために数えるべき (そして数えない!) 他に興味深いものは何ですか?

また、これらのモデルはどれくらい優れていますか? 私が聞いた限りでは、キャッシュを無視するアルゴリズムは、ディスク上のデータに対する 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 範囲ではなく KB 範囲) をコピーするのが、訓練されていた予想よりもはるかに高速であることがわかりました。おそらく、これは現在使用されている大規模なキャッシュに関係しているか、または単に非常に高速なプロセッサ速度に関係しています。しかし、結果として、データのコピーを回避するためだけに、自分のコードをひどく改変する必要はもうありません。

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

「ゼロ バッファ」デバイス ドライバが速度の代名詞だった時代は終わりました。