Most performant way to sort a deeply nested array of objects by another deeply nested array of objects

Question

As an example - I've included a one element array that contains an object that has a Children key, which is an array of objects and each object also has its' own Children key that contains another array.

[
  {
    "Id": "1",
    "Children": [
      {
        "Id": "2",
        "Children": [
          {
            "Id": "10",
            "DisplayName": "3-4",
          },
          {
            "Id": "1000",
            "DisplayName": "5-6",
          },
          {
            "Id": "100",
            "DisplayName": "1-2",
          },
        ]
      }
    ]
  }
]

There is a second array of objects that I would like to compare the first array of objects to, with the intention of making sure that the first array is in the same order as the second array of objects, and if it is not - then sort until it is.

Here is the second array:

[
  {
    "Id": "1",
    "Children": [
      {
        "Id": "2",
        "Children": [
           {
            "Id": "100",
            "DisplayName": "1-2",
          },
          {
            "Id": "10",
            "DisplayName": "3-4",
          },
          {
            "Id": "1000",
            "DisplayName": "5-6",
          },
        ]
      }
    ]
  }
]

The data that this will run on can be up in the tens of thousands - so performance is paramount.

What I'm currently attempting is using a utility method to convert each element of the second array into a keyed object of objects e.g.

{
   1:  {
        "Id": "1",
        "Children": [
          {
            "Id": "2",
            "Children": [
              {
                "Id": "4",
                "DisplayName": "3-4",
              },
              {
                "Id": "3",
                "DisplayName": "1-2",
              },
            ]
          }
        ]
      }
}

This allows fast look up from the top level. I'm wondering if I should continue doing this all the way down or if there is an idiomatic way to accomplish this. I considered recursion as well. The order of the already sorted array is not based on Id - it is arbitrary. So the order needs to be preserved regardless.

Are the objects guaranteed to have same depth and do they contain same number of children at each level? — charlietfl, Aug 02 '18 at 23:56
As long as a key exists in one - the corresponding key in the other will have the same depth yes. Though, there will be keys that exist in the reference that don't exist in the array being compared. I'm going to try with the example you provided, and I may need to use pluck / filter to get both identical than run the recursive function. — zero_cool, Aug 03 '18 at 02:09

charlietfl · Answer 1 · 2018-08-03T00:28:21.730

0

Assuming same depth and all Id's exist in each level of each object use a recursive function that matches using Array#findIndex() in sort callback

function sortChildren(main, other) {
  other.forEach((o, i) => {
    if (o.children) {
      const mChilds = main[i].children, oChilds = o.children;
      
      oChilds.sort((a, b) => {
        return mChilds.findIndex(main => main.Id === a.Id) - mChilds.findIndex(main => main.Id === b.Id)
      });
      // call function again on this level passing appropriate children arrays in
      sortChildren(mChilds, oChilds)
    }
  })
}

sortChildren(data, newData);
console.log(JSON.stringify(newData, null, ' '))

<script>
  var data = [{
    "Id": "1",
    "Children": [{
      "Id": "2",
      "Children": [{
          "Id": "3",
          "DisplayName": "1-2",
        },
        {
          "Id": "4",
          "DisplayName": "3-4",
        },
      ]
    }]
  }]

  var newData = [{
    "Id": "1",
    "Children": [{
      "Id": "2",
      "Children": [{
          "Id": "4",
          "DisplayName": "3-4",
        },
        {
          "Id": "3",
          "DisplayName": "1-2",
        },
      ]
    }]
  }]

</script>

edited Aug 03 '18 at 00:28

answered Aug 03 '18 at 00:17

charlietfl

170,828
13
121
150

The issue with the data I have to sort by is that the id param isn't in ascending / descending order. How would you preserve the order regardless? – zero_cool Aug 03 '18 at 16:15
Am using the index of the relevant ID – charlietfl Aug 03 '18 at 16:21
@zero_cool the order of `Id`? It's risky to think of object keys having a predictable order: https://stackoverflow.com/q/30076219/3294944 (If you meant array index position, ignore my comment. :) ) – stealththeninja Aug 03 '18 at 16:21
No. Each object is element of the children arrays. Index of that object within it's children array. It is array index...nothing to do with object property order – charlietfl Aug 03 '18 at 16:22

Most performant way to sort a deeply nested array of objects by another deeply nested array of objects

1 Answers1

Linked