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

Question

我正在将对象的平面层次结构转换为基于父 Node 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: [],
          },
        ],
      },
    ],
  };

Answer 1

While writing this answer, I saw @cbr's, and thought it was the same logic. But not entirely, and there seems to be a sensible performance difference (in Chrome at least), so I'll still post this one

我无法使用需要很长时间处理的真实数据来测试这一点，但我认为您的瓶颈是在 getChildren 函数中使用 filter 。对于每个人，您都将遍历整个 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');