set equality in linq

Question

I have two lists A and B (List). How to determine if they are equal in the cheapest way? I can write something like '(A minus B) union (B minus A) = empty set' or join them together and count amount of elements, but it is rather expensive. Is there workaround?

Answer 1

A first shot - if they contain the same items, the union of both list should have the same number of items as any of both lists.

listA.Union(listB).Count() == listA.Count()

Note: Fails if one list is empty.

But it's probably still a O(n²) operation.

Another solution - the lists must have the same length and list A minus list B must not contain any elements.

(listA.Count() == listB.Count()) && !listA.Except(listB).Any()

Answer 2

If you are working in c# 3.0 you can write an extension method that loops through all items in each list and compares them individually. Compare the lengths for equality first.

You can then call it like this:

bool result = listA.Equals(listB);

Answer 3

It depends on what you mean by "the list are equal". If you mean they contain the same objects, the solution suggested by Daniel is fine, just Union() the two list and count the items.

If by "equal" you mean that they have the same items in the same order, you'd be better off comparing the Count of both lists, then if they have the same count, just iterate with a plain for loop to compare each element from both lists at the same index. Less pretty but you can hardly be faster.

Answer 4

There isn't a shortcut here, really, unless the lists are sorted, in which case you can compare the elements one-by-one. And obviously I assume that order doesn't matter, or else it's obvious that you can compare them one-by-one then too.

Otherwise, I'd suggest that the most efficient algorithm you could get for large lists of items would probably be something like this, using a hash table to keep track of what you've seen (warning: haven't tested, but it should be clear what I'm getting at.)

public static bool IsEqual<T>(this List<T> x1, List<T> x2)
{
    if(x1.Count != x2.Count) return false;

    var x1Elements = new Dictionary<T, int>();

    foreach(var item in x1)
    {
        int n; x1Elements.TryGetValue(item, out n);
        x1Elements[item] = n+1;
    }

    foreach(var item in x2)
    {
        int n; x1Elements.TryGetValue(item, out n);
        if(n <= 0) return false; // this element was in x2 but not x1
        else x1Elements[item] = n-1;
    }

    // make sure x1 didn't have any elements
    // that weren't in x2

    return x1Elements.Values.All(x => x == 0);
}

Answer 5

Well, that depends on how you interpret your lists.

If you consider them as tuples (so the order of elements in lists matters), then you can go with this code:

    public bool AreEqual<T>(IList<T> A, IList<T> B)
    {
        if (A.Count != B.Count)
            return false;
        for (int i = 0; i < A.Count; i++)
            if (!A[i].Equals(B[i])) 
                return false;
    }

If you consider your lists as sets (so the order of elements doesn't matter), then... you are using the wrong data structures I guess:

    public bool AreEqual<T>(IList<T> A, IList<T> B)
    {
        HashSet<T> setA = new HashSet<T>(A);
        return setA.SetEquals(B);
    }

Answer 6

Alsin, try this:

Comparing two arrays (or IEnumerables) in C#
http://blog.slaven.net.au/archives/2008/03/16/comparing-two-arrays-or-ienumerables-in-c/

Answer 7

If the ordering of the list items is relevant:

bool areEqual = a.SequenceEqual(b);

If the lists are to be treated as unordered sets:

// assumes that the list items are ints
bool areEqual = new HashSet<int>(a).SetEquals(b);

(The SequenceEqual method and the HashSet constructor both have overloads that take an IEqualityComparer parameter, if you need that functionality.)