我想找出数组的字典查找和二进制搜索查找之间的权衡点。我期待字典的恒定时间查找,以及二进制搜索的对数时间查找,具体取决于集合的大小,二进制搜索对于较小的集合执行得更好。
然而,当我看到以下结果时,我感到很惊讶:
令我惊讶的是: 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;
}
}
}
最佳答案
(与评论中提到的差不多。)
我怀疑您看到的主要是缓存未命中的影响。当集合很大时,您会遇到很多缓存未命中 - 特别是使用二分查找时,它可能需要接触集合中的很多点才能找到一个元素。
在较小的尺寸下,我怀疑您也看到了缓存未命中,但这次是在您的 targets
列表中 - 以及 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
更快的随机数生成器,如果你可以找到一个。或者使用其他方式确定要查找的元素。
哦,我个人会重写二进制搜索以使用迭代而不是递归,但那是另一回事。我不认为它会产生重大影响。
关于c# - 二进制搜索和哈希表搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19374092/