配列存在チェックのために二分探索メソッドを実装する（速度比較も）【C#】

# 配列存在チェックのために二分探索メソッドを実装する（速度比較も）【C#】

例によってAtcoderを解いてて詰まったから作りました。
(2022-08-27 ABC266-F)

https://atcoder.jp/contests/abc266/tasks/abc266_f

配列に該当項目が存在するか？のためにListから.Contains(i)をしているとTLEします。
効率よい探索が必要。
Pythonならmap機能でinで探すだけで高速に見つけてくれるが、C#には無いので自作します。

# 探索方法検討
自作の前に...
そもそも、c#には色々便利なリストがあります。これらを利用できないか。
ということで、以下を比較検討しました。
## １．Generic.SortedSetクラス
https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.sortedset-1?view=net-6.0
## ２．System.Collections.SortedListクラス
https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.sortedlist?view=net-6.0

## ３．Generic.SortedList＜TKey,TValue＞ クラス

https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.sortedlist-2?view=net-6.0

## ４．IOrderdEnumerableクラス
https://docs.microsoft.com/ja-jp/dotnet/api/system.linq.iorderedenumerable-1?view=net-6.0

## ５．自作二分探索クラス
``` map.cs
    public class Map
    {
        private long[] _sortedAry;
        public Map(IEnumerable<long> t)
        {
            _sortedAry = t.OrderBy(p => p).ToArray();
        }
        public Map(IEnumerable<int> t)
        {
            _sortedAry = t.Select(p => (long)p).OrderBy(p => p).ToArray();
        }
        public Map(IOrderedEnumerable<long> t)
        {
            _sortedAry = t.ToArray();
        }
        public int this[long i] //1次元
        {
            get { return (_sortedAry.Length == 0) ? -1 : GetIndex(i, 0, _sortedAry.Length - 1); }
        }
        private int GetIndex(long i, int st = 0, int ed = -1)
        {
            if (ed - st <= 0)//最後1回
                return (_sortedAry[st] == i) ? st : -1;

            int half = st + (ed - st) / 2;

            if (_sortedAry[half] > i)
                return GetIndex(i, st, half);
            else if (_sortedAry[half] < i)
                return GetIndex(i, half + 1, ed);
            else
                return half;
        }
    }
```
※Contains(i)じゃなくて[i]で検索します。ついでにインデックスも帰ってくる。


## 実際にテストしてみる

