Linq 递归求和

Question

我有以下数据结构：

        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 的值。

对于 Item Id = 3，我有 21，因为 Item Id = 5 和 Id = 9 的总和就是这个。到目前为止太好了。

我正在努力获得的是对于 Item Id = 1 我也应该有总和 = 21，因为 Id = 3 是 Id = 1 的孩子，它的总和为 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()
                                   };

帮助表示赞赏。

Answer 1

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

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;
    }
}

现在您可以获得任何父母的价格：

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

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

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;
});

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

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它没有。

最后，这是一个不使用任何堆栈（隐式或显式）的变体。

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);
}

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

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可能很慢的内容，并收集IEnumerable我在其他地方看到的建议优化的 s 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仍然是最快的，尽管它现在非常接近，但有时更简单的性能会胜出。