C#,List <T> .Contains() - 太慢了？

Question

谁能解释一下为什么泛型列表的Contains()函数如此之慢？
我有一个包含大约一百万个数字的列表,以及不断检查这些数字中是否有特定数字的代码.
我尝试使用Dictionary和ContainsKey()函数做同样的事情,它比List快了大约10-20倍.
当然,我并不是真的想为此目的使用Dictionary,因为它并不意味着以这种方式使用.
所以,这里真正的问题是,List.Contains()有什么替代方法,但不像Dictionary.ContainsKey()那样糟糕吗？
提前致谢!

Answer 1

如果你只是检查是否存在,HashSet<T>在.NET 3.5中你是最好的选择 - 字典式的性能,但没有键/值对 - 只是值:

    HashSet<int> data = new HashSet<int>();
    for (int i = 0; i < 1000000; i++)
    {
        data.Add(rand.Next(50000000));
    }
    bool contains = data.Contains(1234567); // etc

Answer 2

List.Contains是一个O(n)操作.

Dictionary.ContainsKey是一个O(1)操作,因为它使用对象的哈希码作为键,这使您可以更快地搜索.

我认为拥有一个包含一百万个条目的List是个好主意.我不认为List类是为此目的而设计的.:)

是不是可以将这些millon实体保存到例如RDBMS中,并对该数据库执行查询？

如果不可能,那么无论如何我都会使用词典.

Answer 3

我想我有答案!是的,列表(数组)中的Contains()确实是O(n),但如果数组很短并且您使用的是值类型,那么它仍然应该非常快.但是使用CLR Profiler [从Microsoft免费下载],我发现Contains()是装箱值以便比较它们,这需要堆分配,这非常昂贵(慢).[注意:这是.Net 2.0; 其他.Net版本未经测试.]

这是完整的故事和解决方案.我们有一个名为"VI"的枚举,并创建了一个名为"ValueIdList"的类,它是VI对象列表(数组)的抽象类型.最初的实现是在古老的.Net 1.1天,它使用了封装的ArrayList.我们最近在http://blogs.msdn.com/b/joshwil/archive/2004/04/13/112598.aspx中发现,通用列表(List <VI>)在值类型上比ArrayList执行得更好(比如我们的枚举VI)因为值不必加框.这是真的,它几乎可以工作.

CLR Profiler发布了一个惊喜.以下是分配图的一部分:

• ValueIdList ::包含bool(VI)5.5MB(34.81%)
• Generic.List ::包含bool(<UNKNOWN>)5.5MB(34.81%)
• Generic.ObjectEqualityComparer <T> :: Equals bool(<UNKNOWN> <UNKNOWN>)5.5MB(34.88%)
• 值.VI 7.7MB(49.03%)

正如您所看到的,Contains()令人惊讶地调用Generic.ObjectEqualityComparer.Equals(),这显然需要装入VI值,这需要昂贵的堆分配.奇怪的是,微软将消除列表中的拳击,只是再次要求它进行简单的操作,如此.

我们的解决方案是重新编写Contains()实现,在我们的例子中很容易做到,因为我们已经封装了通用列表对象(_items).这是简单的代码:

public bool Contains(VI id) 
{
  return IndexOf(id) >= 0;
}

public int IndexOf(VI id) 
{ 
  int i, count;

  count = _items.Count;
  for (i = 0; i < count; i++)
    if (_items[i] == id)
      return i;
  return -1;
}

public bool Remove(VI id) 
{
  int i;

  i = IndexOf(id);
  if (i < 0)
    return false;
  _items.RemoveAt(i);

  return true;
}

VI值的比较现在在我们自己的IndexOf()版本中完成,它不需要装箱,而且速度非常快.在这个简单的重写后,我们的特定程序加速了20%.O(n)......没问题!只是避免浪费内存使用!

Answer 4

字典并不是那么糟糕,因为字典中的键被设计为快速找到.要在列表中查找数字,需要遍历整个列表.

当然,只有当您的数字是唯一且没有订购时,字典才有效.

我认为HashSet<T>.NET 3.5中还有一个类,它也只允许使用独特的元素.