James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 136 , comments - 1089 , trackbacks - 0

My Links

News

Welcome to my blog! I'm a Sr. Software Development Engineer in Seattle, WA. I've been doing C++/C#/Java development for over 18 years, but have definitely learned that there is always more to learn!

All thoughts and opinions expressed in my blog and my comments are my own and do not represent the thoughts of my employer.

Blogs I Read

MCC Logo MVP Logo

Follow BlkRabbitCoder on Twitter

Tag Cloud

Archives

Post Categories

C#/.NET Little Wonders: The SequenceEqual() Method

Once again, in this series of posts I look at the parts of the .NET Framework that may seem trivial, but can help improve your code by making it easier to write and maintain. The index of all my past little wonders posts can be found here.

First of all, thanks for all the well-wishers for me and my family, things are starting to settle down a bit, so I hope to be able to continue to blog at least on a bi-weekly basis – and I’m hoping to sprinkle in some C++ blog entries as well.

But for today, we’re going to look at a handy extension method defined in the Enumerable class that let’s us check two sequences for equality.

Introduction - Comparing Sequences

There are times, we want to check to sequences to see if they are equal.  The basic definition of two equal sequences is if they have:

  • The same number of elements, and
  • The same values at each position in both sequences.

That is, two sequences are equal if the count of items are the same and the first elements have the same value, the second elements have the same value, etc.

So, for example, if we were comparing two arrays to see if they were equal, we could do something like this:

   1: public static bool EqualArrays<T>(T[] first, T[] second)
   2: {
   3:     // first check to make sure length same
   4:     if (first.Length != second.Length)
   5:     {
   6:         return false;
   7:     }
   8:  
   9:     // then examine item by item, stopping at the point not equal
  10:     for (int i = 0; i < first.Length; i++)
  11:     {
  12:         if (!Equals(first[i], second[i]))
  13:         {
  14:             return false;
  15:         }
  16:     }
  17:  
  18:     return true;
  19: }

But that only works for arrays, what if we wanted to make it more generic to cover any IEnumerable<T> sequences?  Well, we can use the GetEnumerator() and modify the method to take IEnumerable<T> instance instead, like:

   1: public static bool EqualEnumerables<T>(IEnumerable<T> first, IEnumerable<T> second)
   2: {
   3:     // get enumerators
   4:     using (var firstPos = first.GetEnumerator())
   5:     using (var secondPos = second.GetEnumerator())
   6:     {
   7:         // move to next item
   8:         var hasFirst = firstPos.MoveNext();
   9:         var hasSecond = secondPos.MoveNext();
  10:  
  11:         // as long as both have an item
  12:         while (hasFirst && hasSecond)
  13:         {
  14:             // compare em
  15:             if(!Equals(firstPos.Current, secondPos.Current))
  16:             {
  17:                 return false;
  18:             }
  19:  
  20:             // advance to next items
  21:             hasFirst = firstPos.MoveNext();
  22:             hasSecond = secondPos.MoveNext();
  23:         }
  24:  
  25:         // if we are done, at least one sequence has run out, so they are equal
  26:         // if both are empty
  27:         return !hasFirst && !hasSecond;
  28:     }
  29: }

Fortunately, you don’t have to do any of this work, LINQ has already done this for you in an extension method called SequenceEqual().

SequenceEqual() – Compare two sequences for value equality

The Enumerable.SequenceEqual() extension method is a very general algorithm that compares any two sequences to make sure they have the same count of items, and the same value in each corresponding position. 

It can determine the count much like my second code example above, where it will iterate through the sequences together, and the moment one of them runs out of elements it can simply make sure the other has no elements as well. 

Now, on equality of the values, it will use the default comparer unless you specify an alternate comparer.  Thus the two forms of SequenceEqual() extension method are as follows:

  • first.SequenceEqual(second)
    • Compares the first sequence to the second using the EqualityComparer<T>.Default comparer for the their type.
  • first.SequenceEqual(second, comparer)
    • Compares the first sequence to the second using the specified IEqualityComparer<T> comparer.

Since both of these are based solely on IEnumerable<T>, this means we can compare any two sequences of values as long as the type of value in the sequence is the same.  That is, we can use this method to compare an int[] to a List<int> if we wish.

   1: var evens = new int[] { 2, 4, 6, 8, 10 };
   2: var odds = new List<int> { 1, 3, 5, 7, 9 };
   3:  
   4: // false, not same values
   5: Console.WriteLine("Evens and odds are same: " + 
   6:     evens.SequenceEqual(odds));
   7:  
   8: var evensAsList = evens.ToList();
   9:  
  10: // true, different containers, but same values
  11: Console.WriteLine("Evens array and evens list are same: " +
  12:     evens.SequenceEqual(evensAsList));
  13:  
  14: var evensBelowSeven = evens.TakeWhile(e => e < 7);
  15:  
  16: // false, same starting values but one sequence longer
  17: Console.WriteLine("Evens array and evens < 7 are same: " +
  18:     evens.SequenceEqual(evensBelowSeven));

Keep in mind with these methods that the order of the elements is the order the elements are iterated over, which may not be the original order added, based on whether the container is ordered, un-ordered, sorted, etc.

   1: var orderedNumbers = new int[] { 1, 200, 13, 57, 132 };
   2: var sortedNumbers = new SortedSet<int> { 1, 200, 13, 57, 132 };
   3:  
   4: // false, sortedNumbers will actually iterate as { 1, 13, 57, 132, 200 }
   5: Console.WriteLine("Ordered same as sorted: " +
   6:     orderedNumbers.SequenceEqual(sortedNumbers));

These methods can come in handy for comparing two sequences to make sure the number and order of the items is correct, which can be handy for a variety of needs.

Unit Testing - Using SequenceEqual() to test expected results

So what if you are wanting to verify a method returns a particular sequence of values in a unit test?  For example, say we have a utility method which is a generator (returns a theoretically infinite sequence) of Fibonacci numbers (yes, this has overflow/safety concerns, but hey!  It’s fun!):

   1: // A utility class that holds math utility functions.
   2: public static class MathUtility
   3: {
   4:     // This method returns the fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, ... 
   5:     public static IEnumerable<int> GetFibonacciSequence()
   6:     {
   7:         int first = 0;
   8:         int second = 1;
   9:  
  10:         // first and second result are 0 and 1.
  11:         yield return first;
  12:         yield return second;
  13:  
  14:         // this enumerable sequence is bounded by the caller.
  15:         while(true)
  16:         {
  17:             // each subsequent number sum of previous two
  18:             int current = first + second;
  19:             yield return current;
  20:  
  21:             // wind up for next number if we're requesting one
  22:             first = second;
  23:             second = current;
  24:         }
  25:     }
  26: }

Remember that yield return creates an iterator which only returns the next value when it’s called for. Thus while the above looks like an infinite loop, in reality it depends how it’s being called.  If we use a method to pull it such as Take(10), the method above will only yield 10 numbers and then halt.  This is part of the magic of iterators and deferred execution!

But I digress, we can now use SequenceEqual() to easily check to see whether we get the results we expect for the first 10 values:

   1: [TestClass]
   2: public class FibonacciTest
   3: {
   4:     [TestMethod]
   5:     public void TestFirstTen()
   6:     {
   7:         var results = MathUtility.GetFibonacciSequence();
   8:  
   9:         Assert.IsTrue(results.Take(10).SequenceEqual(
  10:             new[] { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 }));
  11:     }
  12: }

And if we compile and run this test class in a unit test project, we will indeed see the Fibonacci method is indeed working as we expected!

So aside from everyday uses, the SequenceEqual() method is also very handy for checking expected results in unit tests as well.

Summary

LINQ adds many wonderful extension methods that can be called off of any implementation of IEnumerable<T>, one of these is the SequenceEqual() method that checks two sequences to see if they contain the same number of values, and the same value in each position of the sequence.

 

Technorati Tags: , , , , , ,

Print | posted on Thursday, February 16, 2012 7:14 PM |

Feedback

Gravatar

# re: C#/.NET Little Wonders: The SequenceEqual() Method

Nice timing! I was reading through Umbraco 5 sources and encountered a usage of this method in the core that compares two dynamic objects by using SequenceEqual recursively.

The SequenceEqual method unfortunately does not perform optimization for Collections. If an IEnumerable was an ICollection, you could first compare Count to see if they didn't match, so that's something you have to do yourself.
2/17/2012 8:01 AM | Shashi Penumarthy
Gravatar

# re: C#/.NET Little Wonders: The SequenceEqual() Method

As nice as it was to learn about this method, the most interesting part for me was the little paragraph about "yield return". As you noted, I swore you had just built an infinite loop. Now I have to go learn more about iterators and deferred execution. :)
2/17/2012 11:50 AM | Jesse
Gravatar

# re: C#/.NET Little Wonders: The SequenceEqual() Method

If you are unit testing using MSTest there is a CollectionAssert class which has a method offering the same functionality (CollectionAssert.AreEquivalent) as well as other methods for testing collections. Using this method instead of the IEnumerable extension method may make your tests more clear.
2/17/2012 12:18 PM | Tim B
Gravatar

# re: C#/.NET Little Wonders: The SequenceEqual() Method

Oops, made a mistake in my last comment. CollectionAssert.AreEquivalent is for when you don't care about order. If you do care about order, then use CollectionAssert.AreEqual.
2/17/2012 12:23 PM | Tim B
Gravatar

# re: C#/.NET Little Wonders: The SequenceEqual() Method

@sashi : correct. It doesn't check for Count on collection yet, though possible they could improve that in future.

@Jesse: yes yield return is a neat addition to the language, as long as mindful of performance impacts.

@Tim: good to know about collection assert. I checked assert for a similar method but didn't know collection assert existed! Learn something new every day!
2/17/2012 1:05 PM | james michael hare
Gravatar

# re: C#/.NET Little Wonders: The SequenceEqual() Method

Great article. I am certain I'll be using SequenceEqual soon.
2/22/2012 1:23 AM | Christoffer
Gravatar

# re: C#/.NET Little Wonders: The SequenceEqual() Method

If I'm looping through lists how would I create a unique list and maintain sequence at the same time?
At what point would I know I need to modify an item to keep it unique, but in the same position if it's "out of sequence" in subsequent lists?

8/21/2013 6:00 PM | radhat
Gravatar

# re: C#/.NET Little Wonders: The SequenceEqual() Method

For the first part, you can actually use the Distinct() LINQ method. For the second, how do you mean "modify an item to keep it unique?"
8/26/2013 7:54 PM | James Michael Hare
Post A Comment
Title:
Name:
Email:
Comment:
Verification:
 
 

Powered by: