javascript - 在 Javascript (Node.js) 中使用分层组对多维对象进行排序

Question

我有一个分层对象，我通过遍历父对象并对子对象进行排序来对子对象进行排序。这行得通。但现在，我需要有选择地打破层次结构并创建新的虚拟约束。

为了说明这一点，让我们举一个男人的例子，他有 x 个妻子。他和每个妻子都有 y 个 child 。我可以按照妻子对 child 进行排序，或者按照男人对妻子进行排序。

Man01   Wife01a     Kid01aA
                    Kid01aB
        Wife01b     Kid01bC
                    Kid01bD
Man02   Wife02c     Kid02cE
                    Kid02cF
        Wife02d     Kid02dG
                    Kid02dH

让我们给他们起个名字:

Murphy  Winnie  Kurt
                Kara
        Wendy   Klaus
                Klea
Marley  Wonda   Kasper
                Kyra
        Wilma   Kevin
                Karla

并考虑在它们的父级中按字母顺序对它们进行排序:

Marley  Wilma   Karla
                Kevin
        Wonda   Kasper
                Kyra
Murphy  Wendy   Klaus
                Klea
        Winnie  Kara
                Kurt

但是现在，我们希望能够对属于男人的 child 、一般的妻子或一般的 child 进行排序？

Marley  Wilma   Karla
        Wonda   Kasper
        Wilma   Kevin
        Wonda   Kyra
Murphy  Winnie  Kara
        Wendy   Klaus
        Wendy   Klea
        Winnie  Kurt

这是一个极其简化的虚构物体。实际上，我不是按字母顺序排序，而是对许多属性进行多列排序。

将结果输出到表格中很好，但处理本身已经占用了大量时间和内存。我不想进一步复杂化。

如果这没问题，我会将对象展平为数组中的一个表，将每个多列排序链接成一个 super 多列排序，然后从最近的共同祖先开始重新组合，这些祖先在循环中保持完好无损.

但我正在尝试以更有效的方式解决这个问题，而不是将对象转换为成熟的表数组。

• 我该如何解决这个问题？实际上循环遍历每个人两次？
  • 也许对于这种排序有一个“众所周知”的解决方案，但我还不知道？
  • 也许可以使用所有“虚拟”父级的引用来创建类似表格的记录，然后将这些引用分组回层次结构而不循环遍历它们？

这是我所指的对象类型的示例:对于 Object，我的意思是，字面意义上的 {}，尽管该对象包含 [] 对象数组 {}当它有多个成员时。

{
    "men"   : [
        {
            "name"  : "Murphy",
            // a lot of properties
            "wifes" : [
                {
                    "name"  : "Winnie",
                    // a lot of properties
                    "kids"  : [
                        {
                            "name"  : "Kurt",
                            // a lot of properties
                        }, {}, {} // etc...
                    ]
                }, {}, {} // etc...
            ]
        }, {}, {} // etc...
    ]
}

请注意，在这种情况下，我的示例是错误的，因为男人、妻子和 child 都是人类。但实际上有不同的对象具有不同的属性。假设有多个宇宙，我应该选择宇宙、行星、土壤或其他东西。 ;)

Answer 1

we want to be able to sort the kids that belong to a man

然后我会这样排列它们:

Marley  Karla   Wilma   
        Kasper  Wonda
        Kevin   Wilma
        Kyra    Wonda
Murphy  Kara    Winnie
        Klaus   Wendy
        Klea    Wendy
        Kurt    Winnie

当然，因为每个 child 只有一个母亲，所以没有太大区别，但对于您的实际数据，这可能会有所不同。

但是，您现在已经可以看到，您只需对每个人的每个 kids 数组进行排序。

因此，一般来说，您应该先进行分组，然后再对组进行排序 - 有点像 bucket sort，而不是展平到一个大表数组、对其进行多列排序并重新分组。 .

var men = data["men"];
men.forEach(function (man) {
    var kids = {};
    var wifes = man["wifes"];
    for (var i=0; i<wifes.length; i++) {
        var wkids = wifes[i]["kids"];
        for (j=0; j<wkids.length; j++) {
            var id = wkids[j]["name"];
            if (id in kids) {
                kids[id].mothers.push(wifes[i]);
            else {
                kids[id] = wkids[i];
                kids[id].mothers = [ wifes[i] ];
            }
        }
    }
    // if the id is the sort criteria:
    man["kids"] = Object.keys(kids).sort().map(function(id) {
        return kids[id];
    });
    // else build the array first and then sort it:
    // man["kids"] = Object.values(kids).sort(function(kida, kidb) {
    //    <some kid comparison>
    // });

    // you might integrate this loop in the above, but it's independent:
    man["kids"].forEach(function(kid) {
        kid["mothers"].sort( /* some mother comparison */ );
    })
});
// now every man has a sorted "kids" array with each kid having a sorted "mothers" array