NP 困難な問題を (おおよそ) 解決するプログラム (大学向けのプロジェクト) を作成する必要があります。これは線形順序付け問題のバリエーションです。一般に、(グラフとして) 非常に大きな入力があり、(各ソリューションを「評価」する関数に基づいて) 最適なソリューションを見つけようとします。
これを C スタイルのコード (1 つのメインと関数) で記述するか、Solver クラスを構築し、インスタンスを作成してメインから「実行」メソッドを呼び出すと、違いはありますか (Java に似ています)。
また、反復ごとに多くの浮動小数点演算が行われます。
ありがとう！
いいえ。
最大のパフォーマンスの向上/欠陥は、実装するアルゴリズムと、実行する不要な作業の量にあります (不要な作業とは、キャッシュされた可能性のある以前の値の再計算から、メモリ プールの使用に対する malloc/free の使用まで、すべての可能性があります。不変の大きなデータを参照ではなく値で渡す)
最適なコードを実現するための最大の障害は、もはや言語 (適切にコンパイルされた言語の場合) ではなく、プログラマーです。
いいえ、仮想機能を使用している場合を除きます。
編集：実行時のダイナミズムが必要な場合は、はい、仮想関数は手動で構築されたif-elseステートメントと同じかそれよりも高速です。ただし、メソッドの前にキーワードをドロップしても、virtual実際にはポリモーフィズムが必要ない場合は、不要なオーバーヘッドが発生します。コンパイラは、コンパイル時にそれを最適化することはありません。私がこれを指摘しているのは、C++ の機能の 1 つが「ゼロ オーバーヘッドの原則」を破っているからです (Stroustrup を引用)。
補足として、fp数学の多用について言及しているので：
-mfpmath=sse、-ffast-mathおよび-mrecip(最後の 2 つは「少し危険」です。速度と引き換えにエッジケースで奇妙な結果が得られます.最初のものは精度を少し低下させます.80ビットの代わりに64ビットの倍精度があります.しかし、この余分な精度はしばしば必要ありません.)これらのフラグは同様にうまく機能します. C および C++ コンパイラ用。
INFINITY、大きいが無限ではない値で true をシミュレートすると、速度が大幅に向上する場合があります。これはINFINITY、プロセッサが true を特別なケースとして処理する必要があるためです。
経験則 - 何を最適化するかがわかるまで最適化しないでください。したがって、C++ から始めて、動作するプロトタイプを用意してください。次に、プロファイルを作成し、アセンブリのボトルネックを書き直します。しかし、他の人が指摘したように、選択したアルゴリズムは言語よりもはるかに大きな影響を与えます。
パフォーマンスについて言えば、C で実行できることはすべて C++ でも実行できます。たとえば、仮想メソッドは「遅い」ことが知られていますが、それが本当に問題である場合は、C のイディオムに頼ることができます。
void*C++ にはテンプレートも用意されているため、ジェネリック プログラミングに使用するよりもパフォーマンスが向上します。
クラスはSolver一度構築され、runメソッドは一度実行されます...そのような環境では、違いは見られません。代わりに、次の点に注意してください。
メモリ管理は非常に高価です。小さなことをたくさんしなければならない場合malloc()、オペレーティング システムがあなたの昼食を食べてしまいます。近いうちに同じようなことをすることがわかっている場合は、作成したデータ構造を再利用するために断固たる努力をしてください。
クラスをインスタンス化するということは、通常、メモリを割り当てることを意味します。繰り返しますが、少数のオブジェクトをインスタンス化して再利用するためのコストは実質的にかかりません。ただし、破棄してすぐに再構築するためだけにオブジェクトを作成しないように注意してください。
問題が許す限り、アーキテクチャに適した浮動小数点のフレーバーを選択してください。より多くのメモリが必要になりますが、double最終的に よりも高速になる可能性があります。floatこれを微調整するには、実験する必要があります。理想的には、#defineorを使用しtypedefて型を指定し、1 か所で簡単に変更できるようにします。
整数計算は、おそらく浮動小数点よりも高速です。データの数値範囲によっては、整数を固定小数点として扱うことを検討することもできます。小数点以下 3 桁が必要な場合は、ints を使用して「ミリ程度」と見なすことができます。除算と乗算の後に小数をシフトすることを覚えておく必要があります...しかし、大したことではありません。もちろん、基本的な算術以外の数学関数を使用すると、もちろんこの可能性はなくなります。
ファイル入力やアルゴリズム自体と比較して、関数呼び出しとメンバー関数呼び出しのオーバーヘッドが制限要因になることはほとんどありません。C++ iostream は必ずしも超高速ではありません。本当に最適化している場合、C には「制限」があります。C++ では、関数呼び出しをインライン化する方が簡単です。全体として、C++ はコードを明確に編成するためのより多くのオプションを提供しますが、それが大きなプログラムではない場合、または C か C++ かに関係なく同様の方法でそれを作成する場合は、C ライブラリの移植性がより重要になります。
どちらもコンパイルされており、コンパイラは C++ の処理に非常に優れているため、唯一の問題はコードがどれだけ最適化されているかにあると思います。C++ で遅いコードを書く方が簡単だと思いますが、それはモデルがどのスタイルに最も適しているかによって異なります。
結局のところ、同じコンピューターで測定している場合、両方が適切に作成されていて、使用するライブラリがどれだけ適切に作成されているかを前提として、実際の違いがあるとは思えません。
仮想関数などを使用しない限り、パフォーマンスに大きな違いはありません。初期の C++ は C にコンパイルされていたため、(仮想関数などで) かなりのオーバーヘッドが発生する場所を正確に把握していれば、違いを明確に計算できます。
さらに、STL ライブラリと Boost ライブラリを使用すると、C++ を使用すると多くのメリットが得られることに注意してください。特に STL は、最も重要なデータ構造とアルゴリズムの非常に効率的で実証済みの実装を提供するため、開発時間を大幅に節約できます。
実際には、使用するコンパイラとコードの最適化方法にも依存します。
別の側面:
C++ テンプレートは、型固有/最適化されたコード バリエーションを生成するための優れたツールとなります。
たとえば、Cqsortではコンパレーターへの関数呼び出しが必要ですが、std::sort渡されたファンクターをインライン化できます。これは、比較と交換自体が安価な場合に大きな違いを生む可能性があります。
一連の定義またはコードジェネレーターを使用して、または手動で、さまざまなタイプに最適化された「カスタムqsorts」を生成できることに注意してください。これらの最適化はCでも実行できますが、コストがはるかに高くなります。
(これは一般的な武器ではありません。テンプレートは特定のシナリオでのみ役立ちます。通常、単一のアルゴリズムが異なるデータ型に適用されるか、異なる小さなコードが挿入されます。)
まず、C++ で書くことは OOP を使用することを意味するわけではありません。STL アルゴリズムを見てください。第 2 に、C++ は実行時に少しでも高速になる可能性があります (コンパイル時間は C に比べてひどいものになる可能性がありますが、これは、最新の C++ がコンパイラに負担をかける抽象化に大きく依存する傾向があるためです)。
edit : わかりました。Bjarne Stroustrup のqsort と std::sort に関する議論と、FAQ が言及している記事 ( Learning Standard C++ as a New Language ) を参照してください。彼は、C++ スタイルのコードが短くて読みやすいだけではないことを示しています (なぜならより高い抽象化の)、しかしまたいくらか高速です。
私は間違いなくC++を使います。デザインに注意し、ホットスポット内に重いオブジェクトを作成しないようにすると、パフォーマンスの違いは見られないはずですが、コードの理解、保守、拡張がはるかに簡単になります。
テンプレートとクラスを慎重に使用してください。参照によってオブジェクトを渡すことにより、不要なオブジェクトの作成を回避します。過度のメモリ割り当ては避け、必要に応じて、ホットスポットの前にメモリを割り当てます。メモリポインタにrestrictキーワードを使用して、ポインタがオーバーラップするかどうかをコンパイラに通知します。
最適化に関しては、メモリの配置に注意を払ってください。Intelプロセッサで作業していると仮定すると、メモリアライメントとエイリアスポインタについてプラグマを介してコンパイラに通知すれば、ベクトル命令を利用できます。組み込み関数を介して直接ベクトル命令を使用することもできます。
テンプレートを使用してホットスポットコードを自動的に作成し、サイズの異なる短いループなどがある場合は、コンパイラに最適化させることもできます。パフォーマンスを調べてボトルネックにドリルダウンするには、Intelvtuneまたはoprofileが非常に役立ちます。
それが役立つことを願っています
私はいくつかの DSP コーディングを行っていますが、アセンブリ言語を使用することで成果が得られる場合もあります。C または C++ のいずれかを使用し、必要に応じて、特に SIMD 命令を活用するために、アセンブリ言語に移行する準備をしておくことをお勧めします。
良い答え。私はそれを次のように言います：
形式的な構造に関して、アルゴリズムを可能な限り効率的にします。
C++ は C と同じくらい高速ですが、必要のないオブジェクトを作成するなど、ばかげたことをしたくなります。STL コンテナ クラスやイテレータなどは、最新かつ最高のもののように見えるかもしれませんが、ホットスポットでは致命的です。
とはいえ、解体レベルでワンステップ。問題に非常に直接的に取り組んでいることがわかるはずです。ルーチンに出入りするために多くのサイクルを費やしている場合は、インライン化 (またはマクロ) を試してください。メモリの割り当てと解放に迷い込んでいる場合は、ほとんどの場合、それをやめてください。ループ オーバーヘッドの割合が大きい内部ループがある場合は、ループを展開してみてください。
そうすることで、最速で完成させることができます。