Linq 递归求和 [英] Linq Recursive Sum

问题描述

我有以下数据结构:

        List<Item> Items = new List<Item>
        {
            new Item{ Id = 1, Name = "Machine" },
            new Item{ Id = 3, Id_Parent = 1,  Name = "Machine1"},
            new Item{ Id = 5, Id_Parent = 3,  Name = "Machine1-A", Number = 2, Price = 10 },
            new Item{ Id = 9, Id_Parent = 3,  Name = "Machine1-B", Number = 4, Price = 11 },
            new Item{ Id = 100,  Name = "Item" } ,
            new Item{ Id = 112,  Id_Parent = 100, Name = "Item1", Number = 5, Price = 55 }
        };

我想构建一个查询，获取其父项中所有子项价格的总和(项目与 Id_Parent 相关).例如，对于 Item Id = 100，我有 55，因为这是它的 child 的值.

I want to build a query that gets the sum of all children price in its parent (items are related by Id_Parent). For example, for Item Id = 100, I have 55, because thats the value of the its child .

对于 Item Id = 3，我有 21 个，因为 Item Id = 5 和 Id = 9 的总和就是这个.到目前为止还不错.

For Item Id = 3 I have 21, becaue Item Id = 5 and Id = 9 all sum to that. So far soo good.

我正在努力得到的是对于 Item Id = 1 我也应该有总和 = 21，因为 Id = 3 是 Id = 1 的孩子，它的总和为 21.

What I am strugling to get is for Item Id = 1 I should also have the sum = 21, because Id = 3 is a child of Id = 1 and it has a sum of 21.

这是我的代码:

        var result = from i in items
                                   join item in item on i.Id_Parent equals item.Id
                                   select new
                                   {
                                       Name = prod.Nome,
                                       Sum =
                                         (from it in items
                                          where it.Id_Parent == item.Id
                                          group it by new
                                          {
                                              it.Id_Parent
                                          }
                                          into g
                                          select new
                                          {
                                              Sum = g.Sum(x => x.Price)
                                          }
                                         ).First()
                                   };

感谢帮助.

推荐答案

创建一个递归函数来查找父级的所有子级:

Create a recursive function to find all the children of a parent:

public static IEnumerable<Item> ItemDescendents(IEnumerable<Item> src, int parent_id) {
    foreach (var item in src.Where(i => i.Id_Parent == parent_id)) {
        yield return item;
        foreach (var itemd in ItemDescendents(src, item.Id))
            yield return itemd;
    }
}

现在您可以获得任何家长的价格:

Now you can get the price for any parent:

var price1 = ItemDescendants(Items, 1).Sum(i => i.Price);

请注意，如果您知道项目的子项的 id 值始终大于其父项，则不需要递归:

Note if you know that the children of an item are always greater in id value than their parent, you don't need recursion:

var descendents = Items.OrderBy(i => i.Id).Aggregate(new List<Item>(), (ans, i) => {
    if (i.Id_Parent == 1 || ans.Select(a => a.Id).Contains(i.Id_Parent))
        ans.Add(i);
    return ans;
});

对于那些喜欢避免递归的人，您可以使用显式堆栈代替:

For those that prefer to avoid recursion, you can use an explicit stack instead:

public static IEnumerable<Item> ItemDescendentsFlat(IEnumerable<Item> src, int parent_id) {
    void PushRange<T>(Stack<T> s, IEnumerable<T> Ts) {
        foreach (var aT in Ts)
            s.Push(aT);
    }

    var itemStack = new Stack<Item>(src.Where(i => i.Id_Parent == parent_id));

    while (itemStack.Count > 0) {
        var item = itemStack.Pop();
        PushRange(itemStack, src.Where(i => i.Id_Parent == item.Id));
        yield return item;
    }
}

我包含了 PushRange 辅助函数，因为 Stack 没有.

I included PushRange helper function since Stack doesn't have one.

最后，这是一个不使用任何堆栈的变体，无论是隐式还是显式.

Finally, here is a variation that doesn't use any stack, implicit or explicit.

public IEnumerable<Item> ItemDescendantsFlat2(IEnumerable<Item> src, int parent_id) {
    var children = src.Where(s => s.Id_Parent == parent_id);
    do {
        foreach (var c in children)
            yield return c;
        children = children.SelectMany(c => src.Where(i => i.Id_Parent == c.Id)).ToList();
    } while (children.Count() > 0);
}

您也可以用 Lookup 替换源的多次遍历:

You can replace the multiple traversals of the source with a Lookup as well:

public IEnumerable<Item> ItemDescendantsFlat3(IEnumerable<Item> src, int parent_id) {
    var childItems = src.ToLookup(i => i.Id_Parent);

    var children = childItems[parent_id];
    do {
        foreach (var c in children)
            yield return c;
        children = children.SelectMany(c => childItems[c.Id]).ToList();
    } while (children.Count() > 0);
}

我根据关于嵌套枚举过多的评论优化了上面，大大提高了性能，但我也受到启发，尝试删除可能很慢的SelectMany，并收集IEnumerables 正如我在别处看到的建议优化 Concat :

I optimized the above based on the comments about too much nested enumeration, which improved performance vastly, but I was also inspired to attempt to remove SelectMany which can be slow, and collect IEnumerables as I've seen suggested elsewhere to optimize Concat:

public IEnumerable<Item> ItemDescendantsFlat4(IEnumerable<Item> src, int parent_id) {
    var childItems = src.ToLookup(i => i.Id_Parent);

    var stackOfChildren = new Stack<IEnumerable<Item>>();
    stackOfChildren.Push(childItems[parent_id]);
    do
        foreach (var c in stackOfChildren.Pop()) {
            yield return c;
            stackOfChildren.Push(childItems[c.Id]);
        }
    while (stackOfChildren.Count > 0);
}

@AntonínLejsek 的 GetDescendants 仍然是最快的，尽管它现在已经很接近了，但有时更简单的方法会胜过性能.

@AntonínLejsek's GetDescendants is still fastest, though it is very close now, but sometimes simpler wins out for performance.

这篇关于Linq 递归求和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！