初級から中級まで:バブルソート
はじめに
前回の「初級から中級まで:サンドボックスの操作」では、MetaTrader 5がサポートするサンドボックスの1つのナビゲーション方法を見てきました。 また、これを2つのまったく異なる方法で、それぞれ異なる目的のために実行できることも示しました。 操作方法の1つは、オペレーティングシステム自体に組み込まれたダイアログボックスを使うもので、サンドボックス内を移動するうえで最も実用的で、シンプルかつ便利な方法でした。
しかし、もう1つのナビゲーション方法も示しました。 この方法は、開発中のアプリケーションのコード内に直接実装されるため、多少複雑になります。 実は、この場合のナビゲーション機能の目的は、ユーザーとのシンプルで迅速なやり取りではありません。サンドボックス内にどのような種類のファイルが存在し、ディレクトリ構造がどうなっているかを把握するという、まったく別のものです。
この2つ目のアプローチ、より正確には、このサンドボックスの操作方法によって、いくつかの可能性が広がります。ここで少し探ってみましょう。 これは、アプリケーションのテスト中はすべてが完璧に見えるにもかかわらず、実際の運用では問題が発生することがよくあるためです。 ファイルやディレクトリがまったく無秩序に表示されることがあり、名前がソートされていない可能性はさらに高くなります。
これはよくある状況です。たとえば、ファイルやディレクトリの作成日や変更日に基づくフィルタを作成したい場合があります。 検索のためにファイルやディレクトリを特定の順序で表示し、目的の情報を見つけやすくするためです。 前回の記事で取り上げたコードの実装には、結果を順序立てて出力する仕組みがなく、簡単に実装できるようなフィルタリング機能すらありません。
任意の値をソートする、つまり結果をソートした状態で表示するには、コードに特定の要素を組み込む必要があります。 多くの初心者は、この段階で完全に混乱してしまいがちです。 これは、実行すべきタスクの種類に関係しています。このタスク自体は本質的に難しいものではありませんが、同じ目標をいくつかの異なる方法で達成できるという点に難しさがあります。 しかし、特定のプログラミング言語でこれを実装しようとすると、少々分かりにくくなる可能性があります。 他の言語で書かれたコードを、使用する言語に合わせて書き換えなければならないことがよくありますが、経験の浅い人の多くはそれができません。
とはいえ、ここでは率直に言っておきますが、私は特別な工夫をしたり、新しい概念を取り入れたりすることは一切しません。 ここでは、プログラミングではごく一般的でありながら、多くの初心者がその内部の仕組みすら知らないものの使い方を見ていくだけです。 それでは、次のセクションに進み、この記事の最も興味深い部分に入っていきましょう。 というのも、これはまさに、実践で扱う機会があるたびに私が心から楽しめる話題だからです。
泡のように
まず、皆さんもきっとすでにやったことがあるものについてお話ししましょう。 数値の配列を昇順にソートすることです。 なぜこの話を持ち出したのでしょうか。 その理由は簡単です。 MQL5の関数およびプロシージャのライブラリには、ArraySortという関数が含まれています。 この関数は、配列の内容を昇順にソートするためのものです。
この関数の動作をまだ見たことがない方のために、以下の短いコード例を使って、その動作を確認してみましょう。
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. void OnStart(void) 05. { 06. uchar info[10]; 07. 08. MathSrand(GetTickCount()); 09. 10. for (uint c = 0; c < info.Size(); c++) 11. info[c] = (uchar) MathRand(); 12. 13. Print("Array content before ordering..."); 14. ArrayPrint(info); 15. 16. ArraySort(info); 17. 18. Print("Array content after sorting..."); 19. ArrayPrint(info); 20. } 21. //+------------------------------------------------------------------+
コード01
コード01では、疑似乱数生成器を使用して小さな配列を初期化します。 この配列は06行目で宣言されています。 初期化は、10行目のループによっておこなわれます。 ただし、ここで特に注目したいのは、以下の行です。 これらの行では、まずソート前の配列を出力し、次にソート後の配列をもう一度出力します。 生成される値はランダムなので、結果は以下の図に示すものとは異なる可能性が高いです。

図01
これは、実行するたびに新しい値の列が生成されるためです。 ただし、ここで重要なのは、値が昇順にソートされていることを確認することです。 これは、コード01に含まれる16行目の関数によるものです。
しかし、これとサンドボックスの操作の構想と、いったいどのような関係があるのでしょうか。 ここからが本当に面白くなってきます。 多くの初心者は、ここで重要な点を理解していないかもしれません。 データが順序付きで表示される場合(昇順であれ降順であれ)、何らかのソート処理を経る必要があります。 これらの仕組みを理解しておくと、さまざまな課題に取り組む際に役立ちます。 実のところ、どのプログラミング言語にも、あらゆるデータ型をソートできる組み込みの実装が備わっているとは限りません。 ソートの仕組みを理解できれば、ソート処理を一般化した関数やプロシージャを作成できるようになります。 これにより、数値データやテキストだけでなく、その他のデータ型もソートできます。
たとえば、コード01を次のコードに置き換えてみると、コンパイルできないことがわかります。
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. void OnStart(void) 05. { 06. string info[10]; 07. 08. MathSrand(GetTickCount()); 09. 10. for (uint c = 0; c < info.Size(); c++) 11. info[c] = (string) MathRand(); 12. 13. Print("Array content before ordering..."); 14. ArrayPrint(info); 15. 16. ArraySort(info); 17. 18. Print("Array content after sorting..."); 19. ArrayPrint(info); 20. } 21. //+------------------------------------------------------------------+
コード02
なぜでしょうか。 まさにコンパイラが文字列データに対して適切な実装を見つけられないためです。 これは配列そのものの問題ではなく、ArraySort関数の問題です。この関数は、文字列を昇順にソートするようには実装も設計もされていません。 「ちょっと待ってください。 つまり、コード02の16行目を削除すれば、結果が得られるということでしょうか? コンパイラが実行可能なアプリケーションを生成できるからです。」はい、その通りです。 こうしてコード02を実行すると、次の図のような結果が表示されます。もちろん、コードから16行目を削除した後でのことです。

図02
さて、以下の点にご注意ください。 図02には文字列が表示されていますが、これらは昇順にソートされていません。 このソートをしてくれる仕組みがないからです。 ここで、次の点について考えてみましょう。数値が含まれている場合も含め、この文字列データをソートする方法を実装すれば、同じ仕組みを使ってファイルやディレクトリを特定の順序(昇順または降順)でソートできます。 まさにここで、プログラミング言語で実装できるソートの仕組みを学ぶ必要が出てきます。
この作業を簡単にし、誰もが理解できるように、一つずつ順を追って進めていきます。ここでの目標は、できるだけ学びの多い内容にし、初心者にもわかりやすい形で説明することだからです。 こうすれば、誰もがその流れを把握し、私たちが何をしているのかを正確に理解できるようになります。 似たようなことをする必要がある場合、単にコードをコピーするよりも、何が起きているのかを正確に理解することの方がはるかに重要です。 それでは、まず次のコードから見ていきましょう。
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. void OnStart(void) 05. { 06. uchar info[10]; 07. 08. MathSrand(512); 09. 10. for (uint c = 0; c < info.Size(); c++) 11. info[c] = (uchar) MathRand(); 12. 13. Print("Array content before ordering..."); 14. ArrayPrint(info); 15. 16. BubbleSort(info); 17. 18. Print("Array content after sorting..."); 19. ArrayPrint(info); 20. } 21. //+------------------------------------------------------------------+ 22. template <typename T> 23. void BubbleSort(T &arr[]) 24. { 25. #define macroSWAP(A, B) { \ 26. temp = arr[j - 1]; \ 27. arr[j - 1] = arr[j]; \ 28. arr[j] = temp; \ 29. } 30. 31. uint nElements = arr.Size(); 32. T temp; 33. 34. for (uint i = 1; i < nElements; i++) 35. for (uint j = nElements - 1; j >= i; j--) 36. if (typename(T) == "string") 37. { 38. }else 39. if (arr[j - 1] > arr[j]) 40. macroSWAP(arr[j - 1], arr[j]) 41. 42. #undef macroSWAP 43. } 44. //+------------------------------------------------------------------+
コード03
コード03を出発点とします。 ここでは、コード01で紹介した内容と非常によく似たことを行っている点に注目してください。 ただし、ここでは、以下の図に示されているのと同じ結果が得られるようにコードを設定しています。 これは、配列の初期化には引き続き疑似乱数生成器を使用しているものの、その疑似乱数生成器に特定のシード値を設定しているためです。 これは08行目で確認できます。
ここからは特によく注意してください。 コード01やコード02とは異なり、コード03の16行目では、実装したプロシージャを呼び出しています。 このプロシージャの目的は、配列内のデータを昇順にソートすることです。 それでは、いよいよ重要な部分に移りましょう。これまでの記事では、関数やプロシージャのテンプレートの作成方法について説明してきました。 また、このアプローチを実際にどのように活用できるかについても説明しました。 ここで示したコードは、これまでの記事で学んだ知識を活用した例です。 このように、ソートできる値の型に制限があるライブラリ関数ArraySortとは異なり、ここでの実装では、どの型の値でもソートできるようにしています。
これを実現するために、36行目のチェックを用いて、文字列をソートしているのか、それとも他の種類のデータをソートしているのかを判別しています。 現時点では、文字列データはソートしていません。 しかし、文字列以外のデータ型については、すでにソートできます。 これは、次の図に示された結果を見ればわかります。

図03
コードに実装されたメカニズムは、大規模な配列では非常に処理が遅いため、最善のものとは言えませんが、今回のデモには十分な速度であり、問題なく動作しています。 これは図03で確認できます。 「それだけですか?」はい、これだけです。 それでは、いよいよ最も興味深い部分、つまり文字列データのソートが可能になるようコードを修正する手順に進みましょう。 その前に、まずは小さな一歩を踏み出してみましょう。 これは、以下のコードに示されています。
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. void OnStart(void) 05. { 06. string info[10]; 07. 08. MathSrand(512); 09. 10. for (uint c = 0; c < info.Size(); c++) 11. info[c] = (string) (uchar) MathRand(); 12. 13. Print("Array content before ordering..."); 14. ArrayPrint(info); 15. 16. BubbleSort(info); 17. 18. Print("Array content after sorting..."); 19. ArrayPrint(info); 20. } 21. //+------------------------------------------------------------------+ 22. template <typename T> 23. void BubbleSort(T &arr[]) 24. { 25. #define macroSWAP(A, B) { \ 26. temp = arr[j - 1]; \ 27. arr[j - 1] = arr[j]; \ 28. arr[j] = temp; \ 29. } 30. 31. uint nElements = arr.Size(); 32. T temp; 33. 34. for (uint i = 1; i < nElements; i++) 35. for (uint j = nElements - 1; j >= i; j--) 36. if (typename(T) == "string") 37. { 38. }else 39. if (arr[j - 1] > arr[j]) 40. macroSWAP(arr[j - 1], arr[j]) 41. 42. #undef macroSWAP 43. } 44. //+------------------------------------------------------------------+
コード04
コード03とこのコード04の間で、具体的にどのような変更があったかをご確認ください。 これらの変更はすべて、どちらの場合でも同じ値が使用されるようにするためのものです。 とはいえ、文字列はまだソートしていません。 ただし、コード04を実行した結果は以下のとおりです。

図04
ここからはぜひ注意深くお読みください。 これからすることは、多くの読者にとって少々分かりにくく感じられるかもしれません。 数値のソートとは異なり、文字列のソートはそれほど単純な処理ではないからです。 ソートが正しく機能するためには、厳密に定められた方法でおこなう必要があります。 ただし、コード03とコード04を見ればわかるように、37行目と38行目の間に、ソート処理そのものを実装できる箇所があります。 このソートをどのようにおこなうべきかを理解するには、まず、特定の方法で実装するとどのような結果が得られるのかを理解していただく必要があります。 まずは、StringCompare関数を使ってみましょう。何と言っても、これが真っ先に思い浮かぶ選択肢です。 これには、以下のコードを使用します。
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. void OnStart(void) 05. { 06. string info[10]; 07. 08. MathSrand(512); 09. 10. for (uint c = 0; c < info.Size(); c++) 11. info[c] = (string) (uchar) MathRand(); 12. 13. Print("Array content before ordering..."); 14. ArrayPrint(info); 15. 16. BubbleSort(info); 17. 18. Print("Array content after sorting..."); 19. ArrayPrint(info); 20. } 21. //+------------------------------------------------------------------+ 22. template <typename T> 23. void BubbleSort(T &arr[]) 24. { 25. #define macroSWAP(A, B) { \ 26. temp = arr[j - 1]; \ 27. arr[j - 1] = arr[j]; \ 28. arr[j] = temp; \ 29. } 30. 31. uint nElements = arr.Size(); 32. T temp; 33. 34. for (uint i = 1; i < nElements; i++) 35. for (uint j = nElements - 1; j >= i; j--) 36. if (typename(T) == "string") 37. { 38. if (StringCompare(arr[j - 1], arr[j]) > 0) 39. macroSWAP(arr[j - 1], arr[j]) 40. }else 41. if (arr[j - 1] > arr[j]) 42. macroSWAP(arr[j - 1], arr[j]) 43. 44. #undef macroSWAP 45. } 46. //+------------------------------------------------------------------+
コード05
このコードを実行すると、次の図に示す結果が得られます。

図05
「一体、何なんですか、これは? どうやら、ここにはまったく順序の規則性がないようです。 とはいえ、一見したところ、要素は確かにソートされているように見えます。 よく見てみると、この並び方にはどこか奇妙な点があることに気づきます。」
おっしゃるとおりです。 このコードは、文字列配列に含まれる値をソートすることができます。 しかし、ここには奇妙な点があります。37と78は113より小さいのです。 ところが、この2つの値は並びの最後に配置されています。 なぜでしょうか。 その理由は、ソートでは文字列の内容のみが考慮されるということです。 したがって、113から189までのすべての値は正しい順序のままとなります。 しかし、文字列の文字数を考慮しないと、ソート自体は機能していても、その並び順はどこか奇妙に見えます。
興味深いことに、ここで扱っているような数値の代わりに辞書に載っている単語を使うと、ソートが実際に期待通りに機能することがわかります。 しかし、私たちがやっていること、あるいはやろうとしていることに対しては、このソートは100%完璧とはいえませんでした。 さて、この問題を解決するには、比較基準の一つとして、文字列の長さも考慮する必要があります。 これにより、バブルソートのルーチンで文字列配列を正しくソートできるようになります。 必要な変更点は、以下のコードに示されています。
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. void OnStart(void) 05. { 06. string info[10]; 07. 08. MathSrand(512); 09. 10. for (uint c = 0; c < info.Size(); c++) 11. info[c] = (string) (uchar) MathRand(); 12. 13. Print("Array content before ordering..."); 14. ArrayPrint(info); 15. 16. BubbleSort(info); 17. 18. Print("Array content after sorting..."); 19. ArrayPrint(info); 20. } 21. //+------------------------------------------------------------------+ 22. template <typename T> 23. void BubbleSort(T &arr[]) 24. { 25. #define macroSWAP(A, B) { \ 26. temp = arr[j - 1]; \ 27. arr[j - 1] = arr[j]; \ 28. arr[j] = temp; \ 29. } 30. 31. uint nElements = arr.Size(); 32. T temp; 33. 34. for (uint i = 1; i < nElements; i++) 35. for (uint j = nElements - 1; j >= i; j--) 36. if (typename(T) == "string") 37. { 38. if ((StringLen(arr[j - 1]) > StringLen(arr[j]))) 39. macroSWAP(arr[j - 1], arr[j]) 40. if ((StringCompare(arr[j - 1], arr[j]) > 0) && (StringLen(arr[j - 1]) == StringLen(arr[j]))) 41. macroSWAP(arr[j - 1], arr[j]) 42. }else 43. if (arr[j - 1] > arr[j]) 44. macroSWAP(arr[j - 1], arr[j]) 45. 46. #undef macroSWAP 47. } 48. //+------------------------------------------------------------------+
コード06
コード06を実行すると、次のような結果が得られます。

図06
「なるほど、本当に望んでいた通り、予想していた通りの結果が得られました。 ただ、いくつかわからない点があります。 先ほど、コード05は昇順にソートできる、より正確には、辞書に載っている単語を昇順にソートできるとおっしゃっていましたね。 しかし、図05から明らかなように、数値を正しくソートできませんでした。 でも、このコード06の修正版を使用することで、データを正しくソートできました。 コード06をこのように変更すると、辞書から取り出した単語を正しくソートできなくなるのではないでしょうか?」自らをプログラマーと考える人の多くは、おそらく「もちろん、そんなことはない」と答えるでしょう。 コードは変更されましたが、それでも単語を正しくソートできます。
しかし、コードに疑問を抱いている人が、プログラムは正しく動作しないかもしれないと考えるのも無理はありません。 こうした疑問に向き合い、コード構造に加えた変更が妥当かどうかを問い直すうちに、彼らは最終的に、いわば、あらゆるケースに対応できる解決策など存在しないことに気づきます。 また、ある段階では、内部でどのように動作するのかを知り、理解していることが、十分な結果と平凡な結果を分ける決定的な要因になり得ることにも気づきます。
それでは、簡単なテストをしてみましょう。コード06をもう一度修正して、この実装があらゆるケースで使えるかどうかを確認してみましょう。 これをおこなうには、次の例に示すように、コード06を修正するだけで済みます。
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. void OnStart(void) 05. { 06. string info[] = {"value", "data", "time", "assembly", "checking" }; 07. 08. Print("Array content before ordering..."); 09. ArrayPrint(info); 10. 11. BubbleSort(info); 12. 13. Print("Array content after sorting..."); 14. ArrayPrint(info); 15. } 16. //+------------------------------------------------------------------+ 17. template <typename T> 18. void BubbleSort(T &arr[]) 19. { 20. #define macroSWAP(A, B) { \ 21. temp = arr[j - 1]; \ 22. arr[j - 1] = arr[j]; \ 23. arr[j] = temp; \ 24. } 25. 26. uint nElements = arr.Size(); 27. T temp; 28. 29. for (uint i = 1; i < nElements; i++) 30. for (uint j = nElements - 1; j >= i; j--) 31. if (typename(T) == "string") 32. { 33. if ((StringLen(arr[j - 1]) > StringLen(arr[j]))) 34. macroSWAP(arr[j - 1], arr[j]) 35. if ((StringCompare(arr[j - 1], arr[j]) > 0) && (StringLen(arr[j - 1]) == StringLen(arr[j]))) 36. macroSWAP(arr[j - 1], arr[j]) 37. }else 38. if (arr[j - 1] > arr[j]) 39. macroSWAP(arr[j - 1], arr[j]) 40. 41. #undef macroSWAP 42. } 43. //+------------------------------------------------------------------+
コード07
これで、少し違うものになりました。 しかし、実際に異なるのは文字列配列の値だけです。 この場合、単語は昇順に並んでいるため、その並び順は確実にわかっています。 しかし、意外なことに、コード07を実行すると、次の図に示すような結果が得られます。

図07
図07に示された結果は、これらの単語が辞書に載る順序とは明らかに一致していません。 それでも、ここでのソートは、図05に結果を示したコード05の実行時とまったく同じ方法でおこなわれました。 だからこそ、アプリケーションが返す結果は常に完全に正しいとは限らず、かといって必ずしも間違っているわけでもないと理解することが重要なのです。 大事なことは、このアプリケーションにはどのような結果が期待されていたのかということです。 具体的な状況によっては、この結果が望ましい目標の達成に適している場合もあれば、そうでない場合もあります。 この場合は、適していません。 行き詰まってしまいました。
この場合、タスク(ここでは配列内のデータのソート)を実行するために作成されたプロシージャが返す結果は、私たちにとって納得できるものもあれば、そうでないものもあります。 コードにごくわずかな、ほとんど目立たない変更を加えることで、このプロセスをもう少し制御しやすくすることができます。 以下のコードには、この変更が反映されています。
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. void OnStart(void) 05. { 06. string info_01[10]; 07. string info_02[] = {"value", "data", "time", "assembly", "checking" }; 08. //+----------------+ 09. MathSrand(512); 10. 11. for (uint c = 0; c < info_01.Size(); c++) 12. info_01[c] = (string) (uchar) MathRand(); 13. //+----------------+ 14. Print("Number array before ordering..."); 15. ArrayPrint(info_01); 16. 17. BubbleSort(info_01, true); 18. 19. Print("Number array after ordering..."); 20. ArrayPrint(info_01); 21. //+----------------+ 22. Print("Dictionary before ordering..."); 23. ArrayPrint(info_02); 24. 25. BubbleSort(info_02); 26. 27. Print("Dictionary after sorting..."); 28. ArrayPrint(info_02); 29. } 30. //+------------------------------------------------------------------+ 31. template <typename T> 32. void BubbleSort(T &arr[], const bool bUsingLength = false) 33. { 34. #define macroSWAP(A, B) { \ 35. temp = arr[j - 1]; \ 36. arr[j - 1] = arr[j]; \ 37. arr[j] = temp; \ 38. } 39. 40. uint nElements = arr.Size(); 41. T temp; 42. 43. for (uint i = 1; i < nElements; i++) 44. for (uint j = nElements - 1; j >= i; j--) 45. if (typename(T) == "string") 46. { 47. if ((bUsingLength) && ((StringLen(arr[j - 1]) > StringLen(arr[j])))) 48. macroSWAP(arr[j - 1], arr[j]) 49. if ((StringCompare(arr[j - 1], arr[j]) > 0) && ((StringLen(arr[j - 1]) == StringLen(arr[j])) || !bUsingLength)) 50. macroSWAP(arr[j - 1], arr[j]) 51. }else 52. if (arr[j - 1] > arr[j]) 53. macroSWAP(arr[j - 1], arr[j]) 54. 55. #undef macroSWAP 56. } 57. //+------------------------------------------------------------------+
コード08
コード08を使えば、変更内容とその正しさを確認でき、文字列配列も期待どおりにソートできます。 MetaTrader 5 ターミナルでコード08 を実行してみるとどうなるか見てみましょう。 その結果、次のような図が得られます。

図08
完璧です。 数値文字列の配列も、辞書にある単語の配列も、正しくソートされていることを確認してください。 より正確には、期待どおりにソートされています。 以前は、これは不可能でした。 ここで重要なのは、このソートが期待通りの結果を出すために、具体的にどのような実装が必要だったかという点です。 必要だったのは、文字列データを処理するブロックに、チェックをもう1つ追加することだけでした。
ここで紹介したソート方法は理想的なモデルであり、どのような状況でも使えると思われるかもしれませんが、読者の皆さんには、その考えを見直していただきたいと思います。 このソート方法は、間違いなく、既存のあらゆるソート方法の中で最悪のものです。 そのコードは非常に理解しやすいものの、システム全体のパフォーマンスを急速に低下させてしまいます。 これは、ソート対象の配列の各要素について、ループを非常に多くの回数実行しなければならないためです。
より正確に言えば、このループが実行しなければならない反復回数は、最悪の場合、要素数の二乗に等しくなります。 つまり、5つの要素をソートするには、ループを25回実行する必要があります。 要素数が10個の場合、最初の例のわずか2倍であるにもかかわらず、ループの反復回数は100回に増えます。 配列に新しい要素が追加されるにつれて、ループの実行回数が急速に増加することにご注意ください。
このため、一部のプログラマーは、これまで説明してきた手法を「バブル地獄」と呼ぶことがよくあります。これは、新たに追加される要素ひとつひとつが、ソートを正常に完了させるために必要な反復回数を増やす可能性があるためです。
ここで紹介した初歩的で不完全な手法には問題があるものの、ソート済みの配列を出力するために、ループをそれほど何度も実行する必要がない場合もあります。 これは、配列を完全にソートするのに、交換をおこなう反復がわずか数回で済む場合があるためです。 信じがたいことかもしれませんが、コードにほんの少し手を加えるだけで、一見すると効果がないように思えるような変更であっても、この「バブル地獄」を、特定の状況下ではかなり許容できるものに変えることができるのです。
この変更がコードにどのような影響を与え、そして何よりも、どのように実行速度を向上させるのかを理解するには、読者の皆さんも、これまで説明してきた実装でソート処理がどのように行われるのかを理解する必要があります。
これを理解したら、次はコードの改善に取り掛かりましょう。 こうして、特定の状況でソートの処理速度を少し向上させたり、CPU負荷を軽減し、処理時間を短縮したりすることを目指します。
さて、これから実装しようとしているこの変更がコードの実行にどのような影響を与えるかを理解するためには、まず、ソートアルゴリズムの内部で何が起きているかを確認する方法を用意する必要があります。 そのために、コード08を次のコードに置き換えます。
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. void OnStart(void) 05. { 06. string info_01[10]; 07. string info_02[] = {"value", "data", "time", "assembly", "checking" }; 08. //+----------------+ 09. MathSrand(512); 10. 11. for (uint c = 0; c < info_01.Size(); c++) 12. info_01[c] = (string) (uchar) MathRand(); 13. //+----------------+ 14. Print("+----------------+\nNumber array before ordering..."); 15. ArrayPrint(info_01); 16. 17. BubbleSort(info_01, true); 18. 19. Print("Number array after ordering..."); 20. ArrayPrint(info_01); 21. //+----------------+ 22. Print("+----------------+\nDictionary before ordering..."); 23. ArrayPrint(info_02); 24. 25. BubbleSort(info_02); 26. 27. Print("Dictionary after sorting..."); 28. ArrayPrint(info_02); 29. } 30. //+------------------------------------------------------------------+ 31. template <typename T> 32. void BubbleSort(T &arr[], const bool bUsingLength = false) 33. { 34. #define macroSWAP(A, B) { \ 35. temp = arr[j - 1]; \ 36. arr[j - 1] = arr[j]; \ 37. arr[j] = temp; \ 38. } 39. 40. uint nElements = arr.Size(); 41. T temp; 42. uint count = 0; 43. 44. for (uint i = 1; i < nElements; i++) 45. { 46. for (uint j = nElements - 1; j >= i; j--, count++) 47. if (typename(T) == "string") 48. { 49. if ((bUsingLength) && ((StringLen(arr[j - 1]) > StringLen(arr[j])))) 50. macroSWAP(arr[j - 1], arr[j]) 51. if ((StringCompare(arr[j - 1], arr[j]) > 0) && ((StringLen(arr[j - 1]) == StringLen(arr[j])) || !bUsingLength)) 52. macroSWAP(arr[j - 1], arr[j]) 53. }else 54. if (arr[j - 1] > arr[j]) 55. macroSWAP(arr[j - 1], arr[j]) 56. } 57. 58. Print("Number of interactions: ", count); 59. 60. #undef macroSWAP 61. } 62. //+------------------------------------------------------------------+
コード09
コード09では、ソートルーチン内で行われた反復の回数を数える機能を追加しただけである点に注意してください。 これは、42行目を追加し、46行目で反復回数をカウントすることで実現されました。 最後に、58行目で結果を出力して、反復回数を確認します。 一点ご注意ください。この実装で行われる演算の回数は、nElementsの2乗にはなりません。 これは、44行目のループが1回反復されるたびに、46行目のループの反復回数が1回減るためです。 実行された反復回数として表示される値に惑わされないよう、この点を理解しておくことが非常に重要です。
では、このコードを実行してみましょう。次の図に示す結果が得られます。

図09
ここで特に注目したいのは、図09で強調表示されている箇所です。 一定回数の反復がおこなわれていることに注目してください。 さて、ここで問いたいのですが、これは良い結果でしょうか、それとも悪い結果でしょうか。 その質問に対する答えは、状況次第だということです。 ここで一つ注意すべき点があり、まさにそれが、これからお話ししたいことです。 ソート対象の値は、一見するとかなりばらばらに並んでいるように見えることに注目してください。 しかし、それらが目的のソート順にもっと近い並びになっていたら、どうでしょうか。 これにより、前回の結果と比べて反復回数は減るでしょうか。 では、実際に試して、どうなるか見てみましょう。 これには、次のコードを使用します。
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. void OnStart(void) 05. { 06. string info_01[] = {"37", "78", "0", "145", "113", "139", "148", "247", "174", "189"}; 07. string info_02[] = {"value", "data", "time", "assembly", "checking" }; 08. //+----------------+ 09. Print("+----------------+\nNumber array before ordering..."); 10. ArrayPrint(info_01); 11. 12. BubbleSort(info_01, true); 13. 14. Print("Number array after ordering..."); 15. ArrayPrint(info_01); 16. //+----------------+ 17. Print("+----------------+\nDictionary before ordering..."); 18. ArrayPrint(info_02); 19. 20. BubbleSort(info_02); 21. 22. Print("Dictionary after sorting..."); 23. ArrayPrint(info_02); 24. } 25. //+------------------------------------------------------------------+ 26. template <typename T> 27. void BubbleSort(T &arr[], const bool bUsingLength = false) 28. { 29. #define macroSWAP(A, B) { \ 30. temp = arr[j - 1]; \ 31. arr[j - 1] = arr[j]; \ 32. arr[j] = temp; \ 33. } 34. 35. uint nElements = arr.Size(); 36. T temp; 37. uint count = 0; 38. 39. for (uint i = 1; i < nElements; i++) 40. { 41. // interact = false; 42. for (uint j = nElements - 1; j >= i; j--, count++) 43. if (typename(T) == "string") 44. { 45. if ((bUsingLength) && ((StringLen(arr[j - 1]) > StringLen(arr[j])))) 46. macroSWAP(arr[j - 1], arr[j]) 47. if ((StringCompare(arr[j - 1], arr[j]) > 0) && ((StringLen(arr[j - 1]) == StringLen(arr[j])) || !bUsingLength)) 48. macroSWAP(arr[j - 1], arr[j]) 49. }else 50. if (arr[j - 1] > arr[j]) 51. macroSWAP(arr[j - 1], arr[j]) 52. } 53. 54. Print("Number of interactions: ", count); 55. 56. #undef macroSWAP 57. } 58. //+------------------------------------------------------------------+
コード10
コード10の6行目では、図09に示されたのと同じ値を定義していることに注意してください。 いわば、値の並びの乱れが少し小さくなっているのです。 一見すると、これによりソート処理が高速化されるか、あるいは完了までに必要な反復回数が減るように思えるかもしれません。 しかし、意外なことに、コード10を実行すると、結果は次の図のようになります。

図10
つまり、コード10の06行目にある配列は、ソートに必要な反復回数が少なくて済みそうに見えますが、実際には同じ回数の反復を実行しています。 多くの人にとっては奇妙に思えるかもしれませんが、それなら、コード10の何が問題で、反復回数を減らせないのでしょうか。 実のところ、そのコードは問題ありません。 あとは、配列がソート済みかどうかを判定する処理を追加するだけです。
なるほど、でもこのチェックはちょっと複雑そうですね。配列がソートされているかどうかを確認するには、実際に配列をチェックしなければならないからです。 これには時間がかかり、追加の反復が必要になります。 これは望ましくありません。私たちの目標は、まさに反復回数を減らすことだからです。 では、どうすればこの問題を解決できるのでしょうか。 私の考えでは、この部分が最も興味深いのです。というのも、この問題を解決するために必要なのは、コードにほんの少し手を加えることだけだからです。 それでは、次のコードにどのような変更を加える必要があるか見てみましょう。
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. void OnStart(void) 05. { 06. string info_01[] = {"37", "78", "0", "145", "113", "139", "148", "247", "174", "189"}; 07. string info_02[] = {"value", "data", "time", "assembly", "checking" }; 08. //+----------------+ 09. Print("+----------------+\nNumber array before ordering..."); 10. ArrayPrint(info_01); 11. 12. BubbleSort(info_01, true); 13. 14. Print("Number array after ordering..."); 15. ArrayPrint(info_01); 16. //+----------------+ 17. Print("+----------------+\nDictionary before ordering..."); 18. ArrayPrint(info_02); 19. 20. BubbleSort(info_02); 21. 22. Print("Dictionary after sorting..."); 23. ArrayPrint(info_02); 24. } 25. //+------------------------------------------------------------------+ 26. template <typename T> 27. void BubbleSort(T &arr[], const bool bUsingLength = false) 28. { 29. #define macroSWAP(A, B) { \ 30. temp = arr[j - 1]; \ 31. arr[j - 1] = arr[j]; \ 32. arr[j] = temp; \ 33. interact = true; \ 34. } 35. 36. uint nElements = arr.Size(); 37. T temp; 38. bool interact = true; 39. uint count = 0; 40. 41. for (uint i = 1; (i < nElements) && interact; i++) 42. { 43. interact = false; 44. for (uint j = nElements - 1; j >= i; j--, count++) 45. if (typename(T) == "string") 46. { 47. if ((bUsingLength) && ((StringLen(arr[j - 1]) > StringLen(arr[j])))) 48. macroSWAP(arr[j - 1], arr[j]) 49. if ((StringCompare(arr[j - 1], arr[j]) > 0) && ((StringLen(arr[j - 1]) == StringLen(arr[j])) || !bUsingLength)) 50. macroSWAP(arr[j - 1], arr[j]) 51. }else 52. if (arr[j - 1] > arr[j]) 53. macroSWAP(arr[j - 1], arr[j]) 54. } 55. 56. Print("Number of interactions: ", count); 57. 58. #undef macroSWAP 59. } 60. //+------------------------------------------------------------------+
コード11
コード11を実行すると、次のような結果が得られます。

図11
図11では、コード自体に大きな変更を加えることなく、反復回数が減っていることに注目してください。 38行目を追加し、コードのいくつかの部分を修正するだけで済みました。 たとえば、41行目のループやマクロなどです。 なお、コード自体が、配列内で交換が行われたかどうかを確認します。 44行目のループが実行され、かつどの反復でも33行目が実行されなかった場合、その配列はすでに適切にソートされていると断言できます。 したがって、41行目のループの次の反復では、ソートのプロシージャを終了できます。 面白いですよね。
最後に
この記事では、あらゆる配列をソートするために設計された、非常にシンプルでわかりやすい仕組みについて解説しました。 また、得られる結果が、実際に期待するものと必ずしも一致しないことも示しました。 したがって、正しい結果が得られるよう、実装を調整する必要があります。
また、ほんの少しの工夫を加えるだけで、当初は動作が遅かった実装をより柔軟なものに変えることができることも実証しました。 つまり、状況によっては、特定の配列をより高速に処理できるようになるということです。 ほんの少し調整するだけで、期待通りの結果がすでに得られている可能性もあります。 それ以上反復しても得られた結果は変わらないため、さらなる反復は不要になります。
ここで取り上げられている内容のほとんどは、教育目的でおこなわれた変更であるため、添付資料にはコードの最終版のみを含めます。 したがって、なぜ特定のアプローチが選ばれたのかを理解したい場合は、この記事に全文掲載されているコード例を参照してください。 あとは、ここで示した仕組みがどのように動作するかを理解するために、これまでに取り上げた内容を学び、実践するだけです。
| ファイル | 説明 |
|---|---|
| コード01 | 簡単なソートの実演 |
| コード02 | 簡単なソートの実演 |
| コード03 | 簡単なソートの実演 |
MetaQuotes Ltdによりポルトガル語から翻訳されました。
元の記事: https://www.mql5.com/pt/articles/16418
警告: これらの資料についてのすべての権利はMetaQuotes Ltd.が保有しています。これらの資料の全部または一部の複製や再プリントは禁じられています。
この記事はサイトのユーザーによって執筆されたものであり、著者の個人的な見解を反映しています。MetaQuotes Ltdは、提示された情報の正確性や、記載されているソリューション、戦略、または推奨事項の使用によって生じたいかなる結果についても責任を負いません。