I am reordering the nodes in a certain level for a tree structure using the following recursive function. Reorder using the sort is not taking time, however recursively finding the parent node is taking time. how can I make this faster?

const reorderNodes = (tree, reorderedObject) => {
let copy = cloneDeep(tree);

// reorder
const reorder = (children) =>
  children?.slice().sort((a, b) => {
    return (
      reorderedObject.children.findIndex(reordered => reordered.id === a.id) -
      reorderedObject.children.findIndex(reordered => reordered.id === b.id)
    );
  });

if (!reorderedObject.parentId) {
  // if no parent
  copy = reorder(copy);
} else {
  // look recursively      
  copy = copy.map(el => {
    // found element to reorder.
    if (el.children) {
      if (el.id === reorderedObject.parentId) {
        el.children = reorder(el.children);
      } else {
        el.children = reorderNodes(el.children, reorderedObject);
      }
    }
    return el;
  });
}
return copy;
};

tree data

const tree = [
  {
    id: 'module-1',
    label: 'Unit',
    children: [{ id: 'field-zz', label: 'Name' }]
  },
  {
    id: 'module-2',
    label: 'Plans',
    children: [
      {
        id: 'level-1',
        label: 'Test-Level-1',
         children: [
          {
            id: 'level-1-1',
            label: 'Test-Level-1-1',
             children: [
              {
                id: 'field-1-1',
                label: 'ID',
              },
              {
                id: 'field-1-2',
                label: 'First upd',
              }
            ]
          },
          {
            id: 'level-1-2',
            label: 'Level-1-1-2',
            children: [
              {
                id: 'field-2-1',
                label: 'ID',
               
              },
              {
                id: 'field-2-2',
                label: 'First Upd',
                
              }
            ]
          }
        ]
      },
      {
        id: 'level-2',
        label: 'Test-Level-2',
       
        children: [
          {
            id: 'field-3',
            label: 'Keyword',
           
          },
          {
            id: 'field-4',
            label: 'Assignment',
            
          }
        ]
      },
      {
        id: 'module-3',
        label: 'Find more',
        
        children: [
          {
            id: 'field-5',
            label: 'Description',
            
          },
          {
            id: 'field-6',
            label: 'ID',
            
          }
        ]
      }
    ]
  },
  {
    id: 'module-4',
    label: 'Data',
    
    children: [
      { id: 'field-33333', label: 'Date'},
      { id: 'field-44444', label: 'Time'}
    ]
  }
];

reorderedObject

const reorderedObject = {
        parentid: 'module-4',
        
        children: [
          { id: 'field-44444', label: 'Time'},
          { id: 'field-33333', label: 'Date'}
        ]
      }

If i have 4 level depth and 50 items in each level, it takes 10 sec to process.

CodePudding user response：

Your code should be fast. I've implemented a recursive descent parser for a family tree app similar to what you're doing and have never exceeded a few tens of milliseconds drawing an entire family tree.

The main problem with your code is this:

let copy = cloneDeep(tree);

That's a whole lot of malloc() the javascript engine need to do in the background! Avoid copying memory in any language for speed.

If you need the original tree then clone just once before you enter the recursive function.

CodePudding user response：

You just need to perform a graph search, and once you have found the node in question, sort its children.

Since the sort() operation sorts the array in place, there is no need for all the slice() and map() operations. You're recursively copying every level of the tree multiple times, and you have already cloned the entire tree to begin with.

I've implemented the graph search operation as a depth-first search:

const reorderNodes = (tree, reorderedObject) => {
  const reorder = (nodes) => nodes.sort((a, b) => 
    reorderedObject.children.findIndex(reordered => reordered.id === a.id) -
    reorderedObject.children.findIndex(reordered => reordered.id === b.id)
  );

  const find = (nodes) => {
    if (!reorderedObject.parentId) return nodes;

    for (const node of nodes) {
      if (node.children) {
        if (node.id === reorderedObject.parentId) return node.children;
        
        const result = find(node.children);
        if (result) return result;
      }
    }
  }

  const copy = structuredClone(tree);
  const found = find(copy);

  reorder(found);

  return copy;
};

const tree = [{
  id: 'module-1',
  label: 'Unit',
  children: [{
    id: 'field-zz',
    label: 'Name'
  }]
}, {
  id: 'module-2',
  label: 'Plans',
  children: [{
    id: 'level-1',
    label: 'Test-Level-1',
    children: [{
      id: 'level-1-1',
      label: 'Test-Level-1-1',
      children: [{
          id: 'field-1-1',
          label: 'ID',
        },
        {
          id: 'field-1-2',
          label: 'First upd',
        }
      ]
    }, {
      id: 'level-1-2',
      label: 'Level-1-1-2',
      children: [{
        id: 'field-2-1',
        label: 'ID',

      }, {
        id: 'field-2-2',
        label: 'First Upd',

      }]
    }]
  }, {
    id: 'level-2',
    label: 'Test-Level-2',
    children: [{
      id: 'field-3',
      label: 'Keyword',

    }, {
      id: 'field-4',
      label: 'Assignment',

    }]
  }, {
    id: 'module-3',
    label: 'Find more',
    children: [{
      id: 'field-5',
      label: 'Description',

    }, {
      id: 'field-6',
      label: 'ID',

    }]
  }]
}, {
  id: 'module-4',
  label: 'Data',

  children: [{
    id: 'field-33333',
    label: 'Date'
  }, {
    id: 'field-44444',
    label: 'Time'
  }]
}];

const reorderedObject = {
  parentId: 'module-4',
  children: [{
    id: 'field-44444',
    label: 'Time'
  }, {
    id: 'field-33333',
    label: 'Date'
  }]
};

console.log(reorderNodes(tree, reorderedObject));