Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – How to Optimize a Deeply Nested Object Search for Performance?

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);
Tags:

2

Answers


  1. 0

    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]);
}
    Login or Signup to reply.
  2. 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));
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search