小さいながらも非常に有益な戦術レッスンを実施する素晴らしい機会がありました。
残念ながら、大量の計算を生成するプログラムを最適化する問題は文献で十分にカバーされておらず、原則としていくつかの一般原則に要約されています。その忠実度は、著者の議論を読む前でも後でも完全には明らかではありません。 上記の投稿（引用符による検索）は、これらの原則と特定の最適化手法を実際に動作させることができる非興味深い計算タスクを提案したため、実際の投稿が作成されましたが、それは著者が好む方向とは多少異なります（私はかなりMKクラスM3およびArduinoでさえこの問題の解決策を見つけましたが、試してみましたが、すべて同じように、マイクロコントローラーは他のいくつかの目的のために設計されています）、それにもかかわらず、MKプログラミングコースの概念に適合しています。
それで、私たちは始めています。
問題を思い出させてください-最初の4つの5度の合計が最後の5度と等しくなるように、5つの非負の整数を見つける必要があります。 言葉遣いは完全に正確ではなく、さらに洗練されますが、最初はそれで十分です。 この問題を解決するための自然なアルゴリズムは、可能な数のセットをソートし、それらの条件が満たされていることを確認することです。 特定の境界を超えない数値の条件をすぐに明確にします。そうしないと、そのようなセットがまったく存在しない場合に検索が終了しない可能性があります（負ではない整数のうち5つのセットすべてを真剣にチェックすることは望んでいません。私は検索の終わりを見るために生きません）。 この自然な解決策を書いて、現代のプログラミングの1つの重要な機能をすぐに指摘します。
x86 i3-2120 3.3 GHzマシンのMinGWコンパイラバージョン6.2ですべてのプログラムを実行することにすぐに同意するため、これらの数値は示されていません。 システムパラメータが私のものと異なる場合、時間インジケータの絶対値はわずかに異なりますが、異なるオプションの相対的な動作時間は近いはずです。
私たちが見ているのは、100未満の数字のセットの中で、与えられた条件を満たすセットが見つかりませんでした（実際、それらの多くがありますが、数字は異なり、ゼロに等しくないため、私たちには合いません... ？-TK）の正確な定式化を支持する別の引数であり、列挙の過程で1e10の組み合わせをチェックしました。 同時に、プログラムは63秒間実行されました。
条件の形成が不完全であるため、プログラムが正しくないことは既にわかっていますが、修正を始める前に、一定のアルゴリズムを使用した計算の高速化について説明します。 私の時間には、時間の経過に伴うマシンに依存しない実行の最適化に関する推奨事項を示す本がありました。このアルゴリズムには次の推奨事項が適しています。
-内側のループから計算の一部を取り出し、最初の3つの数値の中間和を形成します。
-内部サイクルを編成して、インデックスを増やすのではなく減らす。
-内部ループをdo {} whileの形式で整理します。
-インデックス変数レジスタを作成します。
-5度の計算を最適化し、乗算の数を4から3に減らします
-コンベアなどをブロックしないようにインターリーブ度の計算...
最初はこれらすべての変更を実行してパフォーマンスへの影響を示し、パフォーマンスの数十パーセントが時間の増加にどのように変わるかを実証するつもりでしたが、その後この考えを捨てました。
実際、これらの推奨事項はやや時代遅れであり、現在プログラマーに必要なのはコンパイラにレベル3で最適化を実行させることだけです。はい、これを行う方法を知る必要があります。私の場合、最適化管理はProject / Settingセクションに隠されています...-コンパイル/最適化。ただし、この種の最適化を行うために知っておく必要があるのはそれだけです。 私の投稿の定期的な読者（私はそのようなものがあることを願っています）はすでに、私が職業に入ったときと比較して、現代の電子機器の道徳の低下と不十分な緑の草についてのうめき声を見ることに慣れていますが、今はまったく拒否していません最適化が許可されている場合、最新のコンパイラは前のコンパイラよりもはるかに優れており、生成されたコードの点でほぼ理想的であると確信を持って述べなければなりません。
このような強力なステートメントには証明が必要です。最適化を有効にしてプログラムをコンパイルすると、同じプロセッサ上で実行時間が20秒、つまり速度が3倍になります（主に最初の推奨によるものですが、他のものも5番目まで貢献しました）加速の部分）と私たちの側のわずかな努力なしで素晴らしいです。 希望する人は、パフォーマンスを向上させるために私が言及したすべての方法を実行して結果を見ることができますが、生成されたアセンブラコードを見て、それを改善することはほとんど不可能であることを認識することを強くお勧めします。 元の投稿の著者に参加することで、gcc.godbolt.orgのサイトを強くお勧めします。このサイトでは、さまざまなアーキテクチャおよびさまざまな最適化モードでgccコンパイラによって生成されたコードを確認できます。
パフォーマンスの向上は非常に大きく、アルゴリズムに依存しない最適化のトピックは使い果たされていますが、ポストはこれで終わりではありません。本当に他に何かすることがありますか。 はい、プログラムを改善する（速度を上げる）何かと方法がありますが、ここでコンパイラはもはや私たちのアシスタントではありません。彼はコードで実行されたアクションの本質を理解しておらず、必要な変更を提案できないため、プログラマだけがこれを行うことができます 私の意見では、現代のソフトウェア開発ツールでさえ創造性の余地を残しているため、これは成功です。私の若い同僚は、現代のコンパイラーの進歩に不便を感じました：「それはあなたにとって簡単で、コンパイラーは何も最適化しないことを知っていました、それはありません私たちはすべてを手作業で行いたいと思っていましたが、作業のどの部分が始まるかを決定する必要があります。」 私が言えること-ペンで必要な最適化をすべて行っても、間違いなく悪化することはありません（作業が複製されるため、どちらも改善されません）。したがって、最後に行くことを妨げるものは何もありません。
プログラムに戻り、スピードアップする方法を探します。 むしろ、そのようなメソッドを探す前に、このアクションが必要であることを確認する必要があります。 境界のさまざまな値の実行時間を確認し、値の60と70の値が2倍以上異なることを確認します。これにより、アルゴリズムの実行時間に関する仮説は約（N ** 5）：70/60 = 1.17 ** 5 = 2.2倍。 取得した式を使用して、プログラムの実行時間を1000の境界で推定し、553時間を取得します。これは、予想をわずかに上回ります。多数の場合、時間が短くなることはありません-最適化するのは理にかなっています。
次に、私が思い出すように、パラグラフはTRIZシステムの工学的問題を解決するための原則を示します。
除外の原則、または繰り返される作業の削除
これまでのところ、アルゴリズムの実行時間の推定結果を変更する機会はありませんが、決定項の係数を減らすことができます。 与えられた自然数の集合のすべての順列をソートし、それらをランク付けする可能性とオペランドの順序からの結果の独立性を考慮に入れていることがわかります。我々は、与えられた集合の要素の組み合わせを考慮する必要があると結論付けます。 組み合わせの列挙は、次の要素のループ変数の初期値を変更することで簡単に実装できます。これを行うと、プログラムの速度が2桁劇的に向上します。 まあ、それはそうでなければならない、我々は5のゲインを期待していました！ 回、これは正確に120です。
小さな余談-オリジナルの投稿では、著者はインデックスをさまざまな組み合わせで紙に書き留めて結果を調べた後、似たような考えに至りました。 彼の努力に敬意を表し、私は確率論の組み合わせ論と要素（要素、すべての栄光と力のターバーは単純とは言えないため）-これは数学の一部であり、それなしではアルゴリズムを分析するのは逆効果です。 もちろん、著者が組み合わせの生成方法を再作成できたことは嬉しいですが、掛け算表のように、それとすべてを知っている必要があります。 これは、プログラマが数学を必要とするかどうかについて定期的に発生する論争についての私ですが、これは個人的な会話で表現された私の個人的な意見であり、誤っている可能性があります。
メイントピックに戻ると、これは正確にコンパイラーが実行しない最適化です。ここでは、タスクの本質とソリューションを実装するアルゴリズムを理解する必要がありますが、まだ実行できません（2つのコマンドを使用するコンパイラーは、まだ実現されていない理想ですが、次に来ます）。 また、別の重要な機能-通常、このような最適化の利点は、コンパイラによって実行される最適化から得られる可能性のある利点よりも何倍も大きくなります。 結果を要約し、それらをいくつかの大きな値に外挿しようとします。
フロンティア__最適化なし____コンパイラ______私たちの________両方
10 _________ 0.00 _____________ 0.00 __________ 0.00 ________ 0.00
50 _________ 2.32 ______________ 0.66 __________ 0.02 ________ 0.01
100 ________ 62.91 _____________ 19.93 _________ 0.49 ________ 0.16（1.43）
150 _______ 476.20 ____________ 150.67 _________ 3.80 ________ 1.21（10.99）
1000_______1800時間* ____________ 553時間* _________ 14時間* _______ 5時間*（35時間*）
（括弧内は結果タイプlong longの計算時間です）。
元のバージョンが200を超える境界値で実際に受け入れられなかった場合、最後のオプションは値1000まで適用できます。さらに、2つのソリューションが見つかりましたが、そのうちの1つはオーバーフローのために間違っていますが、後で詳しく説明します。それまでの間、パフォーマンスの改善を再度試みます。
予備執行の原則
明らかな解決策-度を事前に計算してテーブルから選択することは間違いなく結果を与えましたが、率直に言って、期待していたよりも少し小さく、明らかに、乗算の実装では、x86は問題ありませんが、配列からの選択は悪いです しかし、それでも、ほぼ8倍の増加は非常に良いことです。 （何らかの理由で、結果の型がintのバリアントのパフォーマンスはまったく向上しません）。 純粋に理論的には、そのような最適化を実行するコンパイラを想像できますが、これまでのところこれを見たことはありません。 最適化の2つの方向-時間とメモリの原則が互いに矛盾しているため、この場合、速度のために余分なメモリを支払う必要があるという事実に注意してみましょう。
#include "time.h" #include "stdio.h" #define LOOP(n,m) for (int n=m+1; n<=MAX; n++) #define REZ(i) (Pow5[i]) typedef long long int rez_t; int main(void) { rez_t Pow5[1001]; for (int i=0; i<=1000; i++) Pow5[i]=(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i; for (int MAX=50; MAX<=500; MAX+=50) { clock_t t = clock(); unsigned long long v=0; int r=0; LOOP(i1,0) LOOP(i2,i1) LOOP(i3,i2) { rez_t Sum = REZ(i1)+REZ(i2)+REZ(i3); LOOP(i4,i3) LOOP(i5,i4) { v++; if (Sum+REZ(i4)==REZ(i5)) { r++; printf("%4d %4d %4d %4d %4d \n",i1,i2,i3,i4,i5); }; }; }; t = clock() - t; printf ("MAX=%d time is %f seconds.\n", MAX, ((double)t)/CLOCKS_PER_SEC); printf(" %llu %d\n",v,r); }; return 1; };
制限の原則、または不適切なオプションの除外
さらに進んで、いくつかの問題を再定式化するための追加の方法を探します-5次が特定の数に等しい数を見つける必要があります（これは他の4つの数の5次の合計ですが、これは問題ではありません）。 この定式化により、「検索」という単語に集中でき、すぐに最適化の方向のアイデアが促されます-検索の高速化、すべての可能な値をソートすることで線形になりました。これは、順序付けられたデータセットに最適な方法ではありません。 最初の考えはバイナリ検索であり、そのような方向は生産性の大幅な向上をもたらす可能性がありますが、逆の方向に進みます-昇順で値を並べ替えており、目的の値がすでに超えているため、明らかに解決策ではないオプションの検討を停止します 2倍の速度の向上が期待できますが、正確な解析的推定はほとんど不可能であり、実際にはほぼ5倍の加速が得られます。
ちょっとした注意-この方法に切り替えるには、結果の型をdouble整数に変更する必要がありました。 事実は、提案された方法では候補番号の5度の順序付けが必要であり、等式n> mから私の最も深い後悔まで、nまたはmのいずれかがkを超える場合、n％k> m％kは続きません。 私たちは整数で作業しているので、kはどこから来たのかと尋ねますが、実際には、実際に実行可能なアーキテクチャでは、整数（算術演算の実行速度が合理的である場合）はビット深度が制限されているため、それぞれの結果を取得する必要があります表現可能な最大数を法とする演算。 32ビットの結果がある場合、この数は（2 ** 32）-1〜2 ** 32 =（2 ** 2）*（2 ** 30）= 4 *（（2 ** 10）** 3）〜4 *（（10 ** 3）** 3）= 4 *（10 ** 9）= 0.4 *（10 ** 10）この数値の5番目のルートは100に近い数値（正確な値） 84）。 次に、64ビットの結果の場合、境界7130の最大値を取得し、128ビットの結果の場合、最大50e6を取得します。
#include "time.h" #include "stdio.h" #define LOOP(n,m) for (int n=m+1; n<=MAX; n++) #define REZ(i) (Pow5[i]) typedef long long rez_t; int main(void) { rez_t Pow5[1001]; for (int i=0; i<=1000; i++) Pow5[i]=(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i; for (int MAX=50; MAX<=500; MAX+=50) { clock_t t = clock(); unsigned long long v=0; int r=0; LOOP(i1,0) LOOP(i2,i1) LOOP(i3,i2) { rez_t Sum3 = REZ(i1)+REZ(i2)+REZ(i3); int i4=i3+1; do { rez_t Sum4 = Sum3 + REZ(i4); int i5=i4+1; do { v++; if (Sum4==REZ(i5)) { r++; printf("%4d %4d %4d %4d %4d \n",i1,i2,i3,i4,i5); }; i5++; } while ((Sum4>=REZ(i5)) && (i5<=MAX)); i4++; } while (i4<=MAX); }; t = clock() - t; printf ("MAX=%d time is %f seconds.\n", MAX, ((double)t)/CLOCKS_PER_SEC); printf(" %llu %d\n",v,r); }; return 1; };
推定の原理、または以前の結果を使用する（キャタピラー）
悪くはありませんが、バイナリ検索の方がはるかに優れているはずですが、この方法を推奨する別の考慮事項を考慮します-前のサイクルよりも小さい数値を見ていない場合、以前の量よりも少ないため、検索時間を大幅に短縮できます、それらは現在のものよりも小さいことが保証されており、前のものを超えています。 4番目と5番目の数値についてはキャタピラー法に基づいて作業できることがわかります。この方法を使用する場合、保証される反復回数は2 * nを超えることはできません。nは間隔の長さで、以前の必要な数値と比較されます反復n *（n-1）/ 2は（n-1）/ 4回勝ちます。これは、大きな数の場合に非常に重要です。 さらに、反復回数は、バイナリ検索の場合よりもさらに優れています。バイナリ検索はn * log2（n）であり、n> 2 ** 2 = 4でも値を超えます。
#include "time.h" #include "stdio.h" #define LOOP(n,m) for (int n=m+1; n<=MAX; n++) #define REZ(i) (Pow5[i]) typedef long long rez_t; int main(void) { rez_t Pow5[1001]; for (int i=0; i<=1000; i++) Pow5[i]=(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i; for (int MAX=50; MAX<=500; MAX+=50) { clock_t t = clock(); unsigned long long v=0; int r=0; LOOP(i1,0) LOOP(i2,i1) LOOP(i3,i2) { rez_t Sum3 = REZ(i1)+REZ(i2)+REZ(i3); int i4=i3+1; int i5=i4+1; do { rez_t Sum4 = Sum3 + REZ(i4); if (Sum4 >= REZ(i5)) do { v++; if (Sum4==REZ(i5)) { r++; printf("%4d %4d %4d %4d %4d \n",i1,i2,i3,i4,i5); }; i5++; } while ((Sum4>=REZ(i5)) && (i5<=MAX)); i4++; } while ((i4<=MAX) && (i5<MAX)); }; t = clock() - t; printf ("MAX=%d time is %f seconds.\n", MAX, ((double)t)/CLOCKS_PER_SEC); printf(" %llu %d\n",v,r); }; return 1; };
素晴らしい事実-初めて、決定項の前の係数ではなく、その順序を下げることができました。これにより、考慮された数値の境界の大きな値の作業が非常に大幅に加速されます。 結果を再び表に表示し、得られた値を喜ぶ
境界__度表___制限5__キャタピラー法__反転法
100 ________ 0.3 _________________ 0.1 __________ 0.02 ____________ 0.04
150 ________ 1.8 _________________ 0.6 __________ 0.14 ____________ 0.28
200 ________ 6.6 _________________ 2.3 __________ 0.49 ____________ 0.36
300 _______ 50.4 ________________ 16.1 __________ 2.14 ____________ 2.26
1000_______6時間* ________________ 1.5時間* _______ 210.0 ____________ 880 *
5000_______2 g * ________________ 0.5 g * ________ 36時間*
さらに計算すると、24日以内に1万の境界の結果が得られることが期待できることが示されていますが、実際には許容されますが、これは行いません。
トピックのさらなる検討は、5次の顕著な特性、つまり11を法とする少数の残基を考慮して計画されましたが、このトピックはオイラー仮説のトピックに関する次の投稿で十分に開示されており、このプロパティを使用する簡単な方法はないことに注意してください（表示されません）が、難しいものには同じだけの無作法なメモリが必要です。
反転法
したがって、一方で問題を検討し続けます-次のように問題を再定式化します-5度の合計が自然数の5度になる4つの自然数を見つけます。 一見、特別なことは何も起こりませんでしたが、タスクを最後から開始することができます-希望する量を要求し、それを構成しようとします。 このアプローチにより、適切な数に関する制限をすぐに策定できます。 たとえば、4つの数値のうち最大のものについては、必要な数値を超えることはできず（これは簡単なことです）、その5次は必要な数値の4分の5より小さくすることはできません（しかし、これはそれほど簡単ではありませんが、明白です） n-1からn *（4のうち5次の1根= 1.32）の有効な候補、つまり3回。 さらに、4番目の数字の役割の候補を取得すると、残りの差をすぐに計算し、3番目の数字の役割の候補を選択することができます。 私は個人的にそのような最適化の結果を分析的に評価するつもりはないので、プログラムを書いて結果を見るだけです。
#include "time.h" #include "stdio.h" #define LOOP(n,m) for (int n=m+1; n<=MAX; n++) #define REZ(i) (Pow5[i]) typedef long long rez_t; int main(void) { rez_t Pow5[1001]; for (int i=0; i<=1000; i++) { Pow5[i]=(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i; }; for (int MAX=100; MAX<=1000; MAX+=50) { clock_t t = clock(); unsigned long long v=0; int r=0; int i5=MAX; do { int i4=i5-1; do { rez_t Ost1=REZ(i5)-REZ(i4); int i3=i4-1; if (REZ(i4)*4 > Ost1) do { rez_t Ost2 = Ost1-REZ(i3); int i2=i3-1; if ((REZ(i3)*3 > Ost2) && (Ost2>0)) do { rez_t Ost3=Ost2-REZ(i2); int i1=i2-1; if ((REZ(i2)*2 > Ost3) && (Ost3>0)) do { v++; if (Ost3==REZ(i1)) { r++; printf("%4d %4d %4d %4d %4d \n",i1,i2,i3,i4,i5); }; i1--; } while (i1>0); i2--; } while (i2>0); i3--; } while (i3>0); i4--; } while (i4>0); i5--;} while (i5>0); t = clock() - t; printf ("MAX=%d time is %f seconds.\n", MAX, ((double)t)/CLOCKS_PER_SEC); printf(" %llu %d\n",v,r); }; return 1; };
悪くはありませんが、係数を大幅に削減することができましたが、順序は同じままで、大きな値では以前のプログラムでは失われます。
そして、ここからインスピレーションが得られます-新しい方法から始めて、2つの上級用語の列挙を大幅に減らします。そして、すでに合計がわかっているので、trackメソッドを使用して最も若い2つの用語を検索します!!! （感嘆符の数は、アイデアの力と一致しています）。 つまり、1に等しい最小数、次の値-古い値を考慮して可能な最大値を取得し、結果に応じて間隔の下限または上限を移動します。
#include "time.h" #include "stdio.h" #define LOOP(n,m) for (int n=m+1; n<=MAX; n++) #define REZ(i) (Pow5[i]) typedef long long rez_t; int main(void) { rez_t Pow5[1001]; for (int i=0; i<=1000; i++) { Pow5[i]=(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i; }; for (int MAX=100; MAX<=1000; MAX+=50) { clock_t t = clock(); unsigned long long v=0; int r=0; int i5=MAX; do { int i4=i5-1; do { rez_t Ost1=REZ(i5)-REZ(i4); int i3=i4-1; if (REZ(i4)*4 > Ost1) do { rez_t Ost2 = Ost1-REZ(i3); int i2=i3-1; int i1=1; if ((REZ(i3)*3 > Ost2) && (Ost2>0)) do { v++; rez_t Sum2=REZ(i1)+REZ(i2); if (Ost2==Sum2) { r++; printf("%4d %4d %4d %4d %4d \n",i1,i2,i3,i4,i5); }; if (Sum2>=Ost2) i2--; else i1++; } while (i1<=i2); i3--; } while (i3>0); i4--; } while (i4>0); i5--;} while (i5>0); t = clock() - t; printf ("MAX=%d time is %f seconds.\n", MAX, ((double)t)/CLOCKS_PER_SEC); printf(" %llu %d\n",v,r); }; return 1; };
ここにプログラムがあり、ここに結果があります-最大1000の値については、前のバージョンの10倍の21.7秒しか考慮していないため、最初のバージョンと比較しません。 そのようなプログラムを使えば、すでに数千のオーダーの値を狙うことができます。私はこれを好奇心reader盛な読者の共有に任せます。
すべての新年おめでとうございます。