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\$
  • \$\begingroup\$ Is there a reason that no one here is suggesting Linq? msdn.microsoft.com/en-us/library/bb348567.aspx \$\endgroup\$ – MiniRagnarok Sep 16 '15 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\$ – MiniRagnarok Sep 16 '15 at 12:41
14
\$\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\$
  • \$\begingroup\$ +1 nice review. SequenceEqual is very inefficient compared to a for loop though. \$\endgroup\$ – Johan Larsson Sep 16 '15 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\$ – CodesInChaos Sep 16 '15 at 10:09
  • \$\begingroup\$ @CodesInChaos Great observation! \$\endgroup\$ – dcastro Sep 16 '15 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\$ – CodesInChaos Sep 16 '15 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\$ – Johan Larsson Sep 16 '15 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\$
  • 1
    \$\begingroup\$ Can you expand a bit on how/why your code is an improvement? \$\endgroup\$ – Kaz Sep 16 '15 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\$ – Johan Larsson Sep 16 '15 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.