c# - 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，因为这是其子项的值。

对于 Item Id = 3 我有 21，因为 Item Id = 5 和 Id = 9 总和为 21。到目前为止一切顺利。

我努力得到的是 Item Id = 1 我也应该有 sum = 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;
    }
}

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

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

您也可以用 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 正如我在其他地方看到的优化 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 仍然是最快的，虽然它现在非常接近，但有时更简单的性能会胜出。