linq - Dictionary Lookup (O(1)) vs Linq where

Question

什么更快，我应该牺牲 Linq 标准来实现速度（假设字典查找确实更快）？所以让我详细说明：

我有以下内容：

List<Product> products = GetProductList();

我需要根据某些属性搜索产品，例如序列号。我可以先创建一个字典，然后按如下方式填充它：

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

当需要查找产品时，请利用 Dictionary 查找提供的 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)，我看不出它会比这更好。

score 8 · Accepted Answer

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

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

另一个需要注意的小问题是，这Dictionary<TKey,TValue>并不是真正的 O(1)。相反，它接近 O(1)，但在某些情况下可能会降低性能（例如很多冲突的键）。

1 回答 1