Grouping Similar Items into buckets

Question

I've written some code to group a list of items into arbitrarily sized buckets. If the items are all the same and the and the count is a multiple of the bucket size a single bucket is returned, if the items are different then they are grouped into buckets of a given size.

For example, with a bucket size of 3:

1,2         => [1,2]
1,2,3,4,5   => [1,2,3][4,5]
1,1,1,1,1,1 => [1,1,1,1,1,1]
1,1,1,1,1   => [1,1,1][1,1]

To achieve this I've written the following .Net extension method:

public static IEnumerable<IList<T>> GroupBySize<T>(this IEnumerable<T> source, int groupSize, Func<T, T, bool> comparer)
{
    var result = new List<List<T>>();

    if (source.IsNullOrEmpty())
        return result;

    List<T> currentGroup = null;

    for (var i = groupSize; i <= source.Count(); i += groupSize)
    {
        var possibleGroup = source.Slice(i - groupSize, groupSize);
        if (possibleGroup.All(x => comparer(x, possibleGroup.First())))
        {
            if (currentGroup == null)
            {
                currentGroup = new List<T>();
                result.Add(currentGroup);
            }

            currentGroup.AddRange(possibleGroup);
        }
        else
        {
            currentGroup = new List<T>();
            currentGroup.AddRange(possibleGroup);
            result.Add(currentGroup);
            currentGroup = null;
        }
    }

    var remainingItems = source.Count() % groupSize;
    if (remainingItems > 0)
    {
        result.Add(source.Slice(source.Count() - remainingItems, remainingItems).ToList());
    }

    return result;
}

public static IEnumerable<T> Slice<T>(this IEnumerable<T> source, int start, int count)
{
    return source.Skip(start).Take(count);
}

public static bool IsNullOrEmpty<T>(this IEnumerable<T> items)
{
    // Taken from :http://haacked.com/archive/2010/06/10/checking-for-empty-enumerations.aspx
    return items == null || !items.Any();
}

The code passes the tests I've written, but it all (including the method name) feels a bit clunky.

How could this be improved?

Answer 1

I'm not sure you could make this code less clunky, it seems to me the code is reasonably simple, considering what it has to do.

But I can see other problems in your code:

1. The comparer parameter is probably not necessary in most cases, you can use EqualityComparer<T>.Default for this. But optional comparer makes sense to me.
2. LINQ extension methods are usually lazy and that's what I would expect from this method too. For example, if I do something like collection.GroupBySize(3).First(), it's not necessary to create the whole (possibly very long) result, only to discard most of it. To do this, you can use yield return.
3. You iterate the source collection (using LINQ methods) a lot. This can have terrible performance, especially if the source collection is something like a result of a LINQ database query, because it queries the database many times, which is not necessary. To fix this, you should write your method around a single foreach (var item in source) and don't use methods like Count(), First(), or Skip().

Answer 2

As svick said, you should make your method lazy and avoid iterating over the collection more than once. Heres an example of what it might look like:

public static IEnumerable<IList<T>> GroupBySizeNew<T>(this IEnumerable<T> source, int groupSize, Func<T, T, bool> comparer)
{
    if (source == null || groupSize == 0)
        yield break;

    var wholeGroup = new List<T>();
    var singleGroup = new List<T>();
    var backlog = new Queue<IList<T>>();

    T first = default(T);
    bool allSame = true;
    int count = 0;

    foreach (T item in source)
    {
        if (count == 0)
            first = item;

        if (allSame && !comparer(item, first))
        {
            while (backlog.Count > 0)
                yield return backlog.Dequeue();
            allSame = false;
        }

        singleGroup.Add(item);
        if (allSame)
            wholeGroup.Add(item);

        if (singleGroup.Count == groupSize)
        {
            if (allSame)
                backlog.Enqueue(singleGroup);
            else
                yield return singleGroup;
            singleGroup = new List<T>();
        }
        count++;
    }

    if (count == 0)
        yield break;
    else if (allSame && count % groupSize == 0)
        yield return wholeGroup;
    else
    {
        while (backlog.Count > 0)
            yield return backlog.Dequeue();
        if (singleGroup.Count > 0)
            yield return singleGroup;
    }
}