4

ディクショナリ ルックアップと配列のバイナリ サーチ ルックアップの間のトレードオフ ポイントを見つけたかったのです。コレクションのサイズに応じて、ディクショナリの一定時間のルックアップと、バイナリ検索の対数時間のルックアップを期待していました。

しかし、次の結果を見て驚きました。 二分探索は指数関数的に成長し、ハッシュルックアップはゆっくりと成長する

私は驚いた: 1. 二分探索は、最初は対数的に成長し、その後、はるかに速く成長します。2. ハッシュは最初はかなり一貫していますが、その後ゆっくりと成長し始めます。3. 二分探索は、ハッシュ ルックアップより優れていることはありません。以下は私のコードです。私は何を間違えましたか？

class Program
{
    static void Main(string[] args)
    {
        var r = new Random();
        var targets = Enumerable.Range(0, 1000 * 1000).Select(_ => r.Next(int.MaxValue)).ToList();

        for (int totalCount = 1; totalCount < 1000*1000*10; totalCount*=2)
        {
            var a = Enumerable.Range(0, totalCount).Select(_ => r.Next(int.MaxValue)).Distinct().Select(v => new thing(v)).OrderBy(t => t.value).ToArray();
            var d = a.ToDictionary(t => t.value);

            var watch = new System.Diagnostics.Stopwatch();

            {
                watch.Start();
                var found = targets.Select(t => BinarySearch(t, a)).Where(t => t != null).Count();
                watch.Stop();
                Console.WriteLine(string.Format("found {0} things out of {2} in {1} ms with binary search", found, watch.ElapsedMilliseconds, a.Length));
            }
            {
                watch.Restart();
                var found =  targets.Select(t => HashSearch(t, d)).Where(t => t != null).Count();
                watch.Stop();
                Console.WriteLine(string.Format("found {0} things out of {2} in {1} ms with hash search", found, watch.ElapsedMilliseconds, d.Keys.Count));
            }
        }
        Console.ReadLine();
    }

    static thing HashSearch(int needle, Dictionary<int, thing> hash)
    {
        if (!hash.ContainsKey(needle))
            return null;
        return hash[needle];
    }

    static thing BinarySearch(int needle, thing[] sortedHaystack)
    {
        return BinarySearch(needle, sortedHaystack, 0, sortedHaystack.Length - 1);
    }
    static thing BinarySearch(int needle, thing[] sortedHaystack, int minimum, int maximum)
    {
        if (minimum > maximum)
            return null;
        var middle = (minimum + maximum) / 2;
        if (needle == sortedHaystack[middle].value)
            return sortedHaystack[middle];
        if (needle < sortedHaystack[middle].value)
            return BinarySearch(needle, sortedHaystack, minimum, middle - 1);
        return BinarySearch(needle, sortedHaystack, middle + 1, maximum);
    }

    class thing
    {
        public int value;
        public thing(int v)
        {
            value = v;
        }
    }
}
4

1 に答える 1

3

（コメントで指摘されたとおりです。）

ほとんどの場合、キャッシュ ミスの影響が見られると思います。コレクションが大きい場合、多くのキャッシュ ミスが発生します。特にバイナリ検索では、要素を見つけるためにコレクション内の多くのポイントに触れる必要がある可能性があります。

小さいサイズでは、キャッシュ ミスも見られると思いますが、今回はtargetsリストにあり、LINQ 自体のオーバーヘッドも見られます。LINQ は高速ですが、途中で小さなコレクションを 1 回検索するだけの場合は、依然として重要です。

ループを次のように書き直すことをお勧めします。

{
    // Use the same seed each time for consistency. Doesn't have to be 0.
    Random random = new Random(0);
    watch.Start();
    int found = 0;
    for (int i = 0; i < 1000 * 1000; i++)
    {
        if (BinarySearch(t, random.Next(int.MaxValue)) != null)
        {
            found++;
        }
    }
    watch.Stop();
    Console.WriteLine(string.Format
         "found {0} things out of {2} in {1} ms with binary search",
         found, watch.ElapsedMilliseconds, a.Length));
}

もちろん、代わりに乱数生成をループに含めるという問題があります...乱数ジェネレーターをSystem.Random見つけることができる場合よりも高速な乱数ジェネレーターの使用を検討することをお勧めします。または、検索する要素を決定する他の方法を使用します。

ああ、私は個人的に二分探索を再帰ではなく反復を使用するように書き直しますが、それは別の問題です。大きな効果があるとは思えません。

于 2013-10-15T06:19:05.230 に答える