NET 集合提供的搜索速度最快

我有6万项目，需要检查对2万查找列表。是否有一个集合对象(如 List，HashTable)提供了一个异常快速的 Contains()方法？还是我自己写？换句话说，是默认的 Contains()方法只是扫描每个项目，还是使用更好的搜索算法。

foreach (Record item in LargeCollection)
{
if (LookupCollection.Contains(item.Key))
{
// Do something
}
}

注意 。查找列表已经排序。

149505 次浏览
小开
最佳答案

在最一般的情况下，考虑将 System.Collections.Generic.HashSet作为默认的“包含”主力数据结构，因为计算 Contains需要恒定的时间。

“什么是可搜索的最快集合”的实际答案取决于您的特定数据大小、有序性、哈希成本和搜索频率。

小开

如果您不需要订购，请尝试 HashSet<Record>(.Net 3.5的新版本)

如果需要，请使用 List<Record>并调用 BinarySearch。

小开

你考虑过 List.BinarySearch(item)吗？

你说你的大型收藏品已经分类好让这看起来是个完美的机会？散列肯定是最快的，但是这会带来自己的问题，并且需要更多的存储开销。

小开

如果您不担心性能的每一个细节，那么使用 HashSet 或二进制搜索的建议是可靠的。您的数据集不够大，因此99% 的情况下都会出现这个问题。

但是，如果这只是千百次中的一次，而且性能很关键(并且使用 HashSet/二进制搜索被证明是不可接受的) ，那么您当然可以编写自己的算法，在进行排序列表时进行比较。每个列表最多只能被遍历一次，在病理情况下也不会很糟糕(一旦你走这条路，你可能会发现，假设它是一个字符串或其他非整数值，比较将是真正的开销，优化将是下一步)。

小开

如果可以对项目进行排序，那么有一种更快的方法可以做到这一点，那就是在哈希表或 b 树中进行键查找。虽然如果你的项目不能分类，你不能真正把它们放到一个 b-树反正。

无论如何，如果两个列表都是可排序的，那么只需按顺序遍历查找列表即可。

Walk lookup list
While items in check list <= lookup list item
if check list item = lookup list item do something
Move to next lookup list item
小开

如果你使用.Net 3.5，你可以使用:

foreach (Record item in LookupCollection.Intersect(LargeCollection))
{
//dostuff
}

我没有。这里净3.5，所以这是未经测试的。它依赖于一种扩展方法。不是说 LookupCollection.Intersect(LargeCollection)可能不同于 LargeCollection.Intersect(LookupCollection)... 后者可能要慢得多。

这假定 LookupCollection 是 HashSet

小开

保持列表 x 和 y 的排序顺序。

如果 x = y，做你的动作，如果 x < y，x 前进，如果 y < x，y 前进，直到任一列表为空。

这个交集的运行时间与 min (size (x) ，size (y))成正比

不要 运行一个. Contains()循环，这与 x * y 成正比，x * y 更糟糕。

小开

您应该阅读使用单线程和多线程技术对几种不同类型的集合和方法进行快速测试的 这个博客。

根据调查结果，BinarySearch on a List 和 SortedList 是表现最好的两个搜索工具，它们在查找“值”时总是紧密相连。

当使用允许“键”的集合时，Dictionary、 ConcurrentDictionary、 Hashset 和 HashTables 的总体表现最好。

小开

我做了个测试:

  • 前三个字符都是 A-Z0-9的可能组合
  • 用这些字符串填充这里提到的每个集合
  • 最后-搜索每个集合的随机字符串并计算时间(每个集合使用相同的字符串)。

这个测试在保证有结果的情况下模拟查找。

FullCollection

然后我将最初的集合从所有可能的组合改为只有10,000个随机的3个字符组合，这应该会导致一个随机3个字符查找的1/4.6命中率，因此这是一个不能保证结果的测试，并再次运行测试:

PartialCollection

恕我直言，HashTable 虽然速度最快，但并不总是最方便的; 处理对象。但是 HashSet 紧随其后，它可能是值得推荐的。

只是为了好玩(你知道有趣) ，我跑了1.68 M 行(4个字符) : BiggerCollection


提交答案