How to Optimize a Deeply Nested Object Search for Performance?

Question

I have a deeply nested JavaScript object structure representing a hierarchical data model. The object can have multiple levels of nested children, and I need to search for a specific value within this structure. Here is an example of such a nested object:

 const data = {
  id: 1,
  name: "Root",
  children: [
    {
      id: 2,
      name: "Child 1",
      children: [
        {
          id: 3,
          name: "Grandchild 1",
          children: []
        },
        {
          id: 4,
          name: "Grandchild 2",
          children: []
        }
      ]
    },
    {
      id: 5,
      name: "Child 2",
      children: [
        {
          id: 6,
          name: "Grandchild 3",
          children: []
        }
      ]
    }
  ]
};

Currently, I’m using a recursive function to search for the value by ID:

 function searchById(node, id) {
  if (node.id === id) {
    return node;
  }
  if (node.children) {
    for (let child of node.children) {
      const result = searchById(child, id);
      if (result) {
        return result;
      }
    }
  }
  return null;
}

const result = searchById(data, 4);
console.log(result);

trincot · Accepted Answer · 2024-05-16 12:34:21Z

If you only need to search once, then performance shouldn't be an issue.

If you need to search the same nested object many times, then create another object that maps every id to the result. You can populate that second object in one sweep, and then all searches can be done via the second object.

In the below implementation the generator function getEntriesRecursive yields all [id, node] pairs that are found in the nested data structure. The caller can turn these pairs into an object whose keys are those id, and then the lookup is just a property access:

function* getEntriesRecursive(node) {
    yield [node.id, node];
    for (const child of node.children) {
        yield* getEntriesRecursive(child);
    }
}

// Demo
const data = {id: 1,name: "Root",children: [{id: 2,name: "Child 1",children: [{id: 3,name: "Grandchild 1",children: []},{id: 4,name: "Grandchild 2",children: []}]},{id: 5,name: "Child 2",children: [{id: 6,name: "Grandchild 3",children: []}]}]};
const byId = Object.fromEntries(getEntriesRecursive(data));

for (const id of [4, 6, 5]) {
    console.log(id, byId[id]);
}

Alexander Nenashev · Accepted Answer · 2024-05-16 13:52:04Z

0

For maximum speed when looking for more than 1 item, load them into a map (otherwise your solution is ok):

const data = {id: 1,name: "Root",children: [{id: 2,name: "Child 1",children: [{id: 3,name: "Grandchild 1",children: []},{id: 4,name: "Grandchild 2",children: []}]},{id: 5,name: "Child 2",children: [{id: 6,name: "Grandchild 3",children: []}]}]};

const map = new Map;
const traverse = item => (map.set(item.id, item), item.children?.forEach(traverse));

traverse(data);

for (const id of [4, 6, 5]) {
    console.log(id, map.get(id));
}

A benchmark:

` Chrome/124
--------------------------------------------------
Alexander;  ■ 1.00x | x1000000 155 163 164 164 177
trincot      12.32x |  x100000 191 201 209 212 218
-------------------------------------------------- `

Open in the playground

const data = {id: 1,name: "Root",children: [{id: 2,name: "Child 1",children: [{id: 3,name: "Grandchild 1",children: []},{id: 4,name: "Grandchild 2",children: []}]},{id: 5,name: "Child 2",children: [{id: 6,name: "Grandchild 3",children: []}]}]};

// @benchmark Alexander;
const map = new Map;
const traverse = item => (map.set(item.id, item), item.children?.forEach(traverse));

traverse(data);

[4, 6, 5].map(id => map.get(id));

// @benchmark trincot
function* getEntriesRecursive(node) {
  yield [node.id, node];
  for (const child of node.children) {
      yield* getEntriesRecursive(child);
  }
}

const byId = Object.fromEntries(getEntriesRecursive(data));
[4, 6, 5].map(id => byId[id]);

/*@skip*/ fetch('https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js').then(r => r.text().then(eval));

answered May 16, 2024 at 13:52

Alexander Nenashev

26.1k3 gold badges11 silver badges29 bronze badges

3 Comments

Mulan Over a year ago

I appreciate the work that went into this answer. I think the benchmark could be improved if you compare the two algorithms on data sizes practical sizes like n=100, n=1000, and n=10000. Only showing n=3 is only slightly better than no benchmark at all. Fwiw, the benchmark is going to favour your program by a lot :D

Alexander Nenashev Over a year ago

@Mulan yes, the benchmark can run several sizes, but on flat arrays, seems i need to add support to nested structures, but there should be different levels of nesting to benchmark, a complex stuff to implement... anyway thanks for an idea

Alexander Nenashev Over a year ago

@Mulan anyway the benchmark is pretty valid, since it loops thousands times, and time complexity is O(n) i guess, and it properly demonstrates that generators are slow: dev.to/alexander-nenashev/…

Collectives™ on Stack Overflow

How to Optimize a Deeply Nested Object Search for Performance?

2 Answers 2

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related