我想要找出字典查找和二分查找数组之间的权衡点。我期望字典查找具有常数时间,而二分查找根据集合大小具有对数时间,对于较小的集合,二分查找的性能更好。
然而,当我看到以下结果时,我感到惊讶:
我对以下事情感到惊讶:1. 二分查找一开始增长得对数级,然后增长得更快。2. 哈希在一开始相当稳定,但后来也开始缓慢增长。3. 二分查找从未比哈希查找更好。下面是我的代码。我做错了什么?
然而,当我看到以下结果时,我感到惊讶:
![Binary search growing exponentially, and hash lookup growing slowly](https://istack.dev59.com/5TaC6.webp)
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;
}
}
}