スクリプトアルゴリズム、意識してますか?(挨拶)このブログではWikipediaに載っていた交換ソートを片っ端からC#で実装しました。各記事内では配列が並び変わることを確認するに止まり、性能比較までは行なっていなかったので、ここで一気に比較をしてみたいと思います。i7アルゴリズムって?アルゴリズムとは何かという話は別記事で書いたのでそちらをご覧くださいな。時に読む記事【初心者向け】https://ekulabo.com/whats-algorithm初心者のうちからアルゴリズムを理解し、処理時間を意識していくと、超イケてるプログラミングが可能になります。慣れてる人は多分無意識のうちにやっていることなんですよね。性能比較への参加アルゴリズム今回の性能比較大会にエントリーしているアルゴリズムは以下の6種類です。全て交換ソートとなっています。バブルソートアルゴリズムを学び始める人がまず最初に触れるであろうソートアルゴリズムがバブルソートです。最悪計算時間は\(O(n^2)\)、平均計算時間も\(O(n^2)\)と、あくまで学習用のアルゴリズムとなっています。交換ソートのアルゴリズム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交換ソートのひとつである奇偶転置ソートは、比較・交換を行うペアを独立させられるため、並列処理に向いたソート方法です(重要)コムソートやっぱりバブルソートの改良型のアルゴリズムです。離れた要素同士の比較・交換を行なってから隣同士の要素の比較・交換に移るため、バブルソートより交換回数が少なくて済みます。n)\)程度なのでこれまでのアルゴリズムより速いかも。エクスプラボ【Unity/C#】コムソートのアルゴリズムを実装!(コムは櫛)https://ekulabo.com/algorithm-comb-sort交換ソートのひとつであるコムソートは、実装が単純なのに速度が出る素敵ソート。ポイントは伸縮率の1.3という数字です。ノームソート名前がファンタジーなアルゴリズム。挿入ソートに似たアルゴリズムで、要素の移動が交換によって行われます。最悪計算時間は\(O(n^2)\)ですが、実験的には挿入ソートと同じくらいの速度だそうで、これまた期待できそう。エクスプラボ【Unity/C#】精霊が並び替えるノームソートのアルゴリズムを実装!https://ekulabo.com/algorithm-gnome-sort交換ソートのひとつであるノームソート。名前がファンタジーなのでお気に入りのアルゴリズムです。クイックソート分割統治法によって高速化を実現した交換ソートのアルゴリズムです。n)\)なので理論的には上記のアルゴリズムより速いです。結果は......!?エクスプラボ【Unity/C#】最速と噂のクイックソートのアルゴリズムを実装!https://ekulabo.com/algorithm-quick-sort交換ソートのひとつであるクイックソートは、ソートするならクイックソートで、と言われるくらいには速いソート方法です。バブルとクイックは押さえておきたいところ。性能比較のルールエディタ拡張を使って、内容をランダムに生成しておいた配列をScriptableObjectに保存しておきます。各アルゴリズムのスクリプトにおいてこのScriptableObjectに保存された配列をコピーし、コピーされた方の配列をソートします。この時の処理時間を計測して性能を確かめます。生成する配列の長さは100、1000、10000、100000の4種類で、それぞれの処理時間を計測・比較します。各ソート方法で5回計測し、平均値を使って比較を行います。スクリプトの中では、ゲーム開始時の他のスクリプトの処理を避けるため、30フレームごとに要素数100、1000、10000、100000の処理を行なっていきます。ソースコードソースコードはGitHubに載せてあるので、興味のある方はそちらをご覧ください。性能比較を行なった結果は以下の表の通りです。単位はミリ秒(ms)です。25.4986要素数100での最速はコムソート、最遅はクイックソートでした。クイックソート以外は誤差範囲と言えそうですが、ここだけクイックソートが遅いんですよね。(クイックソート)要素数1000での最速はクイックソート、最遅はバブルソートです。n)\)の強みが出ています。n)\)なので、似たぐらいの速度が出ています。(バブルソート)要素数10000での最速はクイックソート、最遅はバブルソートです。コムソートもなかなか早いですね。この辺りから100倍ほどの差が出てきました。(バブルソート)要素数100000での最速はクイックソート、最遅はバブルソートです。ここまでくると圧倒的な差です。クイックソートは30FPSなら1フレームに収まる驚異的な処理時間です。n)\)のアルゴリズムではある程度時間がかかってしまいます。n)\)のアルゴリズムの方が速くなるため、要素数が大きくなりそうならクイックソートを選択するのがベストです。要素数の見積もりが難しそうなら、コムソートを使っておけば安定して合格点の速度が得られるかもしれません。要素数に応じてソートアルゴリズムを切り替える、というのは、実はUnityが使っているC#のArray.Sort()がやっていることなんです。分割した配列の大きさが16より小さければ挿入ソート、分割した配列の数が元の要素数の対数より大きければヒープソート、それ以外はクイックソートでソートするようになっています。次元配列の要素を並べ替えます。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#で実装し、性能比較として処理時間の比較を行いました。バブルソートから勉強していって、クイックソートまでたどり着くと、処理時間が短くなっていく様子が分かって楽しいですね。オススメの学習順はバブル、シェーカー、コム、クイックです。オーダーの違いが顕著に現れるのも実感していけます。ゲーム開発の攻略チャートを作りました!「ゲームを作ってみたいけど、何から手を付けていいか分からない!」そんなお悩みをお持ちの方向けに、todoがアプリをリリースした経験を中心に、ゲーム作りの手順や考慮すべき点をまとめたe-bookを作成しました。ゲーム作りはそれ自体がゲームのように楽しいプロセスなので、「攻略チャート」と名付けています。投稿一覧Unityを使ってアプリを作ったり、Assetを作ったりしてる個人開発者。Unity全般ネタとAsset開発の情報を扱っています。Asset開発は日本語の情報が少ないのよね。ことで些細なネタでも情報を蓄積するのが目的です。2019.08.23バブルソートについての説明とC#による実装を紹介しています。一度は触れるアルゴリズムよね。2019.08.30ソートアルゴリズムの一種であるヒープソートは、ヒープの性質、法則性が分かると簡単に実装できます。実行も速いのでぜひ挑戦してみてね。2019.08.22初心者のうちからアルゴリズムを理解し、処理時間を意識していくと、超イケてるプログラミングが可能になります。2019.08.28交換ソートのひとつであるクイックソートは、ソートするならクイックソートで、と言われるくらいには速いソート方法です。コメントをキャンセルメールアドレスが公開されることはありません。コメントデータの処理方法の詳細はこちらをご覧ください。todoUnityのアセットを作ったり、スマホ向けのアプリを作っています。このブログではUnity初心者に向けたチュートリアルやテクニックを放出しています。詳しいプロフィールはこちら。お仕事の相談や現在提供中のサービスについては、こちらの『サービス内容』のページをご覧ください。Explorers_todoオンライントレーニングのサイトをオープン!エクスプラボを運営しているtodoが、より集中的にゲーム作りについて学べるオンライントレーニングのサイトをオープンしました。エクスプラボのトレーニングルーム』です。勉強したことの進捗も表示できるようになっているので、どれだけ頑張ったのかが分かるようになっています。ゲーム開発の攻略チャート』というe-bookをプレゼントしています。メルマガではゲーム開発のテクニックを中心に役立つ情報をお届けします。詳しくはこちら!お仕事の依頼はこちら!ゲーム開発のサポートも可能!エクスプラボではゲーム開発のサポートのサービスも行なっています。いう場合にオススメのプランです。普通に開発依頼をいただいてもOKです。【Unity】ポストプロセシングを使って簡単にプロっぽいゲーム画面を作るゲームの作り方を学べるオンライン講座のサイトをオープンしました!【ゲーム開発】ゲーム開発者こそ体を動かしてアイディアを出すべきRANKING【Unity】Mathfの切り上げ、切り捨て、偶数丸め。使い分けが大事よねMathf【Unity】ゲームといえばランダム要素。(12)作ったアプリ空とにゃんこと風船と癒し系縦スクロール避けゲーの『空とにゃんこと風船と』(TODOWORKS名義でリリース)気軽に遊べるスマートフォン向けアプリです。ボクセルアートで彩られるどこかレトロ、でも新しい世界で癒されてみませんか?ぼく、猫ですって!タップ系RPG『ぼく、猫ですって!』(TODOWORKS名義でリリース)気軽に遊べるスマホRPG。