17

I have two list of members like this:

Before: Peter, Ken, Julia, Tom

After: Peter, Robert, Julia, Tom

As you can see, Ken is is out and Robert is in.

What I want is to detect the changes. I want a list of what has changed in both lists. How can linq help me?

1
  • 2
    I think you need to define "change" a little more. Is a change in order of items a "change" to you, for example? Mar 8, 2010 at 20:02

4 Answers 4

29

Your question is not completely specified but I assume that you are looking for the differences as sets (that is, ordering does not matter). If so, you want the symmetric difference of the two sets. You can achieve this using Enumerable.Except:

before.Except(after).Union(after.Except(before));
0
22

As an alternative to linq answers, which have to pass both lists twice, use HashSet.SymmetricExceptWith():

var difference = new HashSet(before);
difference.SymmetricExceptWith(after);

Could be considerably more efficient.

5

Another way:

before.Union(after).Except(before.Intersect(after))
2

Here is the version having O(n) complexity, provided your sequences are both ordered:

    public static IEnumerable<T> SymmetricDifference<T>(IEnumerable<T> coll1, IEnumerable<T> coll2, IComparer<T> cmp)
    {
        using (IEnumerator<T> enum1 = coll1.GetEnumerator())
        using (IEnumerator<T> enum2 = coll2.GetEnumerator())
        {
            bool enum1valid = enum1.MoveNext();
            bool enum2valid = enum2.MoveNext();
            while (enum1valid && enum2valid)
            {
                int cmpResult = cmp.Compare(enum1.Current, enum2.Current);
                if (cmpResult < 0)
                {
                    yield return enum1.Current;
                    enum1valid = enum1.MoveNext();
                }
                else if (cmpResult > 0)
                {
                    yield return enum2.Current;
                    enum2valid = enum2.MoveNext();
                }
                else
                {
                    enum1valid = enum1.MoveNext();
                    enum2valid = enum2.MoveNext();
                }
            }
            while (enum1valid)
            {
                yield return enum1.Current;
                enum1valid = enum1.MoveNext();
            }
            while (enum2valid)
            {
                yield return enum2.Current;
                enum2valid = enum2.MoveNext();
            }
        }
    }


    public static IEnumerable<T> SymmetricDifference<T>(IEnumerable<T> coll1, IEnumerable<T> coll2)
    {
        return SymmetricDifference(coll1, coll2, Comparer<T>.Default);
    }
2
  • 1
    This would work only for sorted sequences, right? One cannot make symdiff in just O(n) for arbitrary sequences.
    – Vlad
    Sep 4, 2012 at 13:55
  • Sure it does, just look at the co-iteration. It is slightly modified version of sequential-merge from merge-sort. Although it will not work for unsorted, it is very efficient for sorted, so in many cases it will be faster and more memory-friendly to pre-sort the collection and then use this filter ~> n + 2*(n log n) instead of some naiive all-vs-all n^2 or some hashtable memory hogs ..in case of many elements of course:) Jan 18, 2013 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.