JS中高效统计数组内匹配对象数量的优化方案问询

你的原方案通过嵌套遍历（fruits.map里嵌套items.filter）实现统计，时间复杂度为O(m*n)（m是fruits长度，n是items长度），当数组规模较大时会明显影响性能。下面是更高效的优化方案，时间复杂度可降至O(m+n)：

优化思路 #

1. 先遍历一次items数组，用哈希表（对象/Map）统计每种水果的出现次数，后续查询次数为O(1)
2. 再遍历fruits数组，直接从哈希表中获取对应水果的计数，不存在则返回0

实现代码 #

const items = [
  { id: '111', name: 'apple' },
  { id: '222', name: 'apple' },
  { id: '333', name: 'kiwi' },
];

const fruits = [
  { id: 'fruit-1', name: 'apple' },
  { id: 'fruit-2', name: 'banana' },
  { id: 'fruit-3', name: 'kiwi' },
];

// 第一步：构建items中水果名称的计数映射
const fruitCountMap = items.reduce((acc, { name }) => {
  acc[name] = (acc[name] || 0) + 1;
  return acc;
}, {});

// 第二步：遍历fruits数组，匹配计数
const numberOfFruitsInItems = fruits.map(fruit => ({
  ...fruit,
  total: fruitCountMap[fruit.name] || 0
}));

console.log(numberOfFruitsInItems);
// 输出结果与期望一致：
// [
//   { id: 'fruit-1', name: 'apple', total: 2 },
//   { id: 'fruit-2', name: 'banana', total: 0 },
//   { id: 'fruit-3', name: 'kiwi', total: 1 }
// ]

方案优势 #

• 仅需两次线性遍历，避免了嵌套遍历的性能损耗
• 哈希表的查询操作是常数时间，即使items和fruits规模大幅增长，性能依然稳定
• 代码简洁易读，逻辑清晰

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