字典查找（O（1））vs Linq其中 [英] Dictionary Lookup (O(1)) vs Linq where

问题描述

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

我有以下内容：

 列表< ;产品与GT; products = GetProductList（）; 
  

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

 字典<字符串，产品> dict = new Dictionary< string，Product>（）; 
 foreach（产品p在产品中）
 {
 dict.Add（p.serial，p）; 
} 
  

当找到产品的时候，利用提供的O（1）通过字典查找：

  string some_serial = ...; 
 try {Product p = dict [some_serial]; } catch（KeyNotFoundException）{} 
  

或者使用Linq：

 产品p = products.Where（p => p.serial.Equals（some_serial））。FirstOrDefault（）; 
  

Dict方法的缺点当然是需要更多的内存空间，更多的代码写，不太优雅等（虽然大部分是有争议的）。假设这是非因素。我应该采取第一种方法吗？

总而言之，我想确认上述Linq方法的复杂性是否确实是O（n），我看不到怎么可以比这更好。

解决方案

假设你是从对象的枚举开始，只有这样做一次...

执行 Where 方法而不是添加到 Dictionary< TKey，TValue> 然后查看它备份。原因是字典方法是不 O（1）。在这种情况下，您将项目添加到字典，然后查找。添加部分是O（N），它与 Where 方法一样昂贵，额外的内存开销。

另一个小小的注意事项是 Dictionary< TKey，TValue> 不是真正的O（1） 。它接近O（1），但是在某些情况下（例如许多冲突键）可以降级到较低的性能。

What is faster and should I sacrifice the Linq standard to achieve speed (assuming Dictionary lookup is truly faster)? So let me elaborate:

I have the following:

List<Product> products = GetProductList();

I have a need to search for a product based on some attribute, for example, the serial number. I could first create a dictionary, and then populate it as follow:

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

When it's time to find a product, take advantage of O(1) offered by the Dictionary look-up:

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

Alternatively, using Linq:

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

The drawback with the Dict approach is of course this requires more space in memory, more code to write, less elegant, etc (though most of this is debatable). Assume that's non-factor. Should I take the first approach?

To conclude, I would like to confirm if the complexity of the Linq approach above is indeed O(n) and I don't see how it can be better than that.

解决方案

Assuming you are starting with an enumeration of objects and are only doing this once ...

It will be faster to do the Where method as opposed to adding to a Dictionary<TKey,TValue> and then looking it back up. The reason why is that the dictionary method is not O(1). In this scenario you are adding items to the dictionary and then looking it up. The adding part is O(N) which is just as expensive as the Where method with additional memory overhead.

Another minor point to be aware of is that Dictionary<TKey,TValue> is not truly O(1). It instead approaches O(1) but can degrade to lesser performance in certain circumstances (lots of clashing keys for instance).

这篇关于字典查找（O（1））vs Linq其中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！