C#において配列の探索方法について

自己紹介

　はじめまして、YukiTeitoというものです。色々あって初めてQiitaを書いてみようと思いました。先日、.NET系のプログラミングを書いていた時に配列の探索をしなくてはいけなくなりました。そこで、どの配列の探索方法が速いのか、どの配列の探索方法が扱いやすいのか考えたので、この記事を書くことにしました。また、この記事は TUT Advent Calendar の記事になります。

今回はコンソール上で動く配列の探索方法について比較していきたいと思います。
今回のタイム計測に使うソースコードはこちらです。

        double[] nums = new double[100000000];
        for (int i = 0; i < nums.Length; i++) nums[i] = i;

        var stopWatch = new System.Diagnostics.Stopwatch();//ストップウォッチクラスの生成

        stopWatch.Start();//ストップウォッチをスタートする

        //この中に処理を書く

        stopWatch.Stop();//ストップウォッチを止める

        TimeSpan ts = stopWatch.Elapsed;//TimeSpanクラスの変数に代入

        //出力
        Console.WriteLine($"　{ts}");

今回はこの方法で計測していこうと思う。

Array.IndexOf()について

Array.IndexOf()は、標準で使える配列探索方法です。第一引数として探査対象の配列、第二引数として探索する変数、第三引数として探索するスタート地点を与えることができます。（第三引数は省略できる。）
使い方は以下です。

         int num = Array.IndexOf(nums,3520029);

この時の計測時間は以下で

         00:00:00.0044419

となり、0.0044419秒であった。1000回実行したところ0.43169秒であった。

while文での探索

While分で探索地道に探索をする方法です。while文では、配列の最初からif文を用いて判定し、見つける方法です。
ソースコードは以下。

　　　　　　　　　　　　　　 int j = 0;
            while (true)
            {
                if (nums[j] == 3520029)
                {
                    Console.WriteLine($"{j}");
                    break;
                }
                j++;
            }

この時の計測時間は以下

　　　　　　00:00:00.0274552

となった。平均しても0.0275651秒となった。正直めんどうだし上のほうが断然良いだろう。こんなやつ使うのはくそだ！！

二分探索法について

この二分探索法は、ソート済みのデータに対して、行う探索方法です。探索する値を中央値と比較し、その値が中央値より上にあるかしたにあるかで二分し範囲を狭めていくことで探索をより速くする方法です。
ソースコードは以下

　　　　　public static int BinarySearch<T>(T[] array, T target) where T : IComparable<T>
        {
            int min = 0;
            int max = array.Length - 1;

            while (true)
            {
                // 範囲内に見つからなかった
                if (max < min) return -1;
                // 範囲内の中央値と比較する
                int mid = min + (max - min) / 2;
                switch (target.CompareTo(array[mid]))
                {
                    case -1:    // 中央値より小さい
                        max = mid - 1;
                        break;
                    case 1:     // 中央値より大きい
                        min = mid + 1;
                        break;
                    case 0:     // 見つかった
                        return mid;
                }
            }
        }

この探索法の速度は以下となりました。

　　　　　00:00:00.0001749

平均では、0.0001929秒となった。今回は、他の探索法と違いソートしてあることが前提なので他の探索法より速いことは当然かもしれないが、とにかく書くのがめんどくさい！！実行速度がほしいときはこの方法を使おう（速度がほしいときはC#を使うな）

でも正直どれも遅くね？

探索を何回もすることもあるでしょう。その際に、こんな探索をしていてはプログラミングが遅くて使えません！！
こんなの使う人なんてどう考えてもゴミですね！！こんなの使う人いません。これからは画期的な探索法を書いていきたいと思います。

SuperSearchメソッドという神メソッド

このメソッドは、すべてを抹消しターゲットだけを要素として持つ配列にしてしまうメソッドに変えてしまうメソッドです。これで、配列の計算や要素の中身の把握などせずにいろいろなことができるようになります。

　　　　　public static int SuperSearch(int[] array , int target)
        {
            Array.Clear(array,0,array.Length);
            array[0] = target;
            return 0;
        }

肝心な時間はというと

　　　　　　00:00:00.0138071

となった。少し遅いが便利過ぎてめっちゃ使える。

SuperSearch2メソッド

このメソッドは、配列のすべてを探索したい変数に変えてしまうメソッドです。このことからどこを参照しても必ず探索したい数字が出てくるのですごいです。

　　　　　public static int SuperSearch2(int[] array , int target)
        {
            Random rnd = new Random();
            for (int i = 0; i < array.Length; i++) array[i] = target; 
            return rnd.Next(array.Length);
        }

この実行速度は

　　　　00:00:00.2134277

まぁまぁまぁ、この機能はかなり優秀なのでしょうがないと言えます。やはり画期的な探索法には、時間が必要ですね。

ExtraSearchメソッド

このメソッドは、配列の最初に探索したいメソッドを持ってくるというものすごい使いやすくかつ実行が速いメソッドです。このメソッドにより配列関係のエラーが格段に減ります。また上記にあるどのメソッドよりも速く実行できる神のようなメソッドです。

　　　　　public static int ExtraSearch(int[] array , int target)
        {
            array[0] = target; 
            return 0;
        }

実行速度は

　　　　　00:00:00.0000896

このメソッドはとてもスッキリ！！超かんたん！！めっちゃ便利なメソッドです。また、このように実行速度が爆速です。というわけで、私はこのメソッドをおすすめします。

C#探索法はExtraSearchメソッドで探索するべきです！！

※ネタなので注意

C#の配列の探索について（ネタ）