数组获取所有 children 自下而上的总和

Question

我有一个 javascript 数组，如下所示：

[
    {
        used : 24000,
        service : service A,
        parent : service B,
    },
    {
        used : 450,
        service : service B,
        parent : service C,
    },
    ...
]

我想遍历数组以获得每个服务的总和 child。例如，如果一个服务得到了 A 和 B 作为一个 child，那么它的 used 属性将是它自己的 used + 他的 child used 的总和。因此，我需要首先获得层次结构中最深的服务。

那么最终输出可能是：

[
    {
        used : 24000,
        service : service A,
        parent : service B,
    },
    {
        used : 24450, //Sum here has changed
        service : service B,
        parent : service C,
    },
    ...
]

最后一件事，顶级服务并不总是有空 parent...

如果需要我可以将数组转换为分层数组

有没有人有好的算法可以做这样的事情（可能在 javascript 中，但伪代码也很酷）？

Answer 1

您可以使用 map、reduce 和 filter 在几行中完成：

var services = [{
        used : 24000,
        service : "A",
        parent : "B",
    }, {
        used : 450,
        service : "B",
        parent : "C",
    }, {
        used : 150,
        service : "C",
    }, {
        used: 100,
        service: "D"
    }
]

// Update one service, children first
var _update_service_sums = function(service, services) {
    var children = services.filter(s => s.parent === service.service)
    children.forEach(c => _update_service_sums(c, services))
    service.used_sum = service.used + children.map(c => c.used_sum).reduce((a, b) => a + b, 0);
}

// Update all services
var update_service_sums = function(services) {
    var roots = services.filter(s => s.parent === undefined)
    roots.forEach(r => _update_service_sums(r, services))
}

update_service_sums(services)
console.log(services)

我不想改变 used 的值，以便您可以连续多次调用该函数。

我在这里假设可以有多个根服务并且它们都没有父服务。如果您希望为其他服务计算 used_sum，您可以直接调用 _update_service_sums(service, services)。

Answer 2

这个问题让我想起了很多依赖构建。在依赖构建问题中，您必须根据它们的依赖关系（必须在它们之前出现的作业）来安排作业。如果您有作业 A、B 和 C，其中 A 依赖于 B 和 C，则您必须在 A 之前安排作业 B 和 C。您的问题似乎不在于调度，而是将依赖作业中的数字添加到当前作业中。要从服务 A 获得总计 "used" 数量，您必须首先计算服务 B 和 C 的总计。您的数组是依赖图的表示，但您计算的不是调度作业，而是使用的属性。

问题在于，如果您的图不是树，那么您的实现必须非常不同。从您对问题的描述来看，听起来我们正在处理一棵树。如果我们不是，那么请在评论中让我知道，我可以更新我的答案。如果您将图形视为依赖关系树，那么您需要做的就是保证，对于图形中的每个节点，在对其进行评估之前对其进行评估 children 。这可以通过使用 post 顺序遍历 http://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/ 来完成。如果你可以在这个依赖图上实现 post 顺序遍历，你可以简单地将左侧大小和右侧遍历的值 return 添加到你当前的总数，然后 return 新的"users" 属性供 parents 使用。这是一个计算您的值的 O(n) 算法。

数组获取所有 children 自下而上的总和

Array get sum of all children bottom up

arrays

algorithm

sum

hierarchical-data