C#の安定ソートを検討

 C#, Unity  コメントを追加
9月 032017
 

Unityでゲームプログラムを書いていると、C#で気軽に使える安定ソートが欲しくなるのですが、これという機能が標準で用意されていません。

今更ソートなんて自前で実装したくないんですが、欲しいものがなければ作るしかない。実装までに検討した色々なことをこの記事ではまとめていきます。

実装したものは別の記事にまとめたので、そちらをどうぞ。

アルゴリズム系の実装コードって何故かほとんど可読性が低いですよね。主に変数名がやっつけすぎて理解に時間がかかります。バグの温床だと思うので、そのへんも私なりに読みやすくしています。

その点、これからいくらか紹介する.NETやMonoの実装はとても綺麗で理解しやすいです。

定義

本記事における言葉の定義をします。

安定ソート

安定ソート（stable sort）とは、同値とみなされた要素の元の順序がソート後にも保証されているソートのことを言います。ゲームプログラムを書いていると、アイテムリストのソートとか実装したいときにほぼ間違いなく安定ソートが望まれるので、みんな何かしら対応しているはずです。

不安定なソートアルゴリズムであっても、ソート前のリストにあらかじめインデックスを割り振っておけるなら、比較関数でインデックスも考慮するようにすれば安定ソートが実現できます。

しかし、インデックス追加するみたいなデータ拡張なしに使いたいのです。ゲームプログラムではGCによるストップが快適性を損なうので、GCを引き起こす元となるアロケートは無駄に発生させたくないです。アロケートを徹底的に排除するほどカリカリチューンした経験は私にはないですが、やろうと思ったときにできるよう選択肢はほしいなと思うこの頃。

内部ソート（In-place）

追加の記憶領域を必要としないアルゴリズムをIn-place（インプレース）と呼び、In-placeなソートを内部ソートと呼びます。

厳密な話をするとややこしいのですが、私の関心事はアロケーションを抑えることにあるので、ここでいうIn-Placeとは「ヒープ領域を追加で必要としないこと」ということにします。他にいい言葉がないです。基本的には参照型のnew撲滅です。

例えば、クイックソートは、再帰処理による実装の場合、追加データがすべてスタック領域に乗るので、私の定義では内部ソートです。スタックオーバーフローを嫌って、非再帰処理による実装をすると、スタック構造のデータをアロケートすることになるので、内部ソートではなくなります。このように実装次第で変わったりもします。

そういうわけでIn-placeで高速な安定ソートが存在したら最高なんですが、結論から言えば、そんな都合のいいものはなかなかないようです。検討したことを順に説明していきます。

標準機能の限界

Array.Sort()

C#のソートといえば、Array.Sort()とList<T>.Sort()です。Listの内部表現は配列（Array）なので、これらは実質同じです。

リファレンスを見ると、アルゴリズムの説明がありますが、内容的にどうやら.NETでの実装はイントロソート（後述）のようです。

興味があれば、ソースコードも見てみるといいと思います。自前で用意するときも参考になります。

UnityのMono実装は基本的に純粋なクイックソートのようですね（条件次第ではコムソートに置き換え）。

いずれにせよ、In-placeであることは一貫しています。

さて、Array.Sort()はさすが標準ライブラリだけあってとても高速ですが、下記の前提によります。

  • 配列構造
  • 安定ソートでない

用途次第では、この前提が都合悪いため、別の選択肢が欲しいわけです。私としては、

  • In-placeな安定ソートが欲しい
  • LinkedList（連結リスト）のソートが欲しい

といった動機があります。

LinqのOrderBy

C#に安定ソートがないかといえば、Linqで実現できます。

ソート系のLinq拡張メソッドとして、OrderBy、OrderByDescendingがあります。あと一緒に使うThenBy、ThenByDescending。

じゃあLinqでいいじゃん、と思うかもしれませんが、Linqはあくまで遅延実行されるIEnumerableオブジェクトを生成するものです。生成されたIEnumerableオブジェクトをforeachなどで利用する時に初めて目的の処理が実行されます。処理結果は使い捨てる前提です。

LinqによるソートはIn-placeではないし、結果がListでほしいならToList()する必要があります。あまりに汎用化し過ぎていて、冗長です。

