【C#】自作クラスのグループ化と並び替え

• はじめに
• 文字列のListを並び替える
• 自作クラスのListを並び替える
• 自作クラスのListをグループ化して並び替える
• SelectManyについて
• おわりに
• 参照

はじめに

2017年に収まらなかったので新年一発目の記事となります。

今年もふと気になったあれこれ、やってみたあれこれを雑多に書き残していきますのでよろしくお願いいたします。

さてさて今回のお題ですが、自作クラスの並べ替えを雑にやろうとしたところ、
全然入れ替わらなかったりうまくいかなかったので、
もう少しちゃんと見てみるかぁ、という内容です。

• 文字列の List を並び替える
• 文字列 > int の2つの要素で並び替える
• 文字列をグループ化した後 int で並び替える

文字列のListを並び替える

まずは文字列の Sort について見てみます。

例えばこのような List があった場合。

var sampleList = new List< string> {
    "カテゴリー1",
    "カテゴリー2",
    "カテゴリー",
    "カテゴリー1",
    "カテゴリー2",
    "カテゴリー5",
};

これを下記のように Sort() を引数なしで実行すると、 List が昇順に並び替えられます。

sampleList.Sort();

これが何をしているのかを見たかったのですが、
List クラスが IComparer< T> を null にして Array.Sort< T> を呼んでいる辺りで処理を見失ってしまいました。

というわけで、それはいったん置いておいて msdn のサンプルを見てみることにします。

Sort メソッドに ICompare を継承し、 int を返す Compare メソッドを渡すことで、
並び替える方法がカスタマイズできます。

• List(T).Sort メソッド (IComparer(T)) (System.Collections.Generic) - msdn.aspx)

サンプルでは比較する2つの値が Null かどうかなども確認していますが、
両方 Null ではない場合の比較は下記の 2 種類です。

int retval = x.Length.CompareTo(y.Length);

if (retval != 0) {
    return retval;
}
else {
    return string.Compare(x, y, StringComparison.Ordinal);
}

• x は第一引数の文字列、 y は第二引数の文字列です。

上は簡単で、文字数が異なる場合にその差分を返しています。
下は unsafe メソッドを使って、先頭から一文字ずつ比較をしていました。

パフォーマンス的な理由から、文字数などで違いが判別できる場合はそちらを使っているようです。

Compareメソッドの戻り値

Compare メソッドが返す値は大きく分けて 3 種類です。

• 0 未満： x が y より前に設定される
• 0： 順序変わらず
• 0 より大きい： x が y より後に設定される

後で少し触れますが、例えば -1 を返したときと -5 を返したときで、
Sort() で比較対象として引数に渡される回数が変わっていました。

Sort() は何回実行されるのか

最大で O(n ^ 2) (要素数の 2 乗 * 係数)とのことですが、上記のコードの場合は要素数 6 で 20 回実行されました。

• List(T).Sort メソッド (IComparer(T)) (System.Collections.Generic) - msdn.aspx)

自作クラスのListを並び替える

では、下記のような自作クラスを並び替えてみます。

SampleValue.cs

public class SampleValue {
    public int Id { get; set; }
    public string Category { get; set; }
}

で、これを Category > Id の順に並び替えてみます。

using System;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

public class SortSample : MonoBehaviour {
    private void Start () {
            var sampleList = new List< SampleValue>{
                    new SampleValue {
                        Id = 0,
                        Category = "カテゴリー1",  
                    },
                    new SampleValue {
                        Id = 3,
                        Category = "カテゴリー2",
                    },
                    new SampleValue {
                        Id = 5,
                        Category = "カテゴリー",
                },
                    new SampleValue {
                        Id = 1,
                        Category = "カテゴリー1",
                    },
                    new SampleValue {
                        Id = 2,
                        Category = "カテゴリー2",
                    },
                    new SampleValue {
                        Id = 4,
                        Category = "カテゴリー5",
                    },
        };  
        var compare = new CompareSample();
            // Listを並び替える.
        sampleList.Sort(compare.Compare);

        sampleList.ForEach(v => Debug.Log("ID: " + v.Id + " C: " + v.Category));
    }
}
// 並び替えるためのクラス.
public class CompareSample : IComparer< SampleValue> {
    public int Compare(SampleValue x, SampleValue y) {
        int retval = x.Category.Length.CompareTo(y.Category.Length);
        
        if (retval != 0) {
            return retval;
        }
        else {
            int compareCategory = string.Compare(x.Category, y.Category, StringComparison.Ordinal);
                    // Categoryの値を比較して同じであった場合にIdで並び替え.
            return compareCategory == 0 ? x.Id.CompareTo(y.Id) : compareCategory;
        }
    }
}

• Sort() は List の中の順番を入れ替えるため戻り値の取得などは行いません。
• まず Category 同士を比較し、同じ Category であった場合に Id で並び替えています。

実行結果です。

1. Id: 5 Category: カテゴリー
2. Id: 0 Category: カテゴリー1
3. Id: 1 Category: カテゴリー1
4. Id: 2 Category: カテゴリー2
5. Id: 3 Category: カテゴリー2
6. Id: 4 Category: カテゴリー5

どんな順番で実行されるのか

上で実行回数について触れましたが、どんな組み合わせで実行されるのでしょうか。

実際のところは Sort のアルゴリズムを学ばないと理解できないところではありますが、
とりあえず今回のサンプルを動作させた結果を載せておきます。

List の一番最初に来る「カテゴリー」は 11 回呼ばれているのに対し、
最後に来る「カテゴリー5」は 3 回のみ、かつ第一引数( x )としては一度も呼ばれていませんでした。

この結果だけで考えると、文字列の List を並び替える場合、
それぞれの違いが小さければ小さいほど実行回数は増えるのでは？という感じがしました。

自作クラスのListをグループ化して並び替える

上記では、 Category という文字列に対しても並び替えられていました。

それでは、Category は並び替えず、
同じ Category を持つ Id で並び替えるにはどのようにすれば良いでしょうか。

グループ化する

今回は Linq の GroupBy を使ってみました。

何も考えずに書こうとすると、下記のように書きたくなるのですが、
これだとエラーになります。

// 戻り値が  IEnumerable< IGrouping< string, SampleValue>> であるためエラー.
sampleList.GroupBy(v => v.Category)
    .OrderBy(v => v.Id);

sampleList.GroupBy(v => v.Category) から、 List< SampleValue> の値を取得するには、
SelectMany を使う必要があります。

var sortedList = sampleList.GroupBy(v => v.Category)
    .SelectMany(v => v);

v => v のところが少し変な感じもしますね。

なお、 foreach を使って取得することもできます。

var sortedList = sampleList.GroupBy(v => v.Category);

foreach(var k in sortedList) {
    foreach (var v in k) {
        Debug.Log(v.Category + " Id " + v.Id);
    }
}

結果は下記の通りです。

1. Id: 0 Category: カテゴリー1
2. Id: 1 Category: カテゴリー1
3. Id: 3 Category: カテゴリー2
4. Id: 2 Category: カテゴリー2
5. Id: 5 Category: カテゴリー
6. Id: 4 Category: カテゴリー5

グループ化した List を並び替える

あとはこれをグループごとに並び替えます。

といってこのような感じで並び替えてしまうと、
グループ化が解除されて Id のみで並び替えられてしまいます。

var sortedList = sampleList.GroupBy(v => v.Category)
            .SelectMany(v => v)
            .OrderBy(v => v.Id);

※今回のデータの作りがまずく、このまま実行すると一見そろっているように見えますが、
Category の値を変えるとグループ化されていないのがわかります。

これを防ぐためには、 SelectMany の中で並び順を指定する必要があります。

var sortedList = sampleList.GroupBy(v => v.Category)
            .SelectMany(v => v.OrderBy(x => x.Id));

結果は下記の通りです。

1. Id: 0 Category: カテゴリー1
2. Id: 1 Category: カテゴリー1
3. Id: 2 Category: カテゴリー2
4. Id: 3 Category: カテゴリー2
5. Id: 5 Category: カテゴリー
6. Id: 4 Category: カテゴリー5

SelectManyについて

では今回活躍してくれた、 SelectMany についてもう少し見てみることにします。

SelectMany を使うことで、 IEnumerable< IGrouping< string, SampleValue>> という型で戻ってくる GroupBy の結果を、
IEnumerable< SampleValue> という型に変換できます。

で、この SelectMany のソースをたどってみると、先ほど値を取り出したときと同じように、
foreach を使って値を取り出していました。

Enumerable.cs

private static IEnumerable< TResult> SelectManyIterator< TSource, TResult>(IEnumerable< TSource> source, Func< TSource, IEnumerable< TResult>> selector) {
    foreach (TSource source1 in source) {
        foreach (TResult result in selector(source1))
            yield return result;
    }
}

そのため、下記のようにすれば SelectMany を使わず同様のことができます。
(需要があるかはわかりませんが)

private void Start() {
    ～省略～

    var sortedList = GetSortedSampleValues(sampleList.GroupBy(v => v.Category));
}
private IEnumerable< SampleValue> GetSortedSampleValues(IEnumerable< IGrouping< string, SampleValue>> groupedValue) {
    foreach(var k in groupedValue) {
        // IGrouping< string, SampleValue> を IdでSort.
        foreach (var v in k.OrderBy(v => v.Id)) {
            yield return v;
        }
    }
}

一応両者を計測してみたところ、若干 Foreach の方が良い結果になっていました。

おわりに

Linq は良いぞ

…まぁ使用状況によっては for を使う場合に比べて GC alloc の量が増えたり、
いつでもどこでも使おうぜ！とまでは言い難いです。

ただ、今回のように複雑な処理がわずか数行で書けてしまうのはすごいですね。

参照

Sort

• List(T).Sort Method (IComparer(T)) (System.Collections.Generic).aspx)
• String.Compare Method (String, String, StringComparison) (System)
• 【C#】リストや配列のソート方法まとめ - NinaLabo

GroupBy

• group 句 (C# リファレンス) - Microsoft Docs
• Enumerable.GroupBy(TSource, TKey, TElement) メソッド (IEnumerable(TSource), Func(TSource, TKey), Func(TSource, TElement)) (System.Linq) - msdn.aspx)

SelectMany

• Enumerable.SelectMany(TSource, TResult) Method (IEnumerable(TSource), Func(TSource, IEnumerable(TResult))) (System.Linq) - msdn.aspx)
• LINQ：取得列を明示的に指定する - select句／SelectManyメソッド［C#］ - Build Insider

Others

• unsafe - C# によるプログラミング入門 - ++C++; // 未確認飛行 C
• ビッグ・オー記法(Big-O notation) - Team TRIPLE FALCON