字典查找(O(1))vs Linq在哪里

Question

什么是更快,我应该牺牲Linq标准来实现速度(假设字典查找真的更快)？那么让我详细说明一下:

我有以下内容:

List<Product> products = GetProductList();

我需要根据某些属性搜索产品,例如序列号.我可以先创建一个字典,然后填充如下:

Dictionary<string, Product> dict = new Dictionary<string, Product>();
foreach(Product p in products)
{
    dict.Add(p.serial, p);
}

在找到产品的时候,利用字典查找提供的O(1):

string some_serial = ...;
try { Product p = dict[some_serial]; } catch(KeyNotFoundException) { }

或者,使用Linq:

Product p = products.Where(p => p.serial.Equals(some_serial)).FirstOrDefault();

Dict方法的缺点当然是这需要更多的内存空间,更多的代码来编写,更不优雅等等(尽管这大部分是有争议的).假设这是非因素.我应该采取第一种方法吗？

最后,我想确认上面的Linq方法的复杂性是否确实是O(n),我不知道它是如何更好的.

Answer 1

假设您从一个对象的枚举开始,并且只执行一次...

执行该Where方法会更快,而不是添加到a Dictionary<TKey,TValue>然后再查找它.原因是字典方法不是 O(1).在这种情况下,您将向字典中添加项目,然后进行查找.添加部分是O(N),它Where与具有额外内存开销的方法一样昂贵.

要注意的另一个小问题是,这Dictionary<TKey,TValue>不是真正的O(1).它改为接近O(1),但在某些情况下会降低性能较差(例如许多冲突键).