実装を見てみた感じ、ざっとこんな処理です。

  1. IEnumerableなソート対象を受け取って、順に配列に格納。これはインデックスから値にランダムアクセスするためのバッファ。（ICollectionに対してはCountをバッファサイズに利用する最適化あり。ICollection以外は事前にサイズがわからないため、4から始めて2のべき乗サイズで収まるまで適宜リサイズ）
  2. バッファと同じサイズのint配列を作成し、インクリメントでインデックスを設定。これはマップとして機能し、インデックスをバッファに適用すると値が得られる。
  3. バッファから得られる値で比較して、マップをクイックソートする。同値判定のときは、インデックスで比較することで安定ソートを保証。
  4. ソート済みマップをなめながら、バッファを参照することで、安定ソートされた値が順に得られる。

中身見る前はArray.Sort()使ってるのかと思ってましたが、普通にクイックソートを専用に実装しています。また、Unityの方は、部分リストの要素数が3以下のとき挿入ソートに切り替える最適化が入っていますので、純粋なクイックソートではないです。

ともかくLinqの処理で注目すべきは、インデックスでアクセスするためのバッファと、安定ソートを保証するためのインデックスを管理するマップを生成する必要があるということです。それぞれ要素数分のサイズを要求しますので、オーダーにすると要素数Nに対してO(N)サイズですね。

安定ソートでなくても、「ソート前のリストにあらかじめインデックスを割り振っておけるなら安定ソートにできる」という話を先にしましたが、これを内部で勝手にやってくれるのがLinqのOrderByということです。ただ、汎用処理なので一度バッファに詰め込むというオーバーヘッドが生じますし、このバッファを直接取得する方法もないです。

私がソートしたいのはListとLinkedListであって、それぞれListとLinkedListで結果を得たいのです。ついでに言えば、In-placeであってほしいのです。だから、今回はLinqという選択肢はありえません。ゲームプログラムでLinqはちょっと気軽に使えませんね。

アルゴリズムの選定

動機は明らかにしたので、実装するアルゴリズムを選びましょうか。

基本的なアルゴリズムの比較表がWikipediaにまとまっていて便利です。

選定基準を定義しますと、

  • 安定ソート
  • 高速（平均計算時間が短い）
  • 内部ソート（In-place）
  • ランダムアクセスを要求しない（LinkedListにも使いたいので）

処理速度は平均O(n^2)だと平凡なバブルソート相当なので、これよりはずっと速くあってほしいです。

これら条件を満たすのはマージソートぐらいになります。処理速度が平均O(n log n)、最悪O(n log n)という優秀なソートです。

マージソートのアルゴリズムまで説明する気はないので、アルゴリズムが知りたい人はWikipediaへ。

但し、マージソートの一般的な実装方法はIn-placeではありません。結局のところ、部分リストのマージの際に挿入操作が必要となるため、配列に対する挿入をIn-placeでやろうとしたら大量のswap操作を伴い、速度低下を招きます。

それよりかは、前方部分リストを一時記憶領域に退避して、そこから順に詰めていく方が速いようです。最終的には全体のマージとなるので、一時記憶領域は全体の要素数と同じサイズを要します。つまり、O(N)サイズ。

上記のサイトでIn-placeなマージソートの実装を試みていますが、良い速度は出なかったそうです。

仕方ないので、Listについては内部ソートを諦めます。一方、LinkedListに関しては、挿入は問題とならないので内部ソートが実現可能です。

ソートの改良を考える

まだマージソートを実装してませんが、改良方法を考えます。

割と仰々しいソートなので、要素数が少ないときには、ちょっと複雑な計算をしている分、他のアルゴリズムより性能が劣る結果を示します。

上の記事は一般的なソートアルゴリズムに対して、要素数を変えながら性能評価をまとめたものです。実装次第ではありますが、上記記事では要素数が32～64ぐらいまでは挿入ソートが最速という結果を示しています。いくらか調べてみた感じでも、ソート界隈（？）では要素数32ぐらいまでは挿入ソートが最強というのは定説っぽいと感じました。

また、コムソートが要素数によらず安定してそこそこ速いのも印象的です。

このように条件次第で適切なアルゴリズムが変わってくるため、条件によってアルゴリズムを差し替える、という最適化が行われることがあります。実例を示していきます。

イントロソート（改良版クイックソート）

少ない要素数が苦手なのはクイックソートも同様です。さらにクイックソートには、最悪計算時間がO(n^2)であるという弱点も存在します。これら問題を克服するため、クイックソートの改良版としてイントロソート（Introsort）があります。