### テストに使用したコード
``` test.cs
public test()
        {
            const int SIZE = 200000;
            const int SEARCH_COUNT = 10000;

            var sw = new System.Diagnostics.Stopwatch();
            Console.WriteLine("START");
            sw.Start();

            var q = new List<int>();
            Random r1 = new System.Random();
            for (int i = 0; i < SIZE; i++)
                q.Add(r1.Next(0, SIZE * 2));

            q = q.Distinct().ToList();
            var qDic = q.ToDictionary(x => x, y => 0);

            var sample_list = new int[SEARCH_COUNT];
            for (int i = 0; i < SEARCH_COUNT; i++)
                sample_list[i] = r1.Next(0, SIZE * 2);

            sw.Stop();
            Console.WriteLine(sw.Elapsed + " - Make Rand");
            sw.Restart();

            var pret = new bool[SEARCH_COUNT];
            for (int c = 0; c < SEARCH_COUNT; c++)
                pret[c] = q.Contains(sample_list[c]);

            sw.Stop();
            Console.WriteLine(sw.Elapsed + " - Pure Array Contains");
            sw.Restart();

            var y2 = q.OrderBy(p => p).ToArray();

            sw.Stop();
            Console.WriteLine(sw.Elapsed + " - Array(Sorted)");
            sw.Restart();

            var y2ret = new bool[SEARCH_COUNT];
            for (int c = 0; c < SEARCH_COUNT; c++)
                y2ret[c] = y2.Contains(sample_list[c]);

            sw.Stop();
            Console.WriteLine(sw.Elapsed + " - Array(Sorted) Contains");
            sw.Restart();

            var y1 = q.OrderBy(p => p);

            sw.Stop();
            Console.WriteLine(sw.Elapsed + " - IOrderdEnumerable");
            sw.Restart();

            var yret = new bool[SEARCH_COUNT];
            for (int c = 0; c < SEARCH_COUNT; c++)
                yret[c] = y1.Contains(sample_list[c]);

            sw.Stop();
            Console.WriteLine(sw.Elapsed + " - IOrderdEnumerable Contains");
            sw.Restart();

            SortedList x1 = new SortedList(qDic);
            //SortedList x1 = new SortedList();
            //for (int i = 0; i < q.Count(); i++)
            //    x1.Add(q[i], 0);

            sw.Stop();
            Console.WriteLine(sw.Elapsed + " - SortedList");
            sw.Restart();

            var xret = new bool[SEARCH_COUNT];
            for (int c = 0; c < SEARCH_COUNT; c++)
                xret[c] = x1.Contains(sample_list[c]);

            sw.Stop();
            Console.WriteLine(sw.Elapsed + " - SortedList Contains");
            sw.Restart();

            var x2 = new System.Collections.Generic.SortedList<int, int>(qDic);
            //var x2 = new System.Collections.Generic.SortedList<int, int>();
            //for (int i = 0; i < q.Count(); i++)
            //    x2.Add(q[i], 0);

            sw.Stop();
            Console.WriteLine(sw.Elapsed + " - Generic.SortedList");
            sw.Restart();

            var x2ret = new bool[SEARCH_COUNT];
            for (int c = 0; c < SEARCH_COUNT; c++)
                x2ret[c] = x2.ContainsKey(sample_list[c]);

            sw.Stop();
            Console.WriteLine(sw.Elapsed + " - Generic.SortedList Contains");
            sw.Restart();

            var x3 = new SortedSet<int>(q);
            //var x3 = new SortedSet<int>();
            //for (int i = 0; i < q.Count(); i++)
            //    x3.Add(q[i]);

            sw.Stop();
            Console.WriteLine(sw.Elapsed + " - Generic.SortedSet");
            sw.Restart();

            var x3ret = new bool[SEARCH_COUNT];
            for (int c = 0; c < SEARCH_COUNT; c++)
                x3ret[c] = x3.Contains(sample_list[c]);

            sw.Stop();
            Console.WriteLine(sw.Elapsed + " - Generic.SortedSet Contains");
            sw.Restart();

            var z1 = new Map(q);

            sw.Stop();
            Console.WriteLine(sw.Elapsed + " - Map[Custom Class]");
            sw.Restart();

            var zret = new bool[SEARCH_COUNT];
            for (int c = 0; c < SEARCH_COUNT; c++)
                zret[c] = z1[sample_list[c]] != -1;

            sw.Stop();
            Console.WriteLine(sw.Elapsed + " - Map[Custom Class] Contains");
        }
```

比較のために未ソート、ソートしてからToArray()も入れています。

# 結果

**縦軸は検索回数(SEARCH_COUNT)=nとして表記**

### 配列SIZE=1000のとき

**配列作成にかかる時間**
| ＼|Pure Array | Array(Sorted) | IOrderdEnumerable | SortedList | Generic.SortedList | Generic.SortedSet | 二分探索カスタムクラス |
|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|
|-|-|0.0025350|NaN|0.0012768|0.0005517|0.0009834|0.0000847|0.0024926|

**検索回数**
| ＼|Pure Array | Array(Sorted) | IOrderdEnumerable | SortedList | Generic.SortedList | Generic.SortedSet | 二分探索カスタムクラス |
|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|
|n=100|0.0000582|0.0000846|0.0095038|**0.0000370**|0.0000895|0.0001719|0.0001320|
|n=10000|0.0010369|0.0011975|0.6199364|0.0016111|**0.0007442**|0.0007591|0.0018011|
|n=10000000|0.9748624|1.0208422|測定不能|1.2198101|0.5478009|**0.5386517**|1.6215458|

### 配列SIZE=200000のとき

**配列作成にかかる時間**
| ＼|Pure Array | Array(Sorted) | IOrderdEnumerable | SortedList | Generic.SortedList | Generic.SortedSet | 二分探索カスタムクラス |
|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|
|-|-|0.0261035|NaN|0.0524448|0.0102246|0.0207644|0.0337261|

