System.Array#BinarySearchとSystem.Array#IndexOfの違い

プログラミングC# p178

• Binary Searchはソートされていないと使えないが、Index Ofはソートされていなくても使える。
• オーダは、Binary Searchは件数のlog2に比例、Index Ofは件数に比例(だと思う)、のため、件数が多いほどBinary Searchの方が速くなる傾向にある。

こんなところでしょう。
で、試しにこんなコードを書いてみる。

using System;

class ArrayTest
{
        private const int ARRAY_SIZE = 50000;
        static void Main(string[] args)
        {
                int[] iArray = new int[ARRAY_SIZE];
                for(int i=0; i<iArray.Length; i++)
                {
                        iArray[i] = i;
                }

                Random r = new Random();

                // Binary Search
                DateTime t1 = DateTime.Now;
                for(int i=0; i<iArray.Length; i++)
                {
                        Array.BinarySearch(iArray, r.Next() % ARRAY_SIZE);
                }
                DateTime t2 = DateTime.Now;
                Console.WriteLine("Binary Search: {0}", t2.Subtract(t1));

                // Index Of
                DateTime t3 = DateTime.Now;
                for(int i=0; i<iArray.Length; i++)
                {
                        Array.IndexOf(iArray, r.Next() % ARRAY_SIZE);
                }
                DateTime t4 = DateTime.Now;
                Console.WriteLine("Index Of: {0}", t4.Subtract(t3));
        }
}

僕のマシンで実行した結果はこんな感じ。

Binary Search: 00:00:00.0156250
Index Of: 00:00:04.5625000

Binary Searchは一瞬で終わってますが、Index Ofの方は4秒ほどかかってますね。

ちなみにJavaにもBinary Searchあります。IndexOfは無かったので、適当に実装。

import java.util.*;

public class ArrayTest
{
        private static final int ARRAY_SIZE = 50000;
        public static void main(String[] args)
        {
                int[] iArray = new int[ARRAY_SIZE];
                for(int i=0; i<iArray.length; i++)
                {
                        iArray[i] = i;
                }

                Random r = new Random();

                // Binary Search
                long t1 = System.currentTimeMillis();
                for(int i=0; i<iArray.length; i++)
                {
                        Arrays.binarySearch(iArray, r.nextInt() % ARRAY_SIZE);
                }
                long t2 = System.currentTimeMillis();
                System.out.println("Binary Search: " + (t2 - t1));

                // Index Of
                long t3 = System.currentTimeMillis();
                for(int i=0; i<iArray.length; i++)
                {
                        intArrayIndexOf(iArray, r.nextInt() % ARRAY_SIZE);
                }
                long t4 = System.currentTimeMillis();
                System.out.println("Index Of: " + (t4 - t3));
        }

        private static int intArrayIndexOf(int[] iArray, int key)
        {
                for(int i=0; i<iArray.length; i++)
                {
                        if(iArray[i] == key)
                        {
                                return i;
                        }
                }

                return -1;
        }
}

実行するとこんな感じ。

Binary Search: 15
Index Of: 7907

やっぱりBinary Searchは一瞬で終わってますが、Index Ofの方は時間かかってますね。

ちなみにRubyには標準ではBinary Searchないらしい。
あのBinary Hacksの人がライブラリ作って公開しているみたいです。
http://0xcc.net/ruby-bsearch/
つか、それくらい自分で書けよってことか。。