JavaScript中以低于O(n²)复杂度实现两对象数组条件过滤

JavaScript开发中存在两个对象数组A、B，结构示例如下：

const A = [
     {
         "isAvailable" : true,
         "productCode" : "12103977",
         "size" : "UK/IND-3",
         "url" : "/asics-mens-gel-kayano-28-harmony-blue-running-shoes/12103977"
      },
      {
         "isAvailable" : true,
         "productCode" : "12103978",
         "size" : "UK/IND-4",
         "url" : "/asics-mens-gel-kayano-28-harmony-blue-running-shoes/12103978"
      },
      {
         "isAvailable" : true,
         "productCode" : "12103979",
         "size" : "UK/IND-8",
         "url" : "/asics-mens-gel-kayano-28-harmony-blue-running-shoes/12103979"
      },
]

const B = [
       {
         "dimensionSize" : "3",
         "euroSize" : "36",
         "usSize" : "4"
      },
      {
         "dimensionSize" : "4",
         "euroSize" : "36",
         "usSize" : "4"
      },
      {
         "dimensionSize" : "10",
         "euroSize" : "36",
         "usSize" : "4"
      },
]

需要生成新数组C，过滤规则为：若数组A中任意对象的size字段值，包含数组B中某对象的dimensionSize字段值，则将B中该匹配对象加入数组C。按上述规则得到的预期C数组示例如下：

const C = [
      {
         "dimensionSize" : "3", 
         "euroSize" : "36",
         "usSize" : "4"
      },
      {
         "dimensionSize" : "4", 
         "euroSize" : "36",
         "usSize" : "4"
      },
]

当前已有实现采用filter+forEach嵌套遍历的写法，时间复杂度为O(n²)，代码如下：

let matchArray;
matchArray = B.filter(objB => {
    let match = false;
    A.forEach(objA => {
        if (objA.size.includes(objB.dimensionSize)) {
            match = true;
        }
    });
    return match;
});

由于实际业务中数组长度极大，该O(n²)复杂度的实现无法满足实时数据处理的性能要求，需要时间复杂度低于O(n²)的高效实现方案。

核心优化思路是空间换时间+减少重复遍历，根据业务场景可以选择两种落地实现：

方案1：枚举值去重遍历（适配99%的业务场景，如尺码、分类等固定枚举值场景） #

这类场景下dimensionSize是有限枚举值（比如鞋码通常只有20~30个可选值），去重后基数极小，整体时间复杂度可以降到O(len(A) + len(B))，实现成本极低：

// 1. 提取B中所有dimensionSize并去重，避免重复判断相同值
const dimUniqueValues = [...new Set(B.map(item => item.dimensionSize))];
const hitDimSet = new Set();

for (const objA of A) {
  const currentSize = objA.size;
  // 遍历去重后的枚举值，检查是否被当前size包含
  for (const dim of dimUniqueValues) {
    if (currentSize.includes(dim)) {
      hitDimSet.add(dim);
    }
  }
  // 所有枚举值都已经命中，提前终止A的遍历，减少无效计算
  if (hitDimSet.size === dimUniqueValues.length) break;
}

// 2. 一次遍历B，过滤出命中的项即可，Set查找时间复杂度为O(1)
const C = B.filter(objB => hitDimSet.has(objB.dimensionSize));

以10000条A数据、10000条B数据、30个枚举尺码为例，总计算量约为30*10000 + 10000 = 31万次，相比原O(n²)实现的1亿次计算，性能提升300倍以上。

方案2：AC自动机多模式匹配（适配通用极端场景） #

如果业务中dimensionSize无固定枚举范围、去重后量级和数组长度相当，可以用AC自动机实现多模式匹配，把所有A的size作为匹配目标串，所有dimensionSize作为模式串，一次扫描即可得到所有命中值，整体时间复杂度为线性，适合超大数据量场景。

内容的提问来源于stack exchange，提问作者utkarsh-k