字典查找 (O(1)) 与 Linq where
什么更快？我是否应该牺牲 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)，并且我不知道它如何能比这更好。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
假设您从对象枚举开始并且只执行一次...
与添加到
Dictionary< 相比，执行 Where方法会更快/code> 然后查找它。原因是字典方法不是 O(1)。在这种情况下，您将项目添加到字典中，然后进行查找。添加部分的时间复杂度为 O(N)，与Where方法一样昂贵，并具有额外的内存开销。另一个需要注意的小点是
Dictionary并不是真正的 O(1)。相反，它接近 O(1)，但在某些情况下（例如大量冲突的键）可能会降低性能。Assuming you are starting with an enumeration of objects and are only doing this once ...
It will be faster to do the
Wheremethod as opposed to adding to aDictionary<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 theWheremethod 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).