如何优化JavaScript中两个对象数组合并为关联结构的实现逻辑

你当前实现的时间复杂度为O(U*P)（U为users数组长度，P为posts数组长度），每次遍历user时都要全量遍历posts做过滤，同时includes操作本身也会遍历postIds数组，数据量越大性能损耗越明显。
优化的核心逻辑是空间换时间：先一次性遍历posts数组构建以post id为键的索引结构（Map/普通对象），后续关联查询时仅需O(1)的时间复杂度即可拿到对应post数据，整体时间复杂度降到O(U+P)。

具体实现代码 #

方案1：使用Map构建索引（推荐，支持任意类型的键值） #

// 仅遍历1次posts构建索引
const postMap = new Map(posts.map(post => [post.id, post]));

// 遍历users时直接从索引取数，无需再遍历posts数组
const expectedOutput = users.map(({ id, name, postIds }) => ({
  id,
  name,
  posts: postIds.map(postId => postMap.get(postId))
}));

方案2：使用普通对象构建索引（兼容性更好） #

// 用reduce遍历posts构建索引
const postMap = posts.reduce((acc, post) => {
  acc[post.id] = post;
  return acc;
}, {});

const expectedOutput = users.map(({ id, name, postIds }) => ({
  id,
  name,
  posts: postIds.map(postId => postMap[postId])
}));

方案优势 #

• 性能提升显著：数据量越大对比原有实现的优势越明显，例如posts和users各有1000条时，原有实现需要执行近百万次操作，优化后仅需2000次左右操作即可完成。
• 扩展性更强：如果出现postId不存在对应post的场景，可以很方便的添加兜底逻辑，例如postMap.get(postId) ?? { id: postId, title: '未知内容' }。
• 逻辑可读性更好：先做数据索引再做关联匹配，符合常规的关联数据处理思路。

内容的提问来源于stack exchange，提问作者AlexUA