Faster way to compare two lists of differing objects

Question

I'm comparing two lists to see if one contains a value from the other and vice-versa:

List<customer> NotOnLocal = 
                AllServer.Where(p => !AllLocal.Any(p2 => p2.Reference == p.customerNumber))
                         .ToList();

List<ConnectCustomer> NotOnServer = 
                 AllLocal.Where(p => !AllServer.Any(p2 => p2.customerNumber == p.Reference))
                         .ToList();

This seems to work fine but with over 100,000 objects in each the comparison gets a little slow. Does anyone know if there is a more efficient way to make the comparison and return the respective lists?

score 2 · Accepted Answer · answered May 26 '17 at 10:10

You can use hash sets (assume you are comparing strings) for quick checking if some value is in set (gives you O(1) complexity instead of O(N)):

 var serverCustomerNumbers = new HashSet<string>(AllServer.Select(c => c.customerNumber));
 var localReferences = new HashSet<string>(AllLocal.Select(c => c.Reference));

Now if you need to get whole customer objects

 List<customer> NotOnLocal = 
                    AllServer.Where(c => !localReferences.Contains(c.customerNumber));

Or you can use set operations to get required customer numbers

 var notLocalCustomerNumbers = serverCustomerNumbers.Except(localReferences);

No that speeds things up very nicely (by at least a factor of 10), thanks :) — Dan Hall, May 26 '17 at 11:30

score -1 · Answer 2 · answered May 26 '17 at 10:16

This question goes into the Mathematic area of Set theory: https://en.wikipedia.org/wiki/Set_theory Specifically, a Intersection: https://en.wikipedia.org/wiki/Intersection_(set_theory)

Except for finding those Wikipedia Artikels, that is unfortunatley beyond my knowledge.

You might be able to speed it up computatnionally by making the check easer. But it appears you are alredy matching on a Integer (customerNumber sounds like a Integer Candidate).

Faster way to compare two lists of differing objects

2 Answers2