将连续的相同项分组:IEnumerable <T>到IEnumerable <IEnumerable <T >>

Question

我有一个有趣的问题:给定一个IEnumerable<string>,是否有可能IEnumerable<IEnumerable<string>>在一次传递中产生一组相同的相邻字符串？

让我解释.

1.基本说明性样本:

考虑以下IEnumerable<string>(伪表示):

{"a","b","b","b","c","c","d"}

如何获得一个IEnumerable<IEnumerable<string>>会产生某种形式的东西:

{ // IEnumerable<IEnumerable<string>>
    {"a"},         // IEnumerable<string>
    {"b","b","b"}, // IEnumerable<string>
    {"c","c"},     // IEnumerable<string>
    {"d"}          // IEnumerable<string>
}

方法原型将是:

public IEnumerable<IEnumerable<string>> Group(IEnumerable<string> items)
{
    // todo
}

但它也可能是:

public void Group(IEnumerable<string> items, Action<IEnumerable<string>> action)
{
    // todo
}

...... action每个子序列都会被调用.

2.更复杂的样本

好的,第一个样本非常简单,只是为了使高级意图清晰.

现在假设我们正在处理IEnumerable<Anything>,在这里Anything定义的类型如下:

public class Anything
{
    public string Key {get;set;}
    public double Value {get;set;}
}

我们现在想要生成基于Key的子序列(Anything将具有相同键的每个连续组分组)以便稍后使用它们以便按组计算总值:

public void Compute(IEnumerable<Anything> items)
{
    Console.WriteLine(items.Sum(i=>i.Value));
}

// then somewhere, assuming the Group method 
// that returns an IEnumerable<IEnumerable<Anything>> actually exists:
foreach(var subsequence in Group(allItems))
{
    Compute(subsequence);
}

3.重要说明

• 只对原始序列进行一次迭代
• 没有中间收集分配(我们可以假设原始序列中有数百万个项目,每组中有数百万个连续项目)
• 保持调查员和延迟执行行为
• 我们可以假设结果子序列只迭代一次,并将按顺序迭代.

它有可能吗,你会怎么写呢？

Answer 1

这是你想要的？

• 仅迭代列表一次.
• 推迟执行.
• 没有中间收藏(我的其他帖子在此标准上失败).

此解决方案依赖于对象状态,因为很难在使用yield(无ref或out params)的两个IEnumerable方法之间共享状态.

internal class Program
{
    static void Main(string[] args)
    {
        var result = new[] { "a", "b", "b", "b", "c", "c", "d" }.Partition();
        foreach (var r in result)
        {
            Console.WriteLine("Group".PadRight(16, '='));
            foreach (var s in r)
                Console.WriteLine(s);
        }
    }
}

internal static class PartitionExtension
{
    public static IEnumerable<IEnumerable<T>> Partition<T>(this IEnumerable<T> src)
    {
        var grouper = new DuplicateGrouper<T>();
        return grouper.GroupByDuplicate(src);
    }
}

internal class DuplicateGrouper<T>
{
    T CurrentKey;
    IEnumerator<T> Itr;
    bool More;

    public IEnumerable<IEnumerable<T>> GroupByDuplicate(IEnumerable<T> src)
    {
        using(Itr = src.GetEnumerator())
        {
            More = Itr.MoveNext();

            while (More)
                yield return GetDuplicates();
        }
    }

    IEnumerable<T> GetDuplicates()
    {
        CurrentKey = Itr.Current;
        while (More && CurrentKey.Equals(Itr.Current))
        {
            yield return Itr.Current;
            More = Itr.MoveNext();
        }
    }
}

编辑:添加了清洁用法的扩展方法.固定循环测试逻辑,以便首先评估"更多".

编辑:完成后处理枚举器