linq - 字典查找 (O(1)) 与 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会更快方法而不是添加到 Dictionary<TKey,TValue>然后再回头看。原因是字典方法是不是 O(1)。在这种情况下，您将项目添加到字典中，然后进行查找。加法部分是 O(N)，与 Where 一样昂贵具有额外内存开销的方法。

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