質問がやや広範または奇妙に思われる場合は、事前にお詫び申し上げます。誰かを怒らせるつもりはありませんが、誰かが実際に推奨できるかもしれません。同様の質問を探してみましたが、寒くはありません。
コードの最適化について教えてくれる、より優れたリソース (本、ブログなど) はどれですか?
コードをより人間が読めるようにするためのリソースはかなりあります (Code Complete がおそらく一番の選択肢です)。しかし、それをより高速に、よりメモリ効率よく実行するにはどうすればよいでしょうか?
もちろん、特定の言語ごとにたくさんの本がありますが、メモリ/操作速度の問題をカバーし、言語に依存しないものがあるのだろうか?
メモリの最適化に関して一般的に役立つリンクをいくつか示します。
Ulrich Drepper によるメモリについてすべてのプログラマが知っておくべきこと
Herb Sutter: フリーランチは終わった: ソフトウェアの並行性への根本的な転換
スライド: Herb Sutter: マシン アーキテクチャ (プログラミング言語が教えてくれないこと)
ビデオ: Herb Sutter @ NWCPP: マシン アーキテクチャ: プログラミング言語では決して語られないこと
Intel、AMD、および VIA CPU のマイクロアーキテクチャ アセンブリ プログラマおよびコンパイラ メーカー向けの最適化ガイド、Agner Fog 著
go to Statements で構造化プログラミングを読んでください。「時期尚早の最適化は諸悪の根源である」という言葉は、誰かが何かをより速くしたり小さくしたりしたいと思った瞬間に出てくる言葉の源ですが、それがどんなに重要であるかプロセスの後半であっても、実際には次の重要性についてです。可能な限り物事を効率化します。
時間の複雑さ、空間の複雑さ、およびアルゴリズムの分析について学びます。
時間の複雑さを改善するために空間の複雑さを犠牲にしたい、またはその逆の例を考えてください。
選択した言語とフレームワーク、特に最も頻繁に使用するフレームワークが提供するアルゴリズムとデータ構造の時間と空間の複雑さを理解してください。
適切なハッシュ コードの作成に関する質問については、このサイトの回答をお読みください。
古いデータを不適切に使用するという不利益を被ることなく、キャッシングの利点を得るためにHTTPがとったアプローチを調べてください。これをインメモリ キャッシュに適用するのがどれほど簡単か、または難しいかを検討してください。あなたが「それをねじ込んでください、私はそれが私に与えるスピードブーストのために古くても生きていける」と言うときを考えてみてください. あなたが「やめろ、それが私に与える新鮮さを保証するために遅くても生きていける」と言うときを考えてみてください.
マルチスレッドの方法を学びます。いつパフォーマンスが向上するかを学びます。なぜそれがよくないか、さらに悪化させるのかを学びましょう。
Joe Duffy の多くのブログを見てください。パフォーマンスは、彼の執筆の定期的な関心事です。
毎回、各項目でいっぱいのデータ構造を構築および再構築するのではなく、項目をストリームまたは反復として処理する方法を学びます。実際にそうしない方が良い場合を学びましょう。
物事の費用を知る。それぞれが実際に何が原因であるかがよくわからない限り、「これはネットワーク経由ではなく、ディスク/ディスクではなくメインメモリ/メインメモリではなくCPUキャッシュにあるので、うまくいく」と合理的に判断することはできませんヒットすること、およびコストの違いは何ですか。さらに悪いことに、コストがわからない場合、何かを時期尚早の最適化として却下することはできません。何かを最適化することを気にしないことが最善の選択であることがよくあります。最適化」、あなたは混乱していて、それが機能することを望んでいます.
使用しているスクリプトエンジン/ジッター/コンパイラーなどによってどのような最適化が行われるかについて少し学んでください。彼らに反対するのではなく、彼らと協力する方法を学びましょう。とにかく、それがあなたのためにする仕事をやり直さないように学びましょう。場合によっては、同じ一般原則を自分の仕事に適用できる場合もあります。
このサイトで、実装の詳細として何かが却下されているケースを検索してください。はい、それらはすべて、問題の詳細がその時点で最も重要なものではない場合ですが、それらの実装の詳細はすべて理由があって選択されたものです。彼らが何であったかを学びましょう。反論を学びましょう。
編集（これにさらにいくつか追加していきます）：
もちろん、本によって効率性の問題を強調する点は異なりますが、Stroustrup のThe C++ Programming Language では、効率性に関連するいくつかの異なるオプションの選択について説明する良い機会が何度かあったことを覚えています。 「外部から」クラスのユーザビリティに影響を与えるために、効率のために意思決定を行わないようにする方法。
これは私を別のポイントに導きます。さまざまなプロジェクトで再利用するライブラリ コードの効率に集中してください。非常に特殊なケースでない限り、「より効率的にするためにここで新しいものを手動でロールする必要があるかもしれない」と考えたくはありません。頻繁に使用されるクラスを効率的にするために多くの作業が行われたことを確信したいでしょう。多くの場合、ホットスポットの特定に集中してください。
特殊なケースに関しては、よりあいまいなデータ構造のいくつかは、それらが提供するケースについて知っておく価値があります。たとえば、DAWG は、パターンに一致するものをリスト内で見つけたい場合に、多くの一般的な接頭辞と接尾辞 (ほとんどの自然言語ではほとんどの単語になります) を含む文字列を格納するための非常にコンパクトな構造です。「ペイロード」が必要な場合、各文字が後続の各文字のノードのリストを持つツリー (DAWG の一般化ですが、ターミナル ノードではなくその「ペイロード」で終わる) には、すべてではありませんがいくつかの利点があります。彼らはまた、求める文字列の長さであるO(n)時間で結果を見つけます。n
それはどのくらいの頻度で出てきますか？多くはありません。それは私に一度（実際には数回、しかしそれらは同じケースの変種でした）出てきたので、それまでDAWGについて知っておくべきことをすべて学ぶ価値はありませんでした. しかし、それが後で調査する必要があることを十分に知っていたので、何ギガバイトも節約できました (実際には、16 GB の RAM を搭載したマシンでは処理しきれなかったのが、1.5 GB 未満になりました)。文字列をハッシュセットに入れるのではなく、手で丸めたDAWG に直行するのは完全に時期尚早の最適化です。
「DAWG での文字列の検索は O(n)」 「ハッシュセットでの文字列の検索は O(1)」 これらのステートメントは両方とも真ですが、2 つの速度は同等になる傾向があります。なんで？DAWG は、文字列の長さに関しては O(n) であり、DAWG のサイズに関しては事実上 O(1) であるためです。ハッシュセットは、ハッシュセットのサイズに関しては O(1) ですが、ハッシュの計算は通常、文字列の長さに関して O(n) であり、等価チェックもその長さに関して O(n) です。 . どちらの意見も正しかったのですが、別のことを考えていましたn。時間と空間の複雑さに関する議論では、常に何nを意味するかを知る必要があります。ほとんどの場合、それは構造のサイズになりますが、常にそうとは限りません。
一定の効果を忘れないでください: O(n²) は、n の値が十分に小さい場合、O(1) と同じです! O(n²) のようなものは、n²*k + n * k₁ + k₂ として変換されることを思い出してください。k₁ と k₂ が十分に低く、k と、比較している別のアルゴリズムまたは構造の k が十分に近いと仮定すると、それらは実際には問題ではなく、私たちが気にするのは n² だけです。これは常に正しいとは限りません。k、k₁、k₂ が高すぎて問題が発生することがあります。n が非常に小さくなり、さまざまなアプローチの定数コストの違いが問題になる場合も、そうではありません。もちろん、通常、n が小さい場合、大きな効率性の問題はありませんが、平均サイズが n で、m が大きい構造体に対して m 回の操作を行っている場合はどうなるでしょうか。O(1) アプローチと O(n²) アプローチのどちらかを選択する場合、全体として、O(m) アプローチと O(n²m) アプローチのどちらかを選択しています。前者を支持するのはまだ簡単に思えますが、n が低いと、本質的に 2 つの異なる O(m) アプローチのいずれかを選択することになり、定数係数がはるかに重要になります。
ロックフリーのマルチスレッドについて学びます。または、おそらくしないでください。個人的には、私が専門的に使用している 2 つの独自のコードがあり、最も単純なロックフリー手法以外はすべて使用しています。1 つはよく知られているアプローチに基づいており、今は気にしません (これは .NET2.0 用に最初に作成された .NET コードであり、.NET4.0 ライブラリは同じことを行うクラスを提供します)。私が最初に楽しみのために書いた他のものは、その楽しみのためだけの期間が私に信頼できるものを与えた後にのみ使用しました（そして、多くの場合、4.0ライブラリの何かにまだ打ち負かされていますが、私が気にかけている他のいくつかのものではありません約）。締め切りとクライアントを念頭に置いて、このようなものを書かなければならないのは嫌です。
とはいえ、興味本位でコーディングしているのであれば、そこに含まれる課題は興味深いものであり、実際にやっているときには得られない失敗した計画をあきらめる自由がある場合、一緒に仕事をするのは楽しいことです.有料のクライアント向けの何かであり、効率に関する一般的な懸念について多くのことを学ぶことができます. (私がこれで行ったことのいくつかを見たい場合は、 https://github.com/hackcraft/Ariadneを見てください)。
ケーススタディ
実際、これには上記の原則のいくつかの比較的良い例が含まれています。現在https://github.com/hackcraft/Ariadne/blob/master/Collections/ThreadSafeDictionary.csの 511 行目にあるメソッドを見てください(ここで、ダイクストラを引用している人々にとって炎の餌であるというコメントで冗談を言っています)ケーススタディとして使用してみましょう:
このメソッドは、再帰を使用するために最初に作成されました。これは、当然のことながら再帰的な問題であるためです。現在のテーブルで操作を実行した後、「次の」テーブルがある場合は、それに対してまったく同じ操作を実行する必要があり、それ以上の操作がなくなるまで繰り返します。テーブル。
いくつかの異なる方法では、再帰はほとんどの場合反復よりも遅くなります。すべての再帰呼び出しを繰り返しにする必要がありますか? いいえ、多くの場合、それだけの価値はありません。再帰は、実行内容が明確なコードを作成するための優れた方法です。ここでは上記の原則を適用しますが、これはパフォーマンスが重要な場所で呼び出される可能性のあるライブラリであるため、特定の努力が必要です。
速度を上げようと決心し、次に行ったのは測定です。「反復は再帰よりも速いことはわかっているので、再帰を避けるために変更すると速くなるはずです」に依存しません。それは真実ではありません - よく書かれていない反復バージョンは、よく書かれた再帰バージョンほど良くないかもしれません。
次の問題は、それをどのように書き直すかです。動作することがわかっているテスト済みの方法があり、別のバージョンに置き換える予定です。明らかに、動作しないバージョンに置き換えたくありません。既存のものを最大限に活用しながら書き直すにはどうすればよいでしょうか。
まあ、テール コールの除去については知っています。通常、スタックの管理方法を変更するコンパイラによって行われる最適化で、再帰関数が反復関数に近いプロパティになるようにします (ソース コードの観点からは依然として再帰的ですが、コンパイルされたコードが実際にどのように処理されるかという点では反復的です)。スタックを使用します)。
これにより、次の 2 つのことを考えることができます。 1. コンパイラが既にこれを行っている可能性があります。2. コンパイラがまだこれを行っていない場合は、同じ基本的なアプローチを手動で行うことができます。
その決定が下されたので、メソッドがそれ自体を呼び出したすべてのポイントを、次の呼び出しで異なる 1 つのパラメーターに変更して置き換え、最初に戻りました。つまり、次の代わりに：
CurrentMethod(param0.next, param1, param2, /*...*/);
我々は持っています：
param0 = param0.next;
goto startOfMethod;
それが終わったら、私は再び測定します。クラスの単体テスト全体を実行すると、以前より一貫して 13% 高速になりました。もっと近かったら、もっと詳細な測定を試みたでしょうが、このメソッドを呼び出しさえしないコードを含む実行で一貫して 13% という結果には、かなり満足しています。(また、コンパイラが同じ最適化を行っていなかったか、何も得られなかったこともわかります)。
次に、メソッドをクリーンアップして、新しいコードで意味のある変更を加えます。gotoそれらのほとんどは、確かに厄介なため、削除させてくれました（そして、完全にリファクタリングされgotoたため、同じ最適化が行われた他の場所はそれほど明白ではありません）。goto13% は後藤禁止のルールを破る価値があるので、一部は残しました。
したがって、上記は次の例を示しています。
goto最初のパスで導入された s のほとんどをリファクタリングします)。これらのいくつかは意見とスタイルの問題であり (いくつかを残すという決定にはgoto論争がないわけではありません)、私の決定に同意しないことは確かに問題ありませんが、この投稿でこれまでに提起された点を知っていると、十分な情報に基づいた意見の相違になります。 、ひざまずくものではなく。
他の回答で言及されているリソースに加えて、Michael Abrash のGraphics Programming Black Bookは、最適化について学ぶのに最適です。詳細は少し古くなっていますが、最適化へのアプローチ方法を学ぶための優れたリソースです。
コードを最適化したいときはいつでも、測定、測定、測定が絶対に不可欠です。最適化について学ぶ最良の方法の 1 つは、実行することです。最適化したいコードをいくつか取り、プロファイラーを使用してそのパフォーマンスを測定する方法を学び、変更を加えて結果を測定します。