如何优化excludeItems函数？现有两种实现求更优解

需求说明 #

编写一个名为excludeItems的函数：

• 第一个入参是数据集（对象数组）
• 第二个入参是需排除的键值属性（对象数组）
• 返回排除指定键值属性后的数组

示例代码 #

const items = [
  { color: 'red', type: 'tv', age: 18 },
  { color: 'red', type: 'phone', age: 20 },
  { color: 'silver', type: 'tv', age: 18 },
  { color: 'silver', type: 'phone', age: 20 }
];

const excludes = [
  { k: 'color', v: 'red' },
  { k: 'color', v: 'blue' },
  { k: 'type', v: 'phone' },
];

expectedOutput = [
  { type: 'tv', age: 18 },
  { age: 20 },
  { color: 'silver', type: 'tv', age: 18 },
  { color: 'silver',  age: 20 }
];

现有实现 #

我已经写出两种相似的解决方案，个人觉得第二种略优——不需要遍历值列表检查原对象的值是否存在。想请教有没有更高效的实现方式？

方案1 #

// Option 1
function excludeItems(items, excludes) {
  let exclusionMap = {};
  let results = [];

  excludes.forEach(item => {
    if(!exclusionMap[item.k])
        exclusionMap[item.k] = [];
     
    let itemDoesNotExist = exclusionMap[item.k].indexOf(item.v) === -1;
    if(itemDoesNotExist) {
        exclusionMap[item.k].push(item.v);
    }
  })
  
  results = items.map(item => {
    for(let key in exclusionMap) {
      let exclusionValues = exclusionMap[key];
      if(item[key]) {
        let itemValue = item[key]
        let itemValueIndexInExclusionValue = exclusionValues.indexOf(itemValue);
        
        if(itemValueIndexInExclusionValue !== -1) {
            delete item[key];
        }
      }
    }
    
    return item;
  });
  
  return results;
}

方案2 #

// Option 2
function excludeItems(items, excludes) {
    let exclusionMap = {};
  let results = [...items];
  
  excludes.forEach(item => {
    exclusionMap[item.k + '_' + item.v] = true;
  })
  
  
  results.map(item => {
    for(const key in exclusionMap) {
      const k = key.split('_')[0]; // type
      const v = key.split('_')[1]; // phone
      if(v == item[k]) {
        delete item[k]
      }
    }
    return item;
  })
  return results;
}

更优实现建议 #

现有方案存在两个明显痛点：方案1用数组存排除值，indexOf是O(n)查找效率低；方案2用k_v拼接键，若键/值本身包含_会导致拆分错误。推荐以下两种优化方案：

优化方案一：嵌套Set映射（高效无冲突） #

function excludeItems(items, excludes) {
  // 构建嵌套排除规则：{ 键名: Set(需排除的值集合) }
  const exclusionMap = {};
  excludes.forEach(({ k, v }) => {
    if (!exclusionMap[k]) {
      exclusionMap[k] = new Set();
    }
    exclusionMap[k].add(v);
  });

  // 生成新对象，避免修改原数据
  return items.map(item => {
    const newItem = { ...item };
    for (const key in exclusionMap) {
      if (newItem.hasOwnProperty(key) && exclusionMap[key].has(newItem[key])) {
        delete newItem[key];
      }
    }
    return newItem;
  });
}

优化点说明

• O(1)查找效率：Set.has()是常数时间操作，远快于数组indexOf的线性查找
• 避免原数据污染：用{ ...item }创建新对象，不会改动原数组的对象引用
• 无键冲突风险：嵌套结构不会因为键/值包含特殊字符出错
• 自动去重规则：Set会自动过滤excludes中的重复规则，无需手动判断

优化方案二：预存需检查的键（极致性能） #

如果数据集和排除规则很大，可以进一步减少循环次数：

function excludeItems(items, excludes) {
  const exclusionMap = {};
  const exclusionKeys = new Set(); // 预存所有需要检查的键

  excludes.forEach(({ k, v }) => {
    if (!exclusionMap[k]) {
      exclusionMap[k] = new Set();
      exclusionKeys.add(k);
    }
    exclusionMap[k].add(v);
  });

  return items.map(item => {
    const newItem = { ...item };
    // 只遍历需要检查的键，跳过无关键
    exclusionKeys.forEach(key => {
      if (newItem[key] && exclusionMap[key].has(newItem[key])) {
        delete newItem[key];
      }
    });
    return newItem;
  });
}

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