I have a class called Product that contains some properties like Id (as Guid) and Messages (as List), and a Message class that also contains Id and other properties. I have all messages in Message table and all products in product table. After getting data of both tables, I want to join them regarding on Id property. If I use the below code as it is linear search the performance is terrible.
foreach (Product product in products)
product.Messages = messages.Where(n => n.Id == product.Id).ToList();
You might be able to speed it up by groupding your messages into a lookup table.
messagesDict = messages .GroupBy(x => x.Id) .ToDictionary(x => x.Id, x.ToList());
or, as John Bustos suggested, you can use ToLookup();
messagesDict = messages .ToLookup(x => x.Id);
you use it like this
//you might have to first check if messagesDict //actually has any messages for your project. product.Messages = messagesDict[product.Id];
Your original attempt is O(nm) where n is the number of projects and m is the number of messages.
Dictionary uses hashing, so from a practical standpoint, you can usually assume that it has close to O(1) inserts, and O(1) searches. Under ideal circumstances,
List<T>.Add is also O(1). This means that if you were to manually create your lookup dictionary, then, you could do it in O(m). I would hope that a built-in function like
ToLookup, achieves the same efficiency.
Once you do that, your algorthim becomes O(n + m)