**検索回数**
| ＼|Pure Array | Array(Sorted) | IOrderdEnumerable | SortedList | Generic.SortedList | Generic.SortedSet | 二分探索カスタムクラス |
|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|
|n=10|0.0002383|0.0005216|0.2703895|0.0000534|0.0002125|**0.0000051**|0.0002183|
|n=100|0.0016324|0.0296529|2.5551150|0.0001112|0.0001635|**0.0000370**|0.0003051|
|n=10000|0.1601330|0.1715653|測定不能|0.0032967|**0.0013078**|0.0028416|0.0035492|


### 配列SIZE=10000000のとき

**配列作成にかかる時間**
| ＼|Pure Array | Array(Sorted) | IOrderdEnumerable | SortedList | Generic.SortedList | Generic.SortedSet | 二分探索カスタムクラス |
|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|
|-|-|2.5203717|NaN|6.2385000|**0.6050261**|1.4195260|2.5881175|

**検索回数**
| ＼|Pure Array | Array(Sorted) | IOrderdEnumerable | SortedList | Generic.SortedList | Generic.SortedSet | 二分探索カスタムクラス |
|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|
|n=100|0.1959737|0.1902311|測定不能|**0.0002974**|0.0003365|0.0004881|0.0004014|


# 結論

+ **基本Generic.SortedSetが最強**
+ **ただし、データ件数によってはGeneric.SortedListが配列の作成時間的に有利になることも**(元データがDictionary型だとSortedList有利)

+ Arrayをソートしておいても特に結果が変わるわけではない
+ ソートしてもIOrderdEnumerableのまま使うとかえって遅くなる
+ SortedListはごく少ないリストの時、最速になる可能性がある
+ 二分探索カスタムクラスは勝てない...


:::note warn
SortedList、SortedSetは配列の再作成コストが重いです。初期値の後でデータを追加/削除することが多い(10^6回以上ぐらい)ときは、
その場合は二分探索カスタムクラスがワンチャンあります。
（2*10^5回の追加でList＜int＞は0.0014sに対し、SortedList：2.21s、Generic.SortedList：0.68s、SortedSet：0.057s、Generic.SortedSet：0.036s）
:::

:::note warn
SortedList、Generic.SortedList、SortedSet、Generic.SortedSetは、重複キーが許可されません。
今回は必要としませんでしたが、存在チェック後にそれに紐づくデータを取得したい場合は、DictionaryやGeneric.SortedListが俄然便利です。
:::

# おまけ

要素が２つある形の二分探索クラスも作りました。
グリッド上の(x,y)を探したいときなどに便利？(Dictionaryだとxがキー重複してしまうため)

```Map2D.cs
    public class Map
    {
        //2次元バージョン------------------------------------------------------------------------------------------------
        private long[][] _sortedAry2D;

        public Map(long[][] tary)
        {
            var t = new List<long[]>();
            t.AddRange(tary);
            _sortedAry2D = t.OrderBy(p => p[0]).ThenBy(p => p[1]).ToArray();
        }
        public Map(List<long[]> t)
        {
            _sortedAry2D = t.OrderBy(p => p[0]).ThenBy(p => p[1]).ToArray();
        }
        public Map(List<int[]> t)
        {
            _sortedAry2D = t.Select(p => { return Array.ConvertAll(p, e => (long)Convert.ChangeType(e, typeof(long))); }).OrderBy(p => p[0]).ThenBy(p => p[1]).ToArray();
        }

        //二分探索でi,jが存在するか確認 存在する場合はindex,ない場合は-1を返す
        public int this[long i, long j] //2次元バージョン
        {
            get { return (_sortedAry2D.GetLength(0) == 0) ? -1 : GetIndex2D(i, j, 0, _sortedAry2D.GetLength(0) - 1); }
        }

        private int GetIndex2D(long i, long j, int st = 0, int ed = -1)
        {
            if (ed - st <= 0)//最後1回
                return (_sortedAry2D[st][0] == i && _sortedAry2D[st][1] == j) ? st : -1;

            int half = st + (ed - st) / 2;

            if (_sortedAry2D[half][0] > i)
                return GetIndex2D(i, j, st, half);
            else if (_sortedAry2D[half][0] < i)
                return GetIndex2D(i, j, half + 1, ed);
            else
            {
                if (_sortedAry2D[half][1] > j)
                    return GetIndex2D(i, j, st, half);
                else if (_sortedAry2D[half][1] < j)
                    return GetIndex2D(i, j, half + 1, ed);
                else
                    return st;
            }
        }
    }
```