.NET集合提供了最快的search

我有60K项目需要检查20K查找列表。 是否有一个集合对象(如ListHashTable )提供了一个exception快速的Contains()方法? 或者我将不得不写我自己的? 换句话说,是默认的Contains()方法只是扫描每个项目或使用更好的searchalgorithm。

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

注意 。 查找列表已经sorting。

在最一般的情况下,考虑System.Collections.Generic.HashSet作为默认的“Contains”主力数据结构,因为需要花费不变的时间来评估Contains

“什么是最快可search的集合”的实际答案取决于您的具体数据大小,有序性,散列成本和search频率。

如果您不需要sorting,请尝试使用HashSet<Record> (.NET 3.5新增function)

如果是这样,请使用List<Record>并调用BinarySearch

你有没有考虑List.BinarySearch(item)

你说你的大集合已经被分类了,所以这看起来是个绝好的机会? 哈希值肯定会是最快的,但这会带来自己的问题,并需要更多的开销来存储。

你应该阅读这个博客 ,速度testing几个不同types的集合和方法,每个使用单线程和multithreading技术。

根据调查结果,一个名单上的BinarySearch和SortedList是performance最出色的performance者,当把某些东西看作是一种“价值”的时候,他们一直在徘徊。

当使用允许“键”的集合时,Dictionary,ConcurrentDictionary,Hashset和HashTablesperformance得最好。

保持这两个列表x和ysorting顺序。

如果x = y,则执行操作,如果x <y,则前进x,如果y <x,则前进y直到任一列表为空。

该交点的运行时间与min(size(x),size(y))成正比

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

如果可以对项目进行sorting,那么有一个更快的方法来做到这一点,然后做一个哈希表或B – 树的关键查找。 虽然如果你的物品不能sorting,你不能真的把它们放进一棵b-tree。

无论如何,如果可以对这两个列表进行sorting,那么这只是按顺序查找列表的问题。

 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 

如果你不担心嘎吱嘎嘎的每一个性能最后一点使用HashSet或二进制search的build议是可靠的。 你的数据集不够大,99%的时间都会成为问题。

但是,如果这只是成千上万次这样做的一个performance,并且性能是至关重要的(并且使用HashSet /二进制search已经certificate是不可接受的),那么您可以自己编写自己的algorithm,在执行比较时按照您的要求进行比较。 每个列表最多只能走一次,在病态情况下也不会太差(一旦你走了这条路线,你可能会发现,比较,假设它是一个string或其他非整数值,将是真正的花费和那优化那将是下一个步骤)。

如果你使用的是.Net 3.5,你可以使用下面的代码清理代码:

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

我没有.Net 3.5在这里,所以这是未经testing的。 它依赖于扩展方法。 不是说LookupCollection.Intersect(LargeCollection)可能与LargeCollection.Intersect(LookupCollection)不一样…后者可能慢得多。

这假设LookupCollection是一个HashSet