Working with a large list of Objects, need better (sorted) performance

Question

I have a huge (~100,000) collection of objects over which I have no control (let's call this masterList). They are simple with several fields

public class TheirObject{
public String GUID;
public int blah1;
public string blah2;
...
}

I have another collection of tens of thousands of GUIDs (as a List of Strings) I need to, for every GUID in my list, create a sublist of TheirObjects which contain whichever TheirObjects in the masterList have the same GUIDs.

Here is some simple code That does this:

 List<String> GUIDs;
 List<TheirObject> masterList;
 List<TheirObject> filteredList;
 foreach(String GUID in GUIDs)
 {
      filteredList = new List<TheirObject>();
      foreach(TheirObject tho in masterList)
           if(tho.GUID == GUID)
                filteredList.Add(tho);
      //do stuff with filteredList
 }

However, this takes hours! I am sure that there is a much faster way to do it, perhaphs involving sorted lists, then binary search lookups, but I can't figure out how to do it in c#. Several TheirObjects will have the same GUID in the masterList, so I don't think I can use SortedList. Help!

Don't know if this is a possibility for you, but this is exactly the thing that databases do well. — Steve G
– Steve G, Commented Sep 24, 2014 at 19:03
could you not do or use List<T>.foreach() and do it as a delegate or use a lambda ? — MethodMan
– MethodMan, Commented Sep 24, 2014 at 19:05
@DJKRAZE That would improve nothing at all about the program. It'd add a tiny bit of overhead without making any real functional change. — Servy
– Servy, Commented Sep 24, 2014 at 19:09
Then I would suggest that he do a Lookup or even easier use a Database Query.. — MethodMan
– MethodMan, Commented Sep 24, 2014 at 19:10
I understand that using a database would be ideal but I cannot use one in this situation (restricted toolset on this work system) — Aaron
– Aaron, Commented Sep 24, 2014 at 19:50

driis · Accepted Answer · 2014-09-24 19:06:31Z

12

The straight forward code approach with LINQ would be something like:

var lookup = masterList.ToLookup(tho => tho.GUID);
// Now you have a hash-table based lookup containing the lists of TheirObject grouped by GUID
foreach(string GUID in GUIDs)
{
    filteredList = lookup[GUID].ToList();
    // Do your stuff with filteredList
}

The key here is not iterating the huge list multiple times, which is what kills performance. Instead, iterate through it once and build an efficient lookup. This initial build will take some time, subsequent lookups will take almost no time and (close to) O(1).

Now if the list is really huge and memory constraints does not allow you to build a datastructure more suited for lookups, I would probably try to offload the work to a database, as suggested in the comments.

answered Sep 24, 2014 at 19:06

driis

165k46 gold badges272 silver badges345 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Aaron Over a year ago

This looks great, going to try it!

Aaron Over a year ago

WOW! this code was done in ~1min. What an improvement!

Bastyon Jun 2 at 16:14

love this solution

Collectives™ on Stack Overflow

Working with a large list of Objects, need better (sorted) performance

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related