javascript中更快的“查找和重新排序”逻辑

Question

我正在使用下面的递归函数为树结构重新排序某个级别上的节点。使用排序重新排序并不需要时间，但是递归地查找父节点需要时间。我怎样才能让这个更快？

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

树数据

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'}
        ]
      }

如果我有4级深度和50项在每级，它需要10秒的处理。

Answer 1

你的代码应该很快。我为一个类似于您正在做的家族树应用程序实现了一个递归下降解析器，并且从未超过几十毫秒绘制出整个家族树。

代码的主要问题是：

let copy = cloneDeep(tree);

这是javascript引擎需要在后台完成的大量malloc()！避免以任何语言复制内存以提高速度。

如果您需要原始树，那么在输入递归函数之前只克隆一次。

Answer 2

您只需要执行一个图搜索，一旦找到了有问题的节点，就对其子节点进行排序。

由于sort()操作对数组进行排序，所以不需要所有的slice()和map()操作。您正在递归地多次复制树的每个级别，并且已经克隆了整个树。

我将图形搜索操作实现为深度优先搜索：

​

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

​