アルゴリズムの概念と、基本的にアルゴリズムがコンピューター プログラムのパフォーマンスを向上させる方法を理解しようとしています。
したがって、次のようにして数値のリストを生成するプログラムを作成する必要があるとします。
番号 1 から始まります。
それに 3 を追加します。
結果 (1+3=4) をリストに格納します。
新しい数値に 5 を追加します。
結果 (4+5=9) をリストに格納します。
リストの最新の番号に 3 と 5 を交互に追加し続けます。
これは非常に単純なプログラムで、数値が 10,00,000 を超えるとプログラムを停止する必要があり、これを行う単純なプログラムでリストを生成するのに 10 秒かかるとします。
プログラムがリストを生成するのにかかる時間が短くなるように、この問題のアルゴリズムをどのように設計しますか?
注- ここでは、例を使用して概念を理解しようとしています。上記の時間はランダムであり、事実ではありません。上記の例を使用したくない場合は、誰かが「単純な」例で概念を理解するのを手伝ってくれると助かります。
上で示したもの (リストを作成するための手順のリスト)はアルゴリズムです。
通常、効率の大幅な向上は、あるアルゴリズムから、より少ない作業で同じ目的を達成する別のアルゴリズムに変更することを意味します。たとえば、上記のアルゴリズムでは、(そのような) リストを作成することをまったく避け、代わりに、リスト内の特定のスポットの結果を迅速に生成できるアルゴリズムに置き換えることができます。入力として N を指定すると、次のようになります。のようなことをする
int n = N/2;
int m = N-n;
return 1 + n * 3 + m * 5;
このコードはおそらく正確ではないことに注意してください (入力の奇数と偶数を正しく処理するとは思いません) が、一般的な考え方は理解できます。一連の操作全体を実行して 1 つの結果を取得するのではなく、同等の結果を生成するために、はるかに少ない数の操作を実行します。
プログラムまたはコードのスニペットのパフォーマンスを改善しようとする場合 (つまり、より優れたアルゴリズムを使用して同じ結果を計算する場合)、アルゴリズムの目に見える出力を考慮することが重要です。つまり、アルゴリズム (の出力) はどのように使用または消費されるのでしょうか? つまり、アルゴリズムは何を返し、その戻り値はどのように消費されるのでしょうか?
あなたの質問の上記の手順は、リストを作成する必要があることを示していますが、その後はどうすればよいでしょうか? 結果を破棄するだけの場合 (そのようなプログラムや関数は簡単に作成できます)、優れたオプティマイザー (人間または機械) は、結果が決して使用されないという事実に基づいて、null または空のプログラムまたは関数に置き換えることができます。（真剣に：これはベンチマークでよくある問題です。アルゴリズムは生成されたコードのパフォーマンスを測定するために何らかの結果を計算しますが、その結果は使用されないため、コンパイラは潜在的にループ全体、メモリ割り当て、おそらく関数全体を削除します!)
したがって、パフォーマンスを向上させるためにアルゴリズムを変更する方法の分析に関する質問の設定に関して本当に重要なことは、(プログラムの他の部分によって) 使用される出力の部分を特定または指定することです。
仕様 (アルゴリズムの結果がどのように消費されるか) が与えられると、逆方向に作業して、より少ない作業で同じ結果をもたらすアルゴリズムの改善を見つけることができます。
アルゴリズムを構成するとき、構成を調べて改善の機会を特定できます。別の言い方をすれば、上記のアルゴリズムは、一度に 1 つの値のみを見つけるために他のアルゴリズムで使用される可能性があります。つまり、Jeffry のソリューションは、パフォーマンスの優れた適切な置換アルゴリズムです。
ただし、リスト アルゴリズムの別のコンシューマは、その可視効果の別の部分を要求する場合があるため、別の最適化またはアルゴリズムの置換が適切な場合があります。上で説明したように、結果がまったく使用されず、それでも別の消費者がリスト内のノード数をカウントしたい場合がこれに該当します。この場合、まったく異なる最適化がより適切です。
場合によっては、アルゴリズムが何かを返すように指定でき、結果を消費しているのが誰なのかを知らずに何らかの理由でコードを生成する必要があります。そのような場合、オプティマイザー (人間またはマシン) は、返されるすべての可視効果が消費される可能性があるという悲観的な推定を行うことを余儀なくされます。たとえば、リストが（質問の追加仕様として）返されるものであり、オプティマイザーが消費をさらに詳しく調べないようにすると、実際にリストを作成する必要がある可能性が高いと仮定しましょう（したがって、ジェフリーの答えはうまくいきません）。
つまり、追加のコンテキストがなければ、問題とその解決空間を完全に分析することはできません。
部分的には、その追加のコンテキストは、明示的な return ステートメント (または、グローバル変数の変更など、外部から見えるその他の副作用) の形式を取ります。
さらに、その追加のコンテキストの一部は、(目的の元のアルゴリズムを使用して) 囲み、呼び出し、または構成する別のアルゴリズムの形をとる場合があります。したがって、最適化のプロセスは再帰的であり、(人間または機械) が「見る」ことができるほど、より良い結果が得られます。
あなたが与えた例では、はるかに速くすることはできません。リスト全体を出力する必要があり、説明したアルゴリズムはそれを効率的に行います。
問題を少し修正してみましょう: 1000000 より大きい最初の数値を出力するだけです。これは、リスト全体を生成するよりもスマートに解決できます。
コンピューター プログラムのパフォーマンスを向上させるためにアルゴリズムを使用していないということから始めましょう。アルゴリズムはプログラムです (定義上、アルゴリズムは問題を解決する一連の有限の操作です)。
もちろん、問題に完全に適用できる賢者によって発明された有名なアルゴリズムがあります (あなたの問題はグラフに関するものですか? 最短経路のダイクストラのアルゴリズム、最大フローの Ford-Fulkerson、最小スパニング ツリーの Prim と Kruskal) 、 等々）。一般に、そのような優れたパフォーマンスのアルゴリズムを最初から書き直すのではなく、プログラムに再利用することをお勧めします。
あなたはそれらを使いたいと思うでしょう
番号 1 に関しては、アルゴリズムのパフォーマンスを測定するには、ここでよりよく説明されているいくつかのことを行う必要があるため、いくつかの数学計算も含まれます。
残念ながら、私は大きな表記やそのようなパフォーマンス計算が好きではないので、ウィキペディアのリンクを指すだけでは役に立ちません。