如何验证，如果父项在递归函数LINQ孩子？ [英] How to validate if a parent item has children in recursive LINQ function?

问题描述

我在做一个递归函数LINQ在TIS问题描述：
的模拟CTE递归在C＃

I'm doing a recursive LINQ function as described in tis question: Simulating CTE recursion in C#

我的代码如下：

private static IEnumerable<KeyValuePair<int, int>> getNet(List<DataRow> list, int? leader, int level)
{
    return list
        .Where(x => x.Field<int?>("LeaderID") == leader)
        .SelectMany(x =>
            new[] { 
               new KeyValuePair<int, int>(x.Field<int>("RepID"), level)
                  }.Concat(getNet(list, x.Field<int>("RepID"), level+ 1))
         );
}

我想验证如果父母有孩子再次输入该功能前因为每一个孩子被再次评估，并消耗了大量的时间。

I'd like to validate if a parent has children before entering the function again because every child gets evaluated again and that consumes a lot of time.

即
父有5000儿童，但其中只有5有孩子，我需要东西来验证，如果A的孩子有执行该功能为所有这些前儿童。

i.e Parent A has 5000 children, but only 5 of them have children, I need something to validate if A's children have children before executing the function for all of them.

谢谢！

推荐答案

所以测试儿童早期真的是不会帮你的。你还在做同样的工作，在概念上。如果每次递归调用处理两种深处一次，而不是一个，你自己很大的复杂方法，复制第二深度的工作，每当有孩子，即使没有孩子获得非常，非常小。该方法的昂贵的部分是通过列表中的孩子，而不是在开始搜索方法调用。

So testing the children earlier really isn't going to help you. You're still doing the same work, conceptually. If each recursive call handles two depths at once, instead of one, you're greatly complicating the method itself, duplicating the work of the second depth whenever there are children, and gaining very, very little even when there are no children. The expensive part of the method is in the linear search through the list for the children, not in the method call that starts the search.

线性搜索要提高性能，你需要停止通过一个非常大名单做线性搜索很多很多次。幸运的是，这是很容易做到。只要创建一个查询一次，在方法所有的孩子每个父母，开始。

To improve performance you need to stop doing linear searches through a very large list many, many times. Fortunately, this is easy enough to do. Just create a lookup once, at the start of the method, of all children for each parent.

var lookup = list.ToLookup(x => x.Field<int?>("LeaderID"));

现在，你想要做的事情，在概念上是遍历一棵树。我们可以开始了与广义的穿越能够穿越任何树的方法（使用非递归实现，以提高性能）：

Now, what you're trying to do, conceptually, is traverse a tree. We can start out with a generalized "traverse" method capable of traversing any tree (using a non-recursive implementation, for performance improvements):

public static IEnumerable<T> Traverse<T>(IEnumerable<T> source, 
    Func<T, IEnumerable<T>> childSelector)
{
    var queue = new Queue<T>(source);
    while (queue.Any())
    {
        var item = queue.Dequeue();
        yield return item;
        foreach (var child in childSelector(item))
        {
            queue.Enqueue(child);
        }
    }
}

现在我们有了这些，我们可使用查找有效地让所有的孩子对于每个节点，大大提高了执行。当然，这将会是更漂亮，如果你没有还需要每个节点的深度，但它仍然没有那么糟糕。

Now that we have these we can use the lookup to efficiently get all children for each node, greatly improving the implementation. Of course, it'd be prettier if you didn't also need the depth of each node, but it's still not that bad.

var roots = lookup[leader]
    .Select(row => Tuple.Create(row.Field<int>("RepID"), 0));

return Traverse(roots, node => lookup[node.Item1]
    .Select(row => Tuple.Create(row.Field<int>("RepID"), node.Item2 + 1)));

如果你不需要知道每个节点的深度可以简化这一切下来这样的：

If you don't need to know the depth of each node you can simplify all of that down to this:

var lookup = list.ToLookup(
    row => row.Field<int?>("LeaderID"),
    row => row.Field<int>("RepID"));
return Traverse(lookup[leader], node => lookup[node]);

这篇关于如何验证，如果父项在递归函数LINQ孩子？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！