JavaScript动态多键数据场景下排他过滤器集合的性能优化方案问询

原始实现问题说明 #

原始代码除了时间复杂度高，逻辑也不符合需求：原始实现会保留所有满足过滤条件的数据，而需求是剔除满足所有过滤条件的数据、保留剩余数据。

通用业务场景优化方案 #

核心优化点 #

• 预处理合并同键的过滤器规则，避免重复判断相同键的过滤条件
• 仅遍历过滤器的唯一键进行匹配，无需遍历数据对象的全部键，大部分场景下过滤器的唯一键数量远小于数据对象的平均键数
• 匹配过程中提前终止，只要有一个过滤条件不满足就停止判断剩余规则

代码实现 #

function getExclusive(data, filters) {
  // 预处理过滤器：合并相同键的过滤值，复杂度O(F) F为过滤器总数
  const filterMap = new Map();
  for (const { k, v } of filters) {
    if (!filterMap.has(k)) {
      filterMap.set(k, new Set());
    }
    filterMap.get(k).add(v);
  }
  const filterKeys = Array.from(filterMap.keys());

  // 遍历数据集筛选，复杂度O(D * K) K为过滤器唯一键数量
  return data.filter(datum => {
    let allRulesMatched = true;
    for (const key of filterKeys) {
      // 任意规则不匹配就提前终止
      if (!filterMap.get(key).has(datum[key])) {
        allRulesMatched = false;
        break;
      }
    }
    // 仅未命中所有过滤规则的数据保留
    return !allRulesMatched;
  });
}

极端场景适配说明 #

不存在绝对通用的最优解，需根据业务场景选择适配方案：

• 若数据固定、过滤器频繁变化：可提前为数据建立倒排索引，键为${属性名}:${属性值}，值为对应数据的索引集合，每次查询时先求所有过滤规则的交集，再从总数据中排除交集即可，单次查询复杂度可低至O(F)
• 若数据对象平均键数远小于过滤器唯一键数：可改为遍历数据对象的键匹配过滤规则，能获得更好的性能
• 若数据量极大且允许异步计算：可使用Array.prototype.reduce结合分块处理，避免主线程阻塞。

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