如何在TypeScript中高效遍历两个大型对象数组并合并数据

问题背景 #

现有两个示例数组：

var marks=[{"id":1,"marks":null,"grade":"A"},{"id":1,"marks":90,"grade":null},{"id":1,"marks":90,"grade":"A"},{"id": 2, "marks": 65, "grade":"B"}]
var student=[{"id":1,"name":"john"},{"id": 2, "name": "anna"}]

实际场景中，student数组约有1000个元素，marks数组约有10000个元素。需求是匹配相同id的元素，为student数组中的每个元素添加第一个非null的marks和grade字段。当前用嵌套循环实现的时间复杂度为O(n*m)，效率偏低，需要优化。

预期结果：

var student=[{"id":1,"name":"john","marks":90,"grade":"A"},{"id": 2, "name": "anna", "marks": 65, "grade":"B"}]

优化方案 #

核心思路是预处理marks数组，构建id到目标字段的映射表，将时间复杂度降低到O(n+m)，大幅提升处理效率：

1. 预处理marks数组，生成id对应的非空成绩映射
   遍历marks数组，为每个id记录第一个出现的非空marks和grade，一旦某个id的两个字段都找到非空值，后续该id的元素直接跳过，减少不必要的遍历。

2. 遍历student数组，从映射表中取值合并
   直接通过id从映射表中获取对应的marks和grade，快速合并到学生对象中。

代码实现 #

// 1. 预处理marks数组，构建id到非空marks和grade的映射
const idToScoreMap = {};
for (const item of marks) {
  const { id, marks: currentMarks, grade: currentGrade } = item;
  // 如果该id已经凑齐了非空的marks和grade，直接跳过
  if (idToScoreMap[id]?.marks !== null && idToScoreMap[id]?.grade !== null) {
    continue;
  }
  // 初始化该id的存储对象
  if (!idToScoreMap[id]) {
    idToScoreMap[id] = { marks: null, grade: null };
  }
  // 填充第一个非空的marks
  if (idToScoreMap[id].marks === null && currentMarks !== null) {
    idToScoreMap[id].marks = currentMarks;
  }
  // 填充第一个非空的grade
  if (idToScoreMap[id].grade === null && currentGrade !== null) {
    idToScoreMap[id].grade = currentGrade;
  }
}

// 2. 遍历student数组，合并对应字段
const updatedStudents = student.map(student => {
  const scoreData = idToScoreMap[student.id] || {};
  return {
    ...student,
    marks: scoreData.marks ?? student.marks, // 兼容原student已有marks的情况
    grade: scoreData.grade ?? student.grade
  };
});

console.log(updatedStudents);

说明 #

• 预处理阶段仅需遍历一次marks数组（O(m)），后续查找操作都是O(1)的哈希表访问
• 遍历student数组是O(n)，总时间复杂度为O(n+m)，相比原来的O(nm)，在数据量较大时（比如100010000=10^7次操作 vs 11000次操作），性能提升非常明显
• 逻辑中加入了“凑齐非空值就跳过后续元素”的判断，进一步减少了不必要的处理步骤

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