arrays - 数组自下而上获取所有 child 的总和

Question

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

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

我想遍历数组以获得每个服务子项的总和。例如，如果一个服务有 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,
    },
    ...
]

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

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

有没有人有一个好的算法可以做这样的事情(可能是在 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)。