时间戳

首页 > 解决方案 > 在 Node.js 中构建多分支树时的性能问题

javascript - 在 Node.js 中构建多分支树时的性能问题

问题描述

我正在将对象的平面层次结构转换为基于父节点 ID 的嵌套对象。

问题是当我输入更复杂的结构（更多和更深的孩子）时，这个过程需要很长时间才能完成。

也许它与内存或递归或冗余的其他低效使用有关？我不确定。

编码：

const people = [
  {
    id: '738a8f8a',
    parentNode: null
  },
  {
    id: 'd18fd69c',
    parentNode: '738a8f8a'
  },
  {
    id: 'b507c11d',
    parentNode: '738a8f8a'
  },
  {
    id: '171d4709',
    parentNode: 'b507c11d'
  },
  {
    id: '471b1cee',
    parentNode: 'b507c11d'
  }
];

function getBase(base) {
  for (const person of base) {
    if (person['parentNode'] === null) {
      return person;
    }
  }
  return null;
}

function getChildren(parent) {
  const values = people.filter((person) => {
    return person['parentNode'] === parent['id'];
  });
  return Object.values(values);
}

function buildHierarchy(base = null) {
  if (base === null) {
    base = getBase(people);
    if (base === null) {
      return null;
    }
  }
  const children = getChildren(base).map((child) => {
    return buildHierarchy(child);
  });
  base['childrenNodes'] = children;
  return base;
}

console.log(buildHierarchy());

以及上面 console.log 的输出：

  {
    id: '738a8f8a',
    parentNode: null
    childrenNodes: [
      {
        id: 'd18fd69c',
        parentNode: '738a8f8a',
        childrenNodes: [],
      },
      {
        id: 'b507c11d',
        parentNode: '738a8f8a',
        childrenNodes: [
          {
            id: '171d4709',
            parentNode: 'b507c11d',
            childrenNodes: [],
          },
          {
            id: '471b1cee',
            parentNode: 'b507c11d',
            childrenNodes: [],
          },
        ],
      },
    ],
  };

标签： javascriptnode.jsmemorymemory-managementtree

解决方案

在写这个答案时，我看到了@cbr，并认为这是相同的逻辑。但并非完全如此，而且似乎存在明显的性能差异（至少在 Chrome 中），所以我仍然会发布这个

我无法用需要很长时间处理的真实数据对此进行测试，但我认为您的瓶颈是函数filter中的使用getChildren。对于每个人，您都在遍历整个people阵列。

我认为可以通过在构建层次结构之前只对数据进行一次预处理来减少时间。为此，我们可以创建一个Map，其中每个键是人的 ID，值是其子项的数组。

这可以这样实现：

// For each person
const childMap = people.reduce((map, person) => {
  // If its parentNode is not already in the map
  if (!map.has(person.parentNode)) {
    // Add it
    map.set(person.parentNode, []);
  }
  // Then, push the current person into that parent ID's children Array
  map.get(person.parentNode).push(person);
  return map;
}, new Map());

然后，您的getChildren函数将如下所示：

function getChildren(parent) {
  return childMap.get(parent.id) || [];
}

这是完整的示例，连续运行 100.000 次：

const people = [
  {
    id: '738a8f8a',
    parentNode: null
  },
  {
    id: 'd18fd69c',
    parentNode: '738a8f8a'
  },
  {
    id: 'b507c11d',
    parentNode: '738a8f8a'
  },
  {
    id: '171d4709',
    parentNode: 'b507c11d'
  },
  {
    id: '471b1cee',
    parentNode: 'b507c11d'
  }
];

const childMap = people.reduce((map, person) => {
  if (!map.has(person.parentNode)) {
    map.set(person.parentNode, []);
  }
  map.get(person.parentNode).push(person);
  return map;
}, new Map());

function getBase(base) {
  for (const person of base) {
    if (person.parentNode === null) {
      return person;
    }
  }
  return null;
}

function getChildren(parent) {
  return childMap.get(parent.id) || [];
}

function buildHierarchy(base = null) {
  if (base === null) {
    base = getBase(people);
    if (base === null) {
      return null;
    }
  }
  const children = getChildren(base);
  base.childrenNodes = children.map(buildHierarchy);
  return base;
}

console.time('x');
for (let i = 0; i < 100000; i++) buildHierarchy();
console.timeEnd('x');

您的代码连续运行 100.000 次：

const people = [
  {
    id: '738a8f8a',
    parentNode: null
  },
  {
    id: 'd18fd69c',
    parentNode: '738a8f8a'
  },
  {
    id: 'b507c11d',
    parentNode: '738a8f8a'
  },
  {
    id: '171d4709',
    parentNode: 'b507c11d'
  },
  {
    id: '471b1cee',
    parentNode: 'b507c11d'
  }
];

function getBase(base) {
  for (const person of base) {
    if (person['parentNode'] === null) {
      return person;
    }
  }
  return null;
}

function getChildren(parent) {
  const values = people.filter((person) => {
    return person['parentNode'] === parent['id'];
  });
  return Object.values(values);
}

function buildHierarchy(base = null) {
  if (base === null) {
    base = getBase(people);
    if (base === null) {
      return null;
    }
  }
  const children = getChildren(base).map((child) => {
    return buildHierarchy(child);
  });
  base['childrenNodes'] = children;
  return base;
}

console.time('x');
for (let i = 0; i < 100000; i++) buildHierarchy();
console.timeEnd('x');

@cbr 的代码，连续运行 100.000 次：

const people = [
  {
    id: "738a8f8a",
    parentNode: null,
  },
  {
    id: "d18fd69c",
    parentNode: "738a8f8a",
  },
  {
    id: "b507c11d",
    parentNode: "738a8f8a",
  },
  {
    id: "171d4709",
    parentNode: "b507c11d",
  },
  {
    id: "471b1cee",
    parentNode: "b507c11d",
  },
];

function buildNodeChildLookup(people) {
  const nodeIdToNode = people.reduce((map, curr) => {
    map.set(curr.id, curr);
    return map;
  }, new Map());

  return people.reduce((map, curr) => {
    const children = map.get(curr.parentNode) || [];
    const childNode = nodeIdToNode.get(curr.id);
    children.push(childNode);
    map.set(curr.parentNode, children);
    return map;
  }, new Map());
}

function buildHierarchy(node, nodeToChildren) {
  const children = nodeToChildren.get(node.id) || [];
  return {
    ...node,
    childNodes: children.map((child) => buildHierarchy(child, nodeToChildren)),
  };
}

// assume only one root!
const nodeIdToChildren = buildNodeChildLookup(people);
const root = nodeIdToChildren.get(null)[0];

console.time('x');
for (let i = 0; i < 100000; i++) buildHierarchy(root, nodeIdToChildren);
console.timeEnd('x');

推荐阅读