Get next N elements from enumerable

Question

Context: C# 3.0, .Net 3.5
Suppose I have a method that generates random numbers (forever):

private static IEnumerable<int> RandomNumberGenerator() {
    while (true) yield return GenerateRandomNumber(0, 100);
}

I need to group those numbers in groups of 10, so I would like something like:

foreach (IEnumerable<int> group in RandomNumberGenerator().Slice(10)) {
    Assert.That(group.Count() == 10);
}

I have defined Slice method, but I feel there should be one already defined. Here is my Slice method, just for reference:

    private static IEnumerable<T[]> Slice<T>(IEnumerable<T> enumerable, int size) {
        var result = new List<T>(size);
        foreach (var item in enumerable) {
            result.Add(item);
            if (result.Count == size) {
                yield return result.ToArray();
                result.Clear();
            }
        }
    }

Question: is there an easier way to accomplish what I'm trying to do? Perhaps Linq?

Note: above example is a simplification, in my program I have an Iterator that scans given matrix in a non-linear fashion.

EDIT: Why Skip+Take is no good.

Effectively what I want is:

var group1 = RandomNumberGenerator().Skip(0).Take(10);
var group2 = RandomNumberGenerator().Skip(10).Take(10);
var group3 = RandomNumberGenerator().Skip(20).Take(10);
var group4 = RandomNumberGenerator().Skip(30).Take(10);

without the overhead of regenerating number (10+20+30+40) times. I need a solution that will generate exactly 40 numbers and break those in 4 groups by 10.

Solution 1

I have done something similar. But I would like it to be simpler:

//Remove "this" if you don't want it to be a extension method
public static IEnumerable<IList<T>> Chunks<T>(this IEnumerable<T> xs, int size)
{
    var curr = new List<T>(size);

    foreach (var x in xs)
    {
        curr.Add(x);

        if (curr.Count == size)
        {
            yield return curr;
            curr = new List<T>(size);
        }
    }
}

I think yours are flawed. You return the same array for all your chunks/slices so only the last chunk/slice you take would have the correct data.

Addition: Array version:

public static IEnumerable<T[]> Chunks<T>(this IEnumerable<T> xs, int size)
{
    var curr = new T[size];

    int i = 0;

    foreach (var x in xs)
    {
        curr[i % size] = x;

        if (++i % size == 0)
        {
            yield return curr;
            curr = new T[size];
        }
    }
}

Addition: Linq version (not C# 2.0). As pointed out, it will not work on infinite sequences and will be a great deal slower than the alternatives:

public static IEnumerable<T[]> Chunks<T>(this IEnumerable<T> xs, int size)
{
    return xs.Select((x, i) => new { x, i })
             .GroupBy(xi => xi.i / size, xi => xi.x)
             .Select(g => g.ToArray());
}

Solution 2

Are Skip and Take of any use to you?

Use a combination of the two in a loop to get what you want.

So,

list.Skip(10).Take(10);

Skips the first 10 records and then takes the next 10.

Solution 3

Using Skip and Take would be a very bad idea. Calling Skip on an indexed collection may be fine, but calling it on any arbitrary IEnumerable<T> is liable to result in enumeration over the number of elements skipped, which means that if you're calling it repeatedly you're enumerating over the sequence an order of magnitude more times than you need to be.

Complain of "premature optimization" all you want; but that is just ridiculous.

I think your Slice method is about as good as it gets. I was going to suggest a different approach that would provide deferred execution and obviate the intermediate array allocation, but that is a dangerous game to play (i.e., if you try something like ToList on such a resulting IEnumerable<T> implementation, without enumerating over the inner collections, you'll end up in an endless loop).

(I've removed what was originally here, as the OP's improvements since posting the question have since rendered my suggestions here redundant.)

Solution 4

Let's see if you even need the complexity of Slice. If your random number generates is stateless, I would assume each call to it would generate unique random numbers, so perhaps this would be sufficient:

var group1 = RandomNumberGenerator().Take(10);  
var group2 = RandomNumberGenerator().Take(10);  
var group3 = RandomNumberGenerator().Take(10);  
var group4 = RandomNumberGenerator().Take(10);

Each call to Take returns a new group of 10 numbers.

Now, if your random number generator re-seeds itself with a specific value each time it's iterated, this won't work. You'll simply get the same 10 values for each group. So instead, you would use:

var generator  = RandomNumberGenerator();
var group1     = generator.Take(10);  
var group2     = generator.Take(10);  
var group3     = generator.Take(10);  
var group4     = generator.Take(10);

This maintains an instance of the generator so that you can continue retrieving values without re-seeding the generator.

Solution 5

It seems like we'd prefer for an IEnumerable<T> to have a fixed position counter so that we can do

var group1 = items.Take(10);
var group2 = items.Take(10);
var group3 = items.Take(10);
var group4 = items.Take(10);

and get successive slices rather than getting the first 10 items each time. We can do that with a new implementation of IEnumerable<T> which keeps one instance of its Enumerator and returns it on every call of GetEnumerator:

public class StickyEnumerable<T> : IEnumerable<T>, IDisposable
{
    private IEnumerator<T> innerEnumerator;

    public StickyEnumerable( IEnumerable<T> items )
    {
        innerEnumerator = items.GetEnumerator();
    }

    public IEnumerator<T> GetEnumerator()
    {
        return innerEnumerator;
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return innerEnumerator;
    }

    public void Dispose()
    {
        if (innerEnumerator != null)
        {
            innerEnumerator.Dispose();
        }
    }
}

Given that class, we could implement Slice with

public static IEnumerable<IEnumerable<T>> Slices<T>(this IEnumerable<T> items, int size)
{
    using (StickyEnumerable<T> sticky = new StickyEnumerable<T>(items))
    {
        IEnumerable<T> slice;
        do
        {
            slice = sticky.Take(size).ToList();
            yield return slice;
        } while (slice.Count() == size);
    }
    yield break;
}

That works in this case, but StickyEnumerable<T> is generally a dangerous class to have around if the consuming code isn't expecting it. For example,

using (var sticky = new StickyEnumerable<int>(Enumerable.Range(1, 10)))
{
    var first = sticky.Take(2);
    var second = sticky.Take(2);
    foreach (int i in second)
    {
        Console.WriteLine(i);
    }
    foreach (int i in first)
    {
        Console.WriteLine(i);
    }
}

prints

1
2
3
4

rather than

3
4
1
2

View more solutions

Comments

[THX-1138]

I don't want overhead of Skip/Take, I have edited the question.

[THX-1138]

right, I suppose me using array instead of list is an example of premature optimization. BTW, why do you use (++i % size == 0) instead of curr.Length == size? also your curr = new List<T>() should be curr = new List<T>(size)

[THX-1138]

Yes, I was reusing same array (worked for my case, but that might be a bug in most cases).

[Lasse Espeholt]

I do use (size) both places, I guess you got a early version :) I don't think List will be much slower than arrays. Because then I don't have to reset index each time. It would have been a bug if you did a .ToList() or .ToArray() but if you process the data immediately then it will be fine. See stackoverflow.com/questions/3447355/…

[THX-1138]

it will still dry-run enumerable for slices to be skipped. I'd like to avoid dry runs (performance is an official excuse, but actually it just feels wrong). Also your example enumerates T's not T[]'s as it should have (but I get the point).

[THX-1138]

That's what I thought, but I failed to construct an actual method using that idea. Care to produce a snippet?

[Lasse Espeholt]

Your right, I could have been using .Count instead. Thanks for improving :)

[THX-1138]

well if I'd use ToList or ToArray - that would actually fix the bug, since that would create a new instance on each yield return. no?

[Lasse Espeholt]

Yes, but I would guess that my method is faster because it ain't copying the list to an array - but I have not tested it.

[THX-1138]

yield result.ToArray() clones data into a new array, so calling Clear() on the list will not affect the returned instance of the array.

[THX-1138]

I have changed the implementation to use foreach instead, that should take care of disposing. good point though +1

[THX-1138]

The difference in the return, I return T[] chunks, when you do IList<T> - that's what makes a difference, too bad there is no ((T[]) list)

[THX-1138]

yield return result.ToArray(); ensures that every returned chunk is a unique array-object.

[Dan Tao]

@user93422: Yes, I see that we came up with the same solution to that issue. Your original code did return the same array, though, as you yourself conceded.

[Sean Copenhaver]

I hope that helps at least some what. I probably should brush up on generators myself.

[LBushkin]

@user93422: Yes I noticed that shorty after updating my post. I've corrected my mistake.

[Sean Copenhaver]

I don't think this will work how you think it will with a generator.

[Lasse Espeholt]

The array internally in a list can be larger than the actual list, so either it could return a larger array than you want or do the same as ToArray() - unless of cause the array and list size is equal.

[Dan Tao]

@Sean: Your RandomNumberGenerator function returns a single value. You would need to put it in a loop: while (true) yield return random.Next();

[Lasse Espeholt]

See my linq version. I think it looks nice. You may be able to convert it to C# 2.0

[THX-1138]

how do you change Slice method so it returns IEnumerable<int[]> without calling enmerable.Count()? And does yield return instead of return, what you have right now is exactly: return enumerable.Take(size);...I think.

[Sean Copenhaver]

I'll add my adaptation to a new answer.

[Lasse Espeholt]

Why not use a foreach when you are doing just what the foreach-loop does?

[Dan Tao]

@lasseespeholt: Good question; really my code was just a modified version of what the OP had originally. I can't really give much of a reason, other than that it didn't occur to me. foreach would be more readable.

[THX-1138]

my bad. I am using C# 3.0, not 2.0

[THX-1138]

one caveat, linq version will not work with infinite sequence. For my real case it does what it supposed to do.

[stevemegson]

The LINQ version is nice, but has the disadvantage of consuming all of xs before returning the first slice. GroupBy can't know that there isn't another item with a key of 0 until it has read everything. For a typical enumerable that's just different to the other implementations rather than really wrong, but for the infinite random number generator it means an infinite loop.

[Lasse Espeholt]

@user93422,stevemegson Yeah, it must also be a lot slower than the alternatives. I have pointed it out in my answer.