LoginSignup
0
0

More than 1 year has passed since last update.

@so_rei(So-rei)

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

Last updated at Posted at 2022-08-28

配列存在チェックのために二分探索メソッドを実装する（速度比較も）【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;
            }
        }
    }
0
0
5

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0