Faster ' find & reorder' logic in javascript

Question

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.

I don't see any reordered structure. But probably I have difficulties with understanding what the OP really wants. Could the OP try to be more precise with describing the problem? — Peter Seliger, Jul 07 '22 at 09:02

score 1 · Accepted Answer · answered Jul 07 '22 at 09:18

1

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.

answered Jul 07 '22 at 09:18

slebetman

109,858
19
140
171

Similarly copying the array with `children?.slice()` will also slow you down a bit. – slebetman Jul 07 '22 at 09:20
Not to mention the `map()` operation :) – Robby Cornelissen Jul 07 '22 at 09:34
if i am not using the clone deep I had another problem, the parameter tree is coming from a state and it goes back to the state. this state was not updating correctly. – Sin Jul 07 '22 at 10:40
Read the last sentence of my answer – slebetman Jul 07 '22 at 10:53
@RobbyCornelissen. Self-updating operations like `x = x.map()` can be optimised by programming language runtimes using side-effect of copy-on-write. I'm not sure any javascript engine implements copy-on-write for values but Tcl will optimise it to not deallocate and reallocate memory (basically it reuses the objects that it knows will be garbage collected anyway). Tcl needs copy-on-write because that language does not have references/pointers - everything is a value (basically everything is immutable and changing anything means you create a new object and delete the old one) – slebetman Jul 07 '22 at 10:59
you are right, my cloneDeep is what taking time. I was having some issues when updating redux store when I am not using cloneDeep. – Sin Jul 07 '22 at 11:38

Robby Cornelissen · Answer 2 · 2022-07-07T09:37:30.687

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

Yea, even in this code if i use the cloneDeep(), it slows down a lot. somehow the typescript in my project is not recognising structuredclone. Any other method I can use? — Sin, Jul 07 '22 at 11:15
tried using structuredClone by https://stackoverflow.com/a/72306923/1521686 however this is also slow. — Sin, Jul 07 '22 at 11:29

Faster ' find & reorder' logic in javascript

2 Answers2