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

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

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

探索方法検討

自作の前に...
そもそも、c#には色々便利なリストがあります。これらを利用できないか。
ということで、以下を比較検討しました。

１．Generic.SortedSetクラス

２．System.Collections.SortedListクラス

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

４．IOrderdEnumerableクラス

５．自作二分探索クラス

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

検索回数

＼	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はごく少ないリストの時、最速になる可能性がある
二分探索カスタムクラスは勝てない...

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）

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;
            }
        }
    }