【C#】ソート済み List を動的に作る拡張メソッド

2021/02/02 Tue [edit]

　今回は二分探索によるリスト処理の高速化できる拡張メソッドを作ってみよう。

　普段、何気なく List に値を Add したり、Remove したりしてはいないだろうか？
　また検索というと、標準で使える List.Contains や List.Find、List.FindIndex 等や、Linq の FistOrDefault などを使う機会も多いだろう。
　しかし、これらは逐次探索（O(n)）のため、要素数に比例して、検索速度は遅くなる。特に1000を超えるデータを頻繁に扱うとなると、かなり実行速度に影響が出る。

　そのような場合、ケースにもよるのだが、List に追加する要素の順番は必要ないとき、または ID のように昇順で並んでいる方が便利なとき等、常に List をソート済みにしておくと、二分探索(BinaraySearch)が使えるようになる。
　二分探索のオーダーは O(log n) のため、要素が多くなっても、検索速度はそれほど落ちない。

　もし、ただの１回のみのソートで良いのなら、全て要素を追加した後に、単純に List.Sort や Linq の OrderBy を使う方が良いだろう。しかし、頻繁にデータを追加したり、削除したりする場合は、動的にソート済みリストを作っていく拡張メソッドを作っておくと便利だ。

●動的にソート済みリストに要素を追加、削除していく拡張メソッド

using System.Collections.Generic;

public static class Extentions  //※名前は任意
{
    /// <summary>
    /// 昇順で要素を追加する
    /// 2021/02/02 Fantom
    /// http://fantom1x.blog130.fc2.com/blog-entry-392.html
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="list">対象リスト</param>
    /// <param name="value">追加する要素</param>
    /// <returns>true = 新規追加 / false = 既存あり(重複で追加)</returns>
    public static bool AddSorted<T>(this List<T> list, T value)
    {
        int idx = list.BinarySearch(value);
        if (idx < 0)
        {
            list.Insert(~idx, value);
            return true;
        }
        list.Insert(idx, value);
        return false;
    }

    /// <summary>
    /// 昇順で要素をユニーク追加する
    /// 2021/02/02 Fantom
    /// http://fantom1x.blog130.fc2.com/blog-entry-392.html
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="list">対象リスト</param>
    /// <param name="value">追加する要素</param>
    /// <returns>true = 新規追加 / false = 既存あり(追加しない)</returns>
    public static bool AddSortedUniq<T>(this List<T> list, T value)
    {
        int idx = list.BinarySearch(value);
        if (idx < 0)
        {
            list.Insert(~idx, value);
            return true;
        }
        return false;
    }

    /// <summary>
    /// 昇順のリストから要素を削除
    /// 2021/02/02 Fantom
    /// http://fantom1x.blog130.fc2.com/blog-entry-392.html
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="list">対象リスト</param>
    /// <param name="value">削除する要素</param>
    /// <returns>true = 削除した / false = 既存なし(削除失敗)</returns>
    public static bool RemoveSorted<T>(this List<T> list, T value)
    {
        int idx = list.BinarySearch(value);
        if (idx >= 0)
        {
            list.RemoveAt(idx);
            return true;
        }
        return false;
    }
}

●メインコード例

using System;
using System.Collections.Generic;

string[] array =
{
    "Apple", "Banana", "Candy", "Donuts", "Egg", "Fish", "Candy", "Egg"
};

array.Shuffle();  //※Shuffle は以前の記事を参照
Console.WriteLine(array.Dump());  //※Dump は以前の記事を参照

var list1 = new List(array.Length);
var list2 = new List(array.Length);
foreach (var item in array)
{
    list1.AddSorted(item);      //昇順で追加
    list2.AddSortedUniq(item);  //昇順でユニーク追加
}

Console.WriteLine("list1 : " + list1.Dump());  //※Dump は以前の記事を参照
Console.WriteLine("list2 : " + list2.Dump());  //※Dump は以前の記事を参照

//昇順リストから削除
list1.RemoveSorted("Candy");
list1.RemoveSorted("Egg");
Console.WriteLine("list1 (Removed) : " + list1.Dump());  //※Dump は以前の記事を参照
Console.WriteLine("list2 (Removed) : " + list2.Dump());  //※Dump は以前の記事を参照

//二分探索
int idx1 = list1.BinarySearch("Candy");
Console.WriteLine($"idx1 = {idx1}");
int idx2 = list1.BinarySearch("Egg");
Console.WriteLine($"idx2 = {idx2}");

[Banana, Egg, Apple, Candy, Egg, Donuts, Fish, Candy]
list1 : [Apple, Banana, Candy, Candy, Donuts, Egg, Egg, Fish]
list2 : [Apple, Banana, Candy, Donuts, Egg, Fish]
list1 (Removed) : [Apple, Banana, Candy, Donuts, Egg, Fish]
list2 (Removed) : [Apple, Banana, Candy, Donuts, Egg, Fish]
idx1 = 2
idx2 = 4

　Dump と Shuffle の拡張メソッドは以前に作ったものだ。

・Dump の拡張メソッド
・Shuffle の拡張メソッド

　どのように追加されているかに注目して欲しい。常に昇順に並び替えたリストと同義となるため、追加するたびソート（List.Sort）する必要はもちろん無い。
　取得するときは List.BinarySearch が使えるので、ちょっとやそっと要素数が増えた所で、検索速度が落ちることはない（実際に 100000 [10万] くらいの要素数があっても、検索速度は速い）。

　また、この例ではコンストラクタで new List(int capacity) を使っているが、これは予め格納できるサイズを確保しておくコンストラクタだ。色々なコードを見ていても、ほとんどが引数なし new List() で使われているが、実はこれはとても重要だ。と言うのは、List の様な動的に増やせるコレクションというのは、現在格納できるサイズを超えると、メモリの再割当てをし(サイズ拡大)、コピーする動作を頻繁に繰り返すからだ。要素が多くなると、負荷がかかるのは言うまでもない。はじめからわかっている、または想定できるなら、capacity を指定した方が、要素を追加するとき、無駄な処理が走らない（Dictionary なども同じ）。

　以下は Unity 上で、毎フレーム逐次検索(List.Contains や List.Find)していた箇所を、二分探索探索に置き換えただけのもので、パフォーマンスを比較してみたものだ。
　青い部分はスクリプトの負荷で、激減していることが分かる。実際にほんの数行置き換えただけなのだが、圧倒的なパフォーマンスを出すことができることさえある（この時は約5倍以上になった）。