イントロソートは、基本的にはクイックソートですが、条件次第で別の処理に差し替えます。

  1. 最悪計算時間対策として、再帰のレベル（部分リストの階層の深さ）が一定数を超えるとヒープソートに差し替える。
  2. 要素数が少ないときには、挿入ソートで差し替える。

イントロソートを構成するクイックソート、ヒープソート、挿入ソートというすべてのソートがIn-placeなのが素晴らしい。

ティムソート（改良版マージソート）

マージソートの改良版として、ティムソート（Timsort）があります。Tim PetersさんがPythonで実装したのが最初で、Python 2.3、Java SE 7やAndroidにおいて標準のソートとして採用された実績があります。

残念ながら、Wikipediaには日本語の記事がありません。

日本語での解説は少ないですが、大まかに理解するには上の記事で事足りるでしょう。

実用データを意識したヒューリスティクス（発見的方法）を取り入れていて、イントロソートより複雑な手法です。実用上は最強の安定ソートっぽいけど、実装がちょっと大変。

ティムソートの中で部分的に採用する挿入ソートは、通常の挿入ソートとは異なり、挿入位置を決定するのに二分探索を用いる二分挿入ソートだそうです。少ない要素数に対して、そこまでする必要があるのかちょっと実感がないのですが、比較関数が重い場合を考えると、比較回数を減らすのは有効そうですね。

ただ、二分探索するということは、ランダムアクセス可能ということです。これはLinkedListには使えないですね。通常の挿入ソートに差し替えて、劣化版ティムソートぐらいにはできるでしょうか。

余談ですが、Java 7で取り入れられたTimsortにはバグがあって、Java 8u60で修正されたそうです。何そのホラー。

UnityのArray.Sort()実装

標準機能の実装について紹介する中で、UnityのArray.Sort()が「条件次第ではコムソートに置き換え」ということを書きました。GitHubから該当箇所を引用します。public static void Sort (Array keys, Array items, int index, int length, IComparer comparer)メソッドです。

if (comparer == null) {
    Swapper iswapper;
    if (items == null)
        iswapper = null;
    else
        iswapper = get_swapper (items);
    if (keys is double[]) {
        combsort (keys as double[], index, length, iswapper);
        return;
    }
    if (!(keys is uint[]) && (keys is int[])) {
        combsort (keys as int[], index, length, iswapper);
        return;
    }
    if (keys is char[]) {
        combsort (keys as char[], index, length, iswapper);
        return;
    }
}

比較関数オブジェクトcomparerがnull指定されたとき、ソートに利用するキー集合がdouble/int/charのいずれかの配列であるときにコムソート（combsort）が適用されます。それぞれの型に対応する専用のコムソート実装が存在します。

コムソートは挿入ソートの改良版ではありますが、代償として安定ソートではなくなっています。

Unityは、型によってコムソートに置き換えているわけですが、比較関数を挟んだ汎用処理を捨てたことでオーバーヘッドを減らしています。実際、コムソートが効くケースではめちゃくちゃ速いです。

但し、ほとんどの人がこのコムソートによる最適化の恩恵を受けないでしょう。何故なら、比較関数を与えない引数なしList<T>.Sort()の中に下記の処理があるからです。

public void Sort ()
{
    Array.Sort<T> (_items, 0, _size, Comparer <T>.Default);
    _version++;
}

Comparer<T>.Defaultでデフォルトの比較関数を取得してcomparerとして渡しています。ｽﾞｺｰ

なので、double/int/charのListについては、Sort()ではなくSort((IComparer<T>)null)した方が速いという衝撃の事実。速度計測しておかしいなと思ってよく調べたら、この違いに気付いたわけです。調べても全然情報出てこないし、殆どの人に知られてないんじゃなかろうか。

今回実装する安定ソート

ティムソート作るぞって言いたいところなんですが、そこそこ速くて実用的であればいいので、もっと実装が簡単でバグを出しにくいアプローチを考えた方が安心感あります。

長々と書いてきましたが、結論としては、マージソートをベースにして要素数が少ない時に挿入ソートに置き換えます。それだけ。ごめんなさい。

この記事が長くなったので、実装は別の記事に分離しました。下記リンクからどうぞ。

気が向いたらティムソート作るかもだけど、そこまでしなきゃいけない事情もないので期待しないでください・・・。

コメントを残す（Markdown有効）

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。

Top