Fastest way to compare two List

Question

I have two List<CustomObject>, called list1 and list2

public class CustomObject
{
    public string foo { get; set; }
    public string bar{ get; set; }
}

The goal is to generate a new list with all the entries that have been modified/added in list2.

Because these lists can get pretty long, looping through them is not an option ...

Any ideas?

Do you just need to compare object instances, or do you need to perform a deep compare of all the properties? — John Wu, Dec 24 '16 at 03:10
I pretty much just need to compare the value of foo of every list entry. I guess that counts as deep compare then? — CiriousJoker, Dec 24 '16 at 03:12
Is list1 your original list and list2 is the current list after modifications and such? If you're really asking about tracking what has changed within one list over time that's a very different question (and one which has a simpler answer than comparing two lists). — PMV, Dec 24 '16 at 03:17
Yes, list2 is a modified version of list1 and I want to know what has been changed. With my current understanding of the English language I would call that comparing two lists, but if there's a simpler solution, I'd be glad to hear it :) — CiriousJoker, Dec 24 '16 at 03:19
Kindly check my solution if it helps out .http://stackoverflow.com/questions/41117945/sort-list-based-on-name-of-object-in-list/41118984#41118984 — Hameed Syed, Dec 24 '16 at 03:29
You may find your answer in here http://stackoverflow.com/a/17323838/6151144 — Toàn Trí Đỗ, Dec 24 '16 at 03:29
The other option is not to have two lists at all, but to use change tracking strategies like INotifyPropertyChanged and ObservableCollection to record which objects are added or modified, and then just use that list of modifications later. That's basically how Entity Framework identifies updates that need to propagate down to the database. — PMV, Dec 30 '16 at 00:56

score 2 · Accepted Answer · answered Dec 24 '16 at 04:06

Adding another answer to accomodate some additional NFRs that have come up in the comments:

Objects can be identified by a hash code
The list is very big, so performance is an issue
The idea is to compare an old list to a new list to see if any new hash codes have popped up.

You will want to store your objects in a dictionary:

var list = new Dictionary<string, CustomObject>();

When you add them, provide the hash as the key:

list.Add(customObject.Hash, customObject);

To scan for new ones:

var difference = new List<CustomObject>();
foreach (customObject o in newList)
{
    if (oldList.ContainsKey(o.Hash)) difference.Add(o);
}
Log(String.Format("{0} new hashes found.", difference.Count));

By using the Dictionary you take advantage of the way the keys are stored in a hash table. Finding an item in a hash table is faster than just doing a scan & compare sort of thing. I believe this will be O(n*log(n)) instead of O(n^2).

score 1 · Answer 2 · edited May 23 '17 at 12:33

1

Here's a traditional way to do it:

public class CustomObject : IComparable
{
    public string foo { get; set; }
    public string bar{ get; set; }
    public int CompareTo(CustomObject o)
    {
         if (this.foo == o.foo && this.bar == o.bar) return 0;

         //We have to code for the < and > comparisons too.  Could get painful if there are a lot of properties to compare.
         if (this.Foo == o.Foo) return (this.Bar.CompareTo(o.Bar));
         return this.Foo.CompareTo(o.Foo);
    }
}

Then use Linq.Except:

listA.Except(listB)

edited May 23 '17 at 12:33

Community

1
1

answered Dec 24 '16 at 03:25

John Wu

50,556
8
44
80

May I ask why CompareTo has to return an int? I found [this](https://msdn.microsoft.com/en-us/library/system.icomparable.compareto(v=vs.110).aspx), but I don't get how returning -1, 0 and 1 changes anything. Currently, this always produces a "cannot convert bool to int error" – CiriousJoker Dec 24 '16 at 03:33
Oops forgot that detail. Edited. – John Wu Dec 24 '16 at 03:35
Ooh, now it makes sense, completely missunderstood that documentation – CiriousJoker Dec 24 '16 at 03:36
My only worry is that you probably don't want to return 1 whenever the two instances aren't equal. I'm thinking that would do bad things if you ever used, say, `.Sort()`. Is it worth the trouble to come up logic for < and > for you? – John Wu Dec 24 '16 at 03:48
I don't quite get what you mean with that last sentence, but I'm comparing hashes of a bunch of files, and if hashxyz isn't present in list1, the file has to be downloaded – CiriousJoker Dec 24 '16 at 03:51
Well if there is only one property worth comparing (the hash string) then the solution is trivial. – John Wu Dec 24 '16 at 03:53

Fastest way to compare two List

2 Answers2