提高List的性能

本文关键字：性能 List 提高 | 更新日期: 2023-09-27 18:05:26

我有一个名为Product的类，它包含一些属性，比如Id(作为Guid)和Messages(作为List)，还有一个Message类，它也包含Id和其他属性。我在Message表中有所有的消息，在product表中有所有的产品。在获得两个表的数据后，我想在Id属性上连接它们。如果我使用下面的代码，因为它是线性搜索，性能是可怕的。

foreach (Product product in products)
    product.Messages = messages.Where(n => n.Id == product.Id).ToList();

还有其他更快的方法吗?

谢谢

提高List<T>的性能

您可以通过将您的消息分组到查找表中来加快速度。

messagesDict = messages
    .GroupBy(x => x.Id)
    .ToDictionary(x => x.Id, x.ToList());

或者，正如John Bustos建议的，您可以使用tollookup ();

messagesDict = messages
    .ToLookup(x => x.Id);

你可以这样使用

//you might have to first check if messagesDict 
//actually has any messages for your project.
product.Messages = messagesDict[product.Id];

您最初的尝试是O(nm)，其中n是项目的数量，m是消息的数量。

A Dictionary使用哈希，因此从实用的角度来看，您通常可以假设它具有接近O(1)插入和O(1)搜索。理想情况下，List<T>.Add也为O(1)。这意味着如果您要手动创建查找字典，那么您可以在O(m)中进行。我希望像ToLookup这样的内置功能也能达到同样的效率。

一旦你这样做，你的算法变成O(n + m)

您应该在数据库中执行连接。这将产生最好的性能。如果你坚持在c#中这样做，按Id排序产品，先按Id排序消息

按照其他人的指示，在数据库中执行连接。正如你所指出的，线性搜索是O(n)(在这种情况下你实际上做了很多线性搜索);然而，大多数数据库使用B-Tree数据结构(或类似的东西)按主键对行排序。这意味着在主键上的数据库搜索是O(log n)，这显然显著快。(当然，假设Id是主键)。

相关文章：