Best way of checking content of Generic List

Question

I have to work on some code that's using generic lists to store a collection of custom objects.

Then it does something like the following to check if a given object's in the collection and do something if so:

List<CustomObject> customObjects;
//fill up the list
List<CustomObject> anotherListofCustomObjects;
//fill it up

//...

foreach (CustomObject myCustomObject in customObjects)
{
   if (anotherListofCustomObjects.Contains(myCustomObject))
   {
      //do stuff
   }
}

Problem is is taking forever to process 7000 objects like that.

This is not my code - I am just trying to come up options to improve it - Looks to me it would be much faster to use a dictionary to get the stuff by key instead of looping through the whole collection like the above.

Suggestions?

Answer 1

Why don't you use a dictionary ?

Can you show how CustomObject is implemented ? Does CustomObject implement IEquatable ?

Answer 2

Well, you seem to have answered it yourself? If you need fast query against a set of data, then a dictionary may be better than a flat list (for largish data sizes, which yours is).

You could, for example, use the object as its own key -

Dictionary<CustomObject,CustomObject> ...

Note that the meaning of equality depends on the context. If you are passing in the original reference, then that is fine - ContainsKey would do the job. If you have a different but similar-for-the-purposes-of-equality object to compare to, then you'll need to implement your own GetHashCode(), Equals(), and ideally IEquatable<CustomObject>. Either in CustomObject itself, or in a custom IEqualityComparer<CustomObject>.

Answer 3

Indeed your code is O(n^2) currently, which will be slow. You can:

• use dictionaries or KeyedCollections instead, this will make it O(nlog n)
• if you can assure that the items are in the same order, you can rewrite the last loop to use just one index, and this would be O(n)

Answer 4

Another way besides dictionaries is, if you're on .NET 3.5, to use Linq to objects and Intersect:

foreach(CustomObject c in customObjects.Intersect(anotherListOfCustomObjects))
{
    // do stuff.
}

According to reflector, it uses Hash-based sets to perform the intersection of the sequences.

Answer 5

If you must maintain two separate lists, one of the Set types might be faster (using a Join operation). Some of the available libraries are

1. IESI Collections
2. PowerCollections
3. C5

Answer 6

Just a minor addition to the other comments. If you need the other list of customers to be sorted you could use a SortedList.

Answer 7

You might also consider System.Collections.ObjectModel.KeyedCollection<TKey, TItem>.

To supplement this, I usually create my own IKeyable interface and a specific implementation of KeyedCollection that uses IKeyable for the required overload.

Answer 8

Tests are your friend. The size of the collection determines witch Data Structure/algorithm you should use. I suggest you do some performance benchmarks on the following options:

1. Your current solution
2. Use a BinarySearch algorithm in your sorted List.
3. Use a HashSet<CustomObject>.

Given the number of elements I suspect that the HashSet<CustomObject> is the way to go.

Answer 9

Hashset work great too.

new HashSet<CustomObject>().Join()