二分查找和哈希表查找

Question

我想要找出字典查找和二分查找数组之间的权衡点。我期望字典查找具有常数时间，而二分查找根据集合大小具有对数时间，对于较小的集合，二分查找的性能更好。

然而，当我看到以下结果时，我感到惊讶： 我对以下事情感到惊讶：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;
        }
    }
}

- John Tseng

---

你到底感到惊讶的是什么？字典搜索不是完全恒定的事实吗？还是字典即使对于小集合也能获胜的事实？请注意，通过迭代大型列表，您最终会遇到很多缓存未命中，仅仅是为了迭代而已。 - Jon Skeet

@JonSkeet 很好的提点。我已经澄清了我的问题，并解释了对我来说什么是令人惊讶的。 - John Tseng

我不会说二分查找呈指数增长 - 至少，如果你的x轴是对数轴，它并不明显。将其绘制在线性x轴上，可能会更清晰明了。说实话，其余部分可能仅通过缓存未命中来解释 - 集合越大，即使是名义上的常数时间查找，也会有更多的缓存未命中。 - Jon Skeet

换句话说，这些查找的时间复杂度计算通常假定每个内存读取的代价相同。但是当一些读取未命中缓存而其他读取则不是这种情况并非如此。 - Jon Skeet

@JonSkeet，你太快了。我在评论后立即修复了指数部分。缓存问题可能会解释为什么两个算法在相同的点开始变慢。 - John Tseng

好的。这就留下了“为什么对于单个项目集合，二分查找和哈希速度相同”的问题 - 在这一点上，我认为你正在迭代一个巨大的列表，这会影响你的结果，因为你会有缓存未命中，我怀疑这将使其他所有东西都变得微不足道。 - Jon Skeet

Answer 1

（与评论中所述基本相同。）我怀疑您主要看到的是缓存未命中的影响。当集合很大时，您将遇到许多缓存未命中-特别是对于二进制搜索，它可能需要触及集合中的许多点才能找到元素。

在较小的大小上，我认为您也会看到缓存未命中，但这次是在您的“目标”列表上-以及LINQ本身的开销。 LINQ很快，但当您只在中间执行单个小集合的搜索时，它仍然可以显着影响性能。

我建议将您的循环重写为以下内容：

{
    // 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 更快的随机数生成器。或者使用其他方式来确定要查找的元素。

另外，我个人会重写二分查找以使用迭代而不是递归，但这是另外一个问题。我不认为这会产生显著影响。

- Jon Skeet

---

正如你所预测的那样，迭代二分查找并没有产生显著的影响。 - John Tseng

@JonSkeet 我个人会重写二分查找算法，使用迭代而非递归 为什么？ - Juan M. Elosegui

@JuanM.Elosegui：为什么无缘无故地使用堆栈？在这里递归没有任何好处——循环二分查找很容易编写，并且具有更小的堆栈溢出风险。 - Jon Skeet