7
\$\begingroup\$

I'm using this code for checking if two List<T> are equal or not:

public static bool EqualsAll<T>(this IList<T> a, IList<T> b)
{
    if (a == null || b == null)
        return (a == null && b == null);

    if (a.Count != b.Count)
        return false;

    EqualityComparer<T> comparer = EqualityComparer<T>.Default;

    for (int i = 0; i < a.Count; i++)
    {
        if (!comparer.Equals(a[i], b[i]))
            return false;
    }

    return true;
}

Now assume that I'm using this code for checking two big lists. Is this code efficient?

\$\endgroup\$
2
  • \$\begingroup\$ Is there a reason that no one here is suggesting Linq? msdn.microsoft.com/en-us/library/bb348567.aspx \$\endgroup\$ Sep 16, 2015 at 12:40
  • \$\begingroup\$ The only caveat is that you have to order the lists first but that should be done before comparing them anyway. \$\endgroup\$ Sep 16, 2015 at 12:41

3 Answers 3

15
\$\begingroup\$

Checking whether two lists are equal is naturally an O(n) operation. So yes, your code looks efficient.

Note that you could also replace your for loop with Enumerable.SequenceEqual

public static bool EqualsAll<T>(this IList<T> a, IList<T> b)
{
    if (a == null || b == null)
        return (a == null && b == null);

    if (a.Count != b.Count)
        return false;

    return a.SequenceEqual(b);
}

If you take a look at its implementation, you'll notice that it's very similar to yours. It might be just a tiny bit less efficient - so if performance is an issue here, measure both approaches, and then weigh readability/maintainability vs performance gains.

On a different note, I would rename the method to SequenceEqual and consider it a "specialization" of Enumerable.SequenceEqual for lists.

I would also consider throwing an exception if either argument is null. This would be consistent with the BCL's own extension methods (Select, Where, ToList, SequenceEqual, Any, All, etc).

\$\endgroup\$
13
  • \$\begingroup\$ +1 nice review. SequenceEqual is very inefficient compared to a for loop though. \$\endgroup\$ Sep 16, 2015 at 9:28
  • 4
    \$\begingroup\$ Since you're only using Count, which is part of ICollection<T>, I'd replace the parameters by ICollection<T>. \$\endgroup\$ Sep 16, 2015 at 10:09
  • \$\begingroup\$ @CodesInChaos Great observation! \$\endgroup\$
    – dcastro
    Sep 16, 2015 at 10:12
  • \$\begingroup\$ Perhaps it'd be a good idea to suggest to MS to dynamically check for ICollection<T> in SequenceEqual for an early out. They do similar checks in other parts of LINQ. \$\endgroup\$ Sep 16, 2015 at 10:15
  • 1
    \$\begingroup\$ @craftworkgames As I remembered it the compiler turned foreach into for loop for both arrays and lists but I trust skeet over my memory. I'll write a benchmark. \$\endgroup\$ Sep 16, 2015 at 14:14
3
\$\begingroup\$

Your code is efficient.

Why not expose an overload allowing the caller to pass in a comparer?

public static bool EqualsAll<T>(this IList<T> a, IList<T> b)
{
    return EqualsAll(a, b, null); // there is a slight performance gain in passing null here.
    // It is how it is done in other parts of the framework.
}

public static bool EqualsAll<T>(this IList<T> a, IList<T> b, IEqualityComparer<T> comparer)
{
    if (a == null || b == null) // I agree with dcastro that throwing probably makes more sense here.
        return (a == null && b == null);

    if (a.Count != b.Count)
        return false;

    if (comparer == null)
        comparer = EqualityComparer<T>.Default;

    for (int i = 0; i < a.Count; i++)
    {
        if (!comparer.Equals(a[i], b[i]))
            return false;
    }

    return true;
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Can you expand a bit on how/why your code is an improvement? \$\endgroup\$
    – Kaz
    Sep 16, 2015 at 9:27
  • 1
    \$\begingroup\$ Not sure what to say really, giving the caller an opportunity to pass in a comparer of choice feels natural given how it is done in the framework. \$\endgroup\$ Sep 16, 2015 at 9:30
2
\$\begingroup\$

I would also consider throwing an exception if either argument is null. This would be consistent with the BCL's own extension methods

I agree with this, but as an interesting side note as to why you want to throw exceptions consider the following test case.

IList<string> list1 = null;
IList<string> list2 = null;

Assert.IsTrue(list1.EqualsAll(list2));

This test would actually pass but it's certainly a very odd thing to do; considering calling a method on a null value wouldn't normally work. It just so happens extension methods behave differently in this regard.

Whenever you're working with null values consider the following definitions:

  • not set
  • invalid
  • undefined
  • not allocated
  • not really a list

If you think about nulls in these terms it becomes clear that throwing an exception is the only logical thing to do.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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