【Unity/C#】交換ソートのアルゴリズムを性能比較するのだ

アルゴリズム、意識してますか？(挨拶)

このブログではWikipediaに載っていた交換ソートを片っ端からC#で実装しました。

各記事内では配列が並び変わることを確認するに止まり、性能比較までは行なっていなかったので、ここで一気に比較をしてみたいと思います。

環境

macOS 10.14 Mojave

Unity2018.3.14f1

Unity Hub 2.1.0

MacBook Pro (15-inch, 2016)

プロセッサ　2.9 GHz Intel Core i7

アルゴリズムって？

アルゴリズムとは何かという話は別記事で書いたのでそちらをご覧くださいな。

エクスプラボ

アルゴリズムってなんやいね？　って時に読む記事【初心者向け】

https://ekulabo.com/whats-algorithm

初心者のうちからアルゴリズムを理解し、処理時間を意識していくと、超イケてるプログラミングが可能になります。慣れてる人は多分無意識のうちにやっていることなんですよね。

性能比較への参加アルゴリズム

今回の性能比較大会にエントリーしているアルゴリズムは以下の6種類です。

全て交換ソートとなっています。

バブルソート

アルゴリズムを学び始める人がまず最初に触れるであろうソートアルゴリズムがバブルソートです。

最悪計算時間は\(O(n^2)\)、平均計算時間も\(O(n^2)\)と、あくまで学習用のアルゴリズムとなっています。

エクスプラボ

【Unity/C#】バブルソートをC#で！　交換ソートのアルゴリズム

https://ekulabo.com/algorithm-bubble-sort

バブルソートについての説明とC#による実装を紹介しています。一度は触れるアルゴリズムよね。

シェーカーソート

バブルソートを改良し、前方からと後方からの比較・交換ができるようになったアルゴリズムです。

最悪計算時間は\(O(n^2)\)、平均計算時間も\(O(n^2)\)と、オーダーはバブルソートと一緒ですが、前方と後方の両方で値が確定していくので、バブルソートより多少速くなるはず。

エクスプラボ

【Unity/C#】シェーカーソートのアルゴリズムをC#で実装！

https://ekulabo.com/algorithm-shaker-sort

シェーカーソートについての説明とC#による実装を紹介しています。バブルソートの改良型としてこれも有名。

奇偶転置ソート

これもバブルソートの改良型で、奇数番目の要素から始まるペアでの比較・交換、偶数番目の要素から始まるペアでの比較・交換を交互に行うアルゴリズムです。

最悪計算時間は\(O(n^2)\)でバブルソートと同じですが、ポイントはペアごとに比較・交換を行うため、並列処理が可能なこと。Unityでその強みを発揮できれば速さに期待できそう。

エクスプラボ

【Unity/C#】名前がかっこいい奇偶転置ソートのアルゴリズムを実装

https://ekulabo.com/algorithm-odd-even-sort

交換ソートのひとつである奇偶転置ソートは、比較・交換を行うペアを独立させられるため、並列処理に向いたソート方法です(重要)

コムソート

やっぱりバブルソートの改良型のアルゴリズムです。離れた要素同士の比較・交換を行なってから隣同士の要素の比較・交換に移るため、バブルソートより交換回数が少なくて済みます。

最悪計算時間は\(O(n^2)\)、平均計算時間は実験的に\(O(n\log n)\)程度なのでこれまでのアルゴリズムより速いかも。

エクスプラボ

【Unity/C#】コムソートのアルゴリズムを実装！(コムは櫛)

https://ekulabo.com/algorithm-comb-sort

交換ソートのひとつであるコムソートは、実装が単純なのに速度が出る素敵ソート。ポイントは伸縮率の1.3という数字です。

ノームソート

名前がファンタジーなアルゴリズム。挿入ソートに似たアルゴリズムで、要素の移動が交換によって行われます。

最悪計算時間は\(O(n^2)\)ですが、実験的には挿入ソートと同じくらいの速度だそうで、これまた期待できそう。

エクスプラボ

【Unity/C#】精霊が並び替えるノームソートのアルゴリズムを実装！

https://ekulabo.com/algorithm-gnome-sort

交換ソートのひとつであるノームソート。名前がファンタジーなのでお気に入りのアルゴリズムです。

クイックソート

分割統治法によって高速化を実現した交換ソートのアルゴリズムです。名前からして速そう。

最悪計算時間は\(O(n^2)\)ですが、平均計算時間は\(O(n\log n)\)なので理論的には上記のアルゴリズムより速いです。果たして結果は……！？

エクスプラボ

 

1 User

【Unity/C#】最速と噂のクイックソートのアルゴリズムを実装！

https://ekulabo.com/algorithm-quick-sort

交換ソートのひとつであるクイックソートは、ソートするならクイックソートで、と言われるくらいには速いソート方法です。バブルとクイックは押さえておきたいところ。

性能比較のルール

エディタ拡張を使って、内容をランダムに生成しておいた配列をScriptableObjectに保存しておきます。

各アルゴリズムのスクリプトにおいてこのScriptableObjectに保存された配列をコピーし、コピーされた方の配列をソートします。この時の処理時間を計測して性能を確かめます。

生成する配列の長さは100、1000、10000、100000の4種類で、それぞれの処理時間を計測・比較します。各ソート方法で5回計測し、平均値を使って比較を行います。

スクリプトの中では、ゲーム開始時の他のスクリプトの処理を避けるため、30フレームごとに要素数100、1000、10000、100000の処理を行なっていきます。

ソースコード

ソースコードはGitHubに載せてあるので、興味のある方はそちらをご覧ください。

GitHub

todorok1/AlgorithmPerformanceCheck

https://github.com/todorok1/AlgorithmPerformanceCheck

交換ソートのアルゴリズムをC#で実装し、性能比較を行った. Contribute to todorok1/AlgorithmPerformanceCheck development by creating an account on GitHub.

性能比較の結果

性能比較を行なった結果は以下の表の通りです。単位はミリ秒(ms)です。

要素数100での最速はコムソート、最遅はクイックソートでした。クイックソート以外は誤差範囲と言えそうですが、ここだけクイックソートが遅いんですよね。

順位は以下の通り。

(コムソート) >= (バブルソート) = (シェーカーソート) = (奇偶転置ソート) = (ノームソート) > (クイックソート)

要素数1000での最速はクイックソート、最遅はバブルソートです。この辺りから平均計算時間\(O(n\log n)\)の強みが出ています。コムソートも平均計算時間は実験的に\(O(n\log n)\)なので、似たぐらいの速度が出ています。

順位は以下の通り。

(クイックソート) > (コムソート) >> (シェーカーソート) > (奇偶転置ソート) = (ノームソート) >> (バブルソート)

要素数10000での最速はクイックソート、最遅はバブルソートです。コムソートもなかなか早いですね。この辺りから100倍ほどの差が出てきました。

順位は以下の通り。

(クイックソート) > (コムソート) >> (シェーカーソート) > (奇偶転置ソート) = (ノームソート) >> (バブルソート)

要素数100000での最速はクイックソート、最遅はバブルソートです。ここまでくると圧倒的な差です。クイックソートは30FPSなら1フレームに収まる驚異的な処理時間です。

順位は以下の通り。

(クイックソート) > (コムソート) >>(超えられない壁)>> (シェーカーソート) > (ノームソート) > (奇偶転置ソート) >> (バブルソート)

結果の総評

要素数が少なければ\(O(n^2)\)でも大差がなく、むしろ\(O(n\log n)\)のアルゴリズムではある程度時間がかかってしまいます。

要素数が1000を超える頃には\(O(n\log n)\)のアルゴリズムの方が速くなるため、要素数が大きくなりそうならクイックソートを選択するのがベストです。

要素数の見積もりが難しそうなら、コムソートを使っておけば安定して合格点の速度が得られるかもしれません。

要素数に応じてソートアルゴリズムを切り替える、というのは、実はUnityが使っているC#のArray.Sort()がやっていることなんです。分割した配列の大きさが16より小さければ挿入ソート、分割した配列の数が元の要素数の対数より大きければヒープソート、それ以外はクイックソートでソートするようになっています。

docs.microsoft.com

Array.Sort Method (System)

https://docs.microsoft.com/ja-jp/dotnet/api/system.array.sort?view=netframework-4.8#System_Array_Sort_System_Array_

1 次元配列の要素を並べ替えます。Sorts the elements in a one-dimensional array.

今回の性能比較の結果からも分かるように、クイックソートは要素数が少ない時にはあまり速度が出ないので、その部分を挿入ソートで処理することで速度を出しているんですね。

ソートアルゴリズムを組み合わせて使うのは有効な手段なので、自力でソートを実装する場合はこれも考えてみると良いと思います。

おまけ・結果の個別評価

総評が終わったので、あとは個別の結果について所見を述べます。

バブルソート

バブルソート単体の実験結果は以下の通りです。

実行する度に揺らいでしまうので平均を取っておいて良かったです。

注目したいのは要素数100000の交換回数。intの範囲を超えてまさかの25億回。隣り合う要素同士で交換を行うのでどうしても回数が増えてしまいますね。

要素数100000で1分ほど処理を行なっているときは(応答なし)の状態だったのでかなり不安でした。要素数が大きい場合は実用に向かないので、やはり学習用のアルゴリズムという位置付けでしょうか。

ここから学び始めて、どんどん速く処理できるアルゴリズムを知っていくのはRPGで強くなっていく感覚に似ているかもしれません。

シェーカーソート

シェーカーソート単体の実験結果は以下の通りです。

交換回数はバブルソートと同じですが、配列の前と後ろでどんどん値が確定していくのでその分速くなっています。

要素数100000の場合、平均値で見るとバブルソートより12000ms(12秒)も早いですね。正直なところ、次の奇偶転置ソートの方が速くなると思っていましたが、こちらの方が早かったです。意外。

奇偶転置ソート

奇偶転置ソート単体の実験結果は以下の通りです。

こちらも交換回数はバブルソートと同じでした。

要素数100000の場合、平均値で見るとバブルソートより6000ms(6秒)早いです。これが並列処理による結果なのかは今回の実験では特定できませんが、バブルソートより速くなっていることは事実です。

名前のかっこよさだけで終わらなくて良かったです。

コムソート

コムソート単体の実験結果は以下の通りです。

要素数100の時点から安定して速くなっています。交換回数も上3つのソート方法より少なくなっているのに注目です。

離れた要素を交換していることから、配列の奥にある小さな値を手前に持ってくるのが簡単になっている影響ですね。

要素数100000の場合、平均値で見るとバブルソートより62500ms(62.5秒)も早いです。文字通りレベルが違いますね。

ノームソート

ノームソート単体の実験結果は以下の通りです。

全体的に奇偶転置ソートと同等かちょっと速いくらいでした。交換回数はバブルソート一族と一緒です。隣接要素の比較だからここはしょうがないところ。

要素数100000の場合、平均値で見るとバブルソートより7000ms(7秒)も早いです。

クイックソート

クイックソート単体の実験結果は以下の通りです。

はやい(確信)

要素数100ではまさかの最下位でしたが、それより大きな範囲では安定して最速でした。さすがクイック。

要素数100000の場合、平均値で見るとバブルソートより62500ms(62.5秒)も早いです。バブルソートと比べてしまうと、コムソートの結果とクイックソートの結果は完全に誤差の範囲内ですね。

30FPSだったら1フレーム(33ms)以内に処理が終わっているので、ギリ処理落ちしない程度に収まります。

「とりあえずクイックソートを使っておけ」と言われるも理解できます。

まとめ

交換ソートのアルゴリズムをC#で実装し、性能比較として処理時間の比較を行いました。

バブルソートから勉強していって、クイックソートまでたどり着くと、処理時間が短くなっていく様子が分かって楽しいですね。

オススメの学習順はバブル、シェーカー、コム、クイックです。オーダーの違いが顕著に現れるのも実感していけます。他2つは趣味で。