プロジェクト用に実行しているコードがあります。これはO（N ^ 2）です。私の場合、Nは200です。このO（N ^ 2）をO（N logN）に変えるアルゴリズムがあります。これは、この新しいアルゴリズムを使用すると、約100倍高速になるはずであることを意味します。ただし、2倍の増加（別名2倍高速）しか得られていません。
私は物事を絞り込んで、何かを台無しにしたのか、それともこのプログラムのコーディング方法に固有のものなのかを確認しようとしています。手始めに、ネストされたクラス内に多くの関数オーバーヘッドがあります。たとえば、私はこれをたくさん持っています（多くのループ内に）：
energy = globals->pair_style->LJ->energy();
実際のデータに関しては正しい結果が得られているので、速度の増加が間違っているので、関数のオーバーヘッドによって実際に速度が50分の1に低下する可能性があるのではないかと思います。
ありがとう！
まず、の解釈よりもO(N logN)約100倍速い解釈は正しくありません。big-Oh表記は、制限の上限と動作を扱い、複雑さの乗法定数を考慮していません。O(N^2)N=200
第二に、はい、最近のハードウェアでは、パイプラインの中断により、関数呼び出しは比較的高価になる傾向があります。あなたの場合、これがどれほど大きな要因であるかを知るために、いくつかのマイクロベンチマークを考え出す必要があります。
絶対的な最大のヒットはキャッシュミスです。L1キャッシュミスは比較的安価ですが、L2（またはL3がある場合はL3）をミスすると、着信ストールまでに数百または数千のサイクルが失われる可能性があります。
ただし、これは問題の一部にすぎない可能性があります。プロファイルを作成するまで、コードを最適化しないでください。遅い領域を特定し、それらが遅い理由を理解します。実行速度が遅い理由を理解したら、最適化するチャンスがあります。
余談ですが、O表記は非常に便利ですが、すべてではありません。O（n ^ 2）アルゴリズムは、はるかに効果的にキャッシュされるため、少量のデータ（および少量は数千未満を意味する場合があります）に対してO（n log n）よりも大幅に高速に動作することを確認しました。
私は画像処理アルゴリズムに取り組んできましたが、ピクセルごとに関数を呼び出すと（つまり、640x480の場合は307200になります）、パフォーマンスが大幅に低下する可能性があります。関数をインラインで宣言するか、関数をマクロにしてみてください。これにより、関数呼び出しが原因であるかどうかがすぐにわかります。いくつかのプロファイリングツールを見てみてください。VS 2010にはいくつかの優れたツールが付属しています。それ以外の場合は、Intel VTune、glowcodeもあります。彼らはあなたが時間を過ごしている場所を示すのに役立ちます。
IMHO 1600の関数呼び出しでパフォーマンスが大幅に低下することはないと思います（200 log 200）
Big O表記の重要な点は、データセットのサイズが大きくなるにつれて、実行時間の制限のみを指定することです。定数はすべて破棄されます。O（N ^ 2）は実際にO（N log N）よりも遅いですが、実際の実行時間はN^2対1000NlogNである可能性があります。つまり、O（N ^ 2）はO（N一部のデータセットのログN）。
詳細がなければ、これ以上言うのは難しいです-はい、関数呼び出しには確かにかなりのオーバーヘッドがあり、それがパフォーマンスの大幅な向上が見られない理由かもしれません-または、O（ N log N）は、サイズのデータセットでは十分に機能しません。
を使用してプロファイリングすることをお勧めします
プロファイリングに関する大きなFAQトピックはここにあります：Linuxで実行されているC ++コードをプロファイリングするにはどうすればよいですか？
gprof（コンパイル時のインストルメンテーションが必要です）valgrind --tool=callgrindおよびkcachegrind; 優れた視覚化を備えた優れたツール-スクリーンショットはこちら：
