Jacob Carpenter’s Weblog

November 16, 2007

Slice revisited

Filed under: csharp — Jacob @ 10:43 am

So Dustin responded to my last post in the comments of his original post with the following code snippet:

public static bool IsEmpty<T>(this IEnumerable<T> sequence)
{
    if (sequence == null)
        throw new ArgumentNullException("sequence");

    if (sequence.GetEnumerator().MoveNext())
        return false;

    return true;
}

public static IEnumerable<IEnumerable<T>> Slice<T>(this IEnumerable<T> sequence, int size)
{
    if (sequence == null)
        throw new ArgumentNullException("sequence");
    if (size <= 0)
        throw new ArgumentOutOfRangeException("size");

    while (!sequence.IsEmpty())
    {
        yield return sequence.Take(size);
        sequence = sequence.Skip(size);
    }
}

First of all: wow. That is remarkably succinct and elegant code capturing what we’re expressing with slice. (The parameter validation won’t occur until enumeration begins, but that’s easy to change.)

The trouble is that Take and Skip hide a lot of potentially expensive, unnecessary enumeration.

To look at it, we can create an iterator method to represent our source sequence:

public static IEnumerable<int> NumbersOneToTen()
{
    yield return 1;
    yield return 2;
    yield return 3;
    yield return 4;
    yield return 5;
    yield return 6;
    yield return 7;
    yield return 8;
    yield return 9;
    yield return 10;
}

Now, rather than calling slice with an array, we can set a breakpoint in this method and actually step through the calls to MoveNext(). [Note: this is a little unfair because some methods that accept an IEnumerable actually internally optimize for situations where they have, say, an ICollection/IList (for example, Reverse). This does not appear to be the case with Take/Skip, though.]

Here are the tallies for MoveNext() when executing the following code:

foreach (var slice in NumbersOneToTen().Slice(3))
    foreach (var item in slice)
        Console.WriteLine(item);
  MoveNexts Total
IsEmpty [false] 1 1
First slice [1, 2, 3] 3 4
IsEmpty [false] 4 8
Second slice [4, 5, 6] 6 14
IsEmpty [false] 7 21
Third slice [7, 8, 9] 9 30
IsEmpty [false] 10 40
Fourth slice [10] 11 51
IsEmpty [true] 11 62

It’s of some note that all of the slices, except the last, require n calls to MoveNext where n is the last element of the slice. Returning the last slice (as well as checking IsEmpty at the end) requires n+1 MoveNexts, because Take asks for more elements than there are remaining in the sequence. The 11th MoveNext simply returns false.

Now, I certainly don’t think Take or Skip are inherently evil. There are certainly contexts in which their use is completely benign.

But, the question emerges: do we care about 62 calls to MoveNext when 11 will do? Comments?

Advertisements

3 Comments »

  1. Hi Jacob,

    I posted a more optimal version in the comments to http://diditwith.net/2007/11/14/ImproveYourCBorrowFromF.aspx

    Comment by Dustin Campbell — November 16, 2007 @ 2:39 pm

  2. Jacob, Where exactly do I set the breakpoint to get to the MoveNext call? Is there a setting that I have to turn on in Visual Studio? I must be missing something since I couldn’t get Visual Studio to step into the MoveNext…

    Comment by Firefly — June 2, 2008 @ 1:32 am

  3. Firefly–

    I’m using Visual Studio 2008 (I’m not sure if this is the same behavior in 2005). Set the breakpoint on the line that says “yield return 1;”.

    Then when you run with the debugger, it should stop every time the sequence is enumerated (the calls to MoveNext).

    Comment by Jacob — June 2, 2008 @ 8:58 am


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: