代码之家 › 专栏 › 技术社区 › ÐÐ°n

迭代器块到LINQ

yield-return iterator linq c#

ÐÐ°n · 技术社区 · 14 年前

我很难找到用于以下迭代器块的正确LINQ语法:

class Program
{
    class Operation
    {
        public IEnumerable<Operation> NextOperations { get; private set; }
    }
    class Item { }

    static Item GetItem(Operation operation)
    {
        return new Item();
    }

    static IEnumerable<Item> GetItems(IEnumerable<Operation> operations)
    {
        foreach (var operation in operations)
        {
            yield return GetItem(operation);

            foreach (var item in GetItems(operation.NextOperations))  // recursive
                yield return item;
        }
    }

    static void Main(string[] args)
    {
        var operations = new List<Operation>();
        foreach (var item in GetItems(operations))
        {
        }
    }
}

也许我所拥有的是最好的?对于这个特定的代码, yield return 在显式 foreach 确实是正确的解决方案吗?

3 回复 | 直到 14 年前

Eric Lippert 14 年前

也许我所拥有的是最好的?

很不错。我们可以做得更好一点。

对于这个特定的代码,显式foreach中的yield返回确实是正确的解决方案?

这是一个合理的解决办法。它很容易阅读,也很容易纠正。正如我前面提到的,如果树非常深,那么性能可能不好。

我会这样做:

static IEnumerable<T> AllNodes(this T root, Func<T, IEnumerable<T>> getChildren) 
{
    var stack = new Stack<T>();
    stack.Push(root);
    while(stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach(var child in getChildren(current).Reverse())
            stack.Push(child);
    }
} 

static void Main()      
{      
    var operation = whatever;
    var items = from op in operation.AllNodes(x=>x.NextOperations)
                select GetItem(op);
    foreach (var item in items)      
    {      
    }      
}

请注意,只有当您关心迭代“按顺序”进行时,才需要调用Reverse()。例如,假设操作alpha有子操作beta、gamma和delta,delta有子操作zeta和omega。遍历过程如下:

push Alpha
pop Alpha
yield Alpha
push Delta
push Gamma 
push Beta
pop Beta
yield Beta
pop Gamma
yield Gamma
pop Delta
yield Delta
push Omega
push Zeta
pop Zeta
yield Zeta
pop Omega
yield Omega

现在堆栈是空的,所以我们已经完成了,我们按照“预排序遍历”的顺序获取项目。如果你不关心顺序,如果你所需要的只是确保你得到了所有的顺序,那么不要费心去颠倒孩子们的顺序,你会得到他们的顺序α,δ,ω,zeta,gamma,beta。

有道理?

Jon Skeet 14 年前

使用标准的查询操作符,Linq通常不擅长递归。您可以编写上述更通用的形式,但是您将找不到一种执行这种遍历的标准Linq方法。

Tomas Petricek 14 年前

我认为您的实现是好的。但是,如果您想要使用LINQ(并使其稍微短一点,但不是显著短一点),那么您可以实现 GetItems 使用迭代所有操作并返回当前项和所有其他递归生成项的查询:

static IEnumerable<Item> GetItems(IEnumerable<Operation> operations) 
{ 
    return from op in operations
           from itm in (new[] { GetItem(op) }).Concat
                       (GetItems(op.NextOperations));
           select itm;
}

对于每个操作,我们生成一个序列,其中包含当前操作的项,然后是所有递归生成的项。通过使用嵌套 from 子句,您可以迭代此集合以获得“平面”结构。

我认为,通过使用一个支持“将元素附加到前面”操作的函数(不可变)列表,可以使它更好一点,这正是我们在嵌套中所做的 从 。使用 FuncList from my functional programming 书籍(但这不再是懒惰的序列):

static FuncList<Item> GetItems(IEnumerable<Operation> operations) 
{ 
    return (from op in operations
            from itm in FuncList.Cons(GetItem(op), GetItems(op.NextOperations));
            select itm).AsFuncList();
}

正如jon所提到的,使用查询编写递归方面没有好的方法(您可以使用lambda函数而不是方法编写递归查询——但这并不是更好的方法)。