13

繰り返しになりますが、私は自分が一連の間違った仮定に直面していることに気づきました。記事自体は、実証済みの最適なアルゴリズムを変更して仮想メモリを考慮することにより、パフォーマンスが 10 倍向上することについて説明しています。

いくつかのギガヘルツのクロック周波数で動作する最新のマルチイシュー CPU では、最悪の場合の損失は、VM ページ フォールトごとに約 1,000 万命令です。回転ディスクで実行している場合、その数は 1 億の命令に近くなります。

O(log2(n)) アルゴリズムは、これらの操作がページ フォールトやディスク操作の低速化を引き起こす場合、何の役に立つでしょうか? 最も関連性の高いデータセットでは、ページ フォールトを回避する O(n) または O(n^2) アルゴリズムでさえ、その周りを円で囲みます。

そのようなアルゴリズムはもっとありますか? 教育の基本的な構成要素をすべて再検討する必要がありますか? 自分で書くとき、他に何に注意する必要がありますか?

説明:

問題のアルゴリズムは、Big-O 表記に欠陥があるか無意味であるため、実証済みの最適なアルゴリズムよりも高速ではありません。実証済みの最適なアルゴリズムは、最新のハードウェア/OS では当てはまらない仮定、つまりすべてのメモリ アクセスが等しく交換可能であるという仮定に依存しているため、高速です。

4

5 に答える 5

14

アルゴリズムを再検討する必要があるのは、顧客がプログラムの遅さについて苦情を言ったり、重要な締め切りに間に合わなかったりした場合だけです。それ以外の場合は、正確性、堅牢性、読みやすさ、およびメンテナンスの容易さに重点を置いてください。これらの項目が達成されるまで、パフォーマンスの最適化は開発時間の無駄です。

ページ フォールトとディスク操作は、プラットフォーム固有の場合があります。常にコードをプロファイリングして、ボトルネックがどこにあるかを確認してくださいこれらの領域に時間を費やすことで、最大のメリットが得られます。

興味がある場合は、ページ フォールトやディスク操作の遅延に加えて、次の点に注意してください。

  • キャッシュ ヒット -- データ指向設計
  • キャッシュ ヒット -- 不要な分岐 / ジャンプを減らします。
  • キャッシュ予測 -- プロセッサのキャッシュに収まるようにループを縮小します。

繰り返しになりますが、これらの項目は、品質が達成され、顧客からの苦情があり、プロファイラーがプログラムを分析した後にのみ提供されます。

于 2010-06-12T18:55:36.473 に答える
3

GregS の回答をさらに詳しく説明します。違いは、有効な複雑さと漸近的な複雑さの違いです。漸近的複雑度は定数要素を無視し、「十分に大きい」入力に対してのみ有効です。多くの場合、「十分な大きさ」とは、実際には「現在および数十年にわたって、どのコンピューターでも処理できるよりも大きい」ことを意味します。これは、理論が(当然のことながら)悪い評判を得るところです。もちろん、「十分に大きい」とはn =3 を意味する場合もあります。

これを調べるより複雑な (したがってより正確な) 方法は、最初に「関心のある問題のサイズ範囲はどのくらいですか?」と尋ねることです。次に、そのサイズ範囲でさまざまなアルゴリズムの効率を測定して、「隠れた定数」の感覚をつかむ必要があります。または、実際に定数の推定値を提供するアルゴリズム漸近法のより細かい方法を使用できます。

他に注目すべきは「遷移点」です。もちろん、2 n 2時間で実行されるアルゴリズムは、すべてのn < 1.99 * 10 17に対して 10 16 n log( n ) 回で実行されるアルゴリズムよりも高速になります。そのため、二次アルゴリズムが選択されます (CERN が懸念するデータのサイズを扱っている場合を除きます)。準指数項でさえ噛み付くことがあります – n < 5*10 15の場合、3 n 3はn 3 + 10 16 n 2よりもはるかに優れています (これらが実際の複雑さであると仮定します)。

于 2010-06-12T20:37:26.063 に答える
3

重要なことの 1 つは、big-O 表記の最も一般的な使用法 (ランタイムの複雑さについて話すため) は話の半分にすぎないことを認識することです。別の半分、つまり空間の複雑さ (big-O を使用して表現することもできます) があり、また、非常に関連性があります。

一般に、最近では、メモリ容量の進歩がコンピューティング速度の進歩を上回っているため (シングル コアの場合、並列化によりこれを回避できます)、スペースの複雑さはあまり重視されていませんが、特にメモリ容量を備えたマシンでは、依然として心に留めておくべき要素です。より限られたメモリ、または非常に大量のデータを扱う場合。

于 2010-06-12T18:53:06.393 に答える
1

O(n) はストーリーの一部にすぎません。大きな部分であり、多くの場合支配的な部分ですが、常に支配的な部分であるとは限りません。パフォーマンスの最適化 (開発の早い段階で行うべきではありません) に到達したら、使用しているすべてのリソースを考慮する必要があります。アムダールの法則を一般化できますつまり、実行時間は最も限られたリソースによって支配されます。これは、実行している特定のハードウェアも考慮する必要があることも意味することに注意してください。超並列コンピュータ (CM や MassPar など) 向けに高度に最適化され、非常に効率的なプログラムは、大きなベクトル ボックス (Cray-2 など) や高速マイクロプロセッサではうまく機能しないでしょう。そのプログラムは、多数の有能なマイクロプロセッサー (map/reduce スタイル) ではうまく機能しないかもしれません。キャッシュ、CPU 通信、I/O、CPU 速度、メモリ アクセスなどのさまざまなバランスに対するさまざまな最適化は、さまざまなパフォーマンスを意味します。

私がパフォーマンスの最適化に時間を費やしていた頃は、システム全体で「バランスのとれた」パフォーマンスを目指していました。低速の I/O システムを備えた超高速の CPU はほとんど意味がありませんでした。O() は通常、CPU の複雑さのみを考慮します。メモリ スペースをトレードオフできる場合があります (ループをアンロールしても O() は意味がありませんが、実際のパフォーマンスに役立つことがよくあります)。キャッシュ ヒット、リニア メモリ レイアウト、メモリ バンク ヒットに関する懸念。仮想メモリと実メモリ。テープ、回転ディスク、RAID など。パフォーマンスが CPU アクティビティによって支配され、I/O とメモリのローフィングが発生している場合、big-O が主な懸念事項です。CPU の使用率が 5% で、ネットワークの使用率が 100% の場合は、ビッグオーから離れて I/O やキャッシングなどに取り組むことができます。

特にマルチコアを使用したマルチスレッドは、そのすべての分析をさらに複雑にします。これは非常に広範な議論につながります。興味があれば、Google は数か月または数年の参考資料を提供できます。

于 2010-06-12T21:44:16.093 に答える
1

私が見る壊れた仮定はありません。Big-O 記法は、非常に単純化された理想化されたコンピューティング マシンでのアルゴリズムの複雑さの尺度であり、定数項は無視されます。明らかに、これは実際のマシンでの実際の速度に関する最終的な言葉ではありません。

于 2010-06-12T19:42:52.970 に答える