JavaScript中如何高效对比两个对象数组的quantity属性大小？

我有两个对象数组：detail 和 sale.detail，需要校验同一_id对应的元素中，detail数组的quantity属性是否大于sale.detail数组的quantity属性。

示例数组 #

Array detail #

[
  {
    "provider": { "uid": "6271a32082193f4b88e292f0", "name": "Genérico" },
    "_id": "628ff19af062bde6a9fd7a3b",
    "name": "MALBORO ARTESANAL \"20\"",
    "quantity": 6,
    "subtotal": 3156,
    "total": 0,
    "quantityOnBd": 6
  },
  {
    "provider": { "uid": "6271a32082193f4b88e292f0", "name": "Genérico" },
    "_id": "628fef9bf062bde6a9fd7986",
    "name": "MALBORO ROJO \"20\"",
    "quantity": 7,
    "subtotal": 4368,
    "total": 0,
    "quantityOnBd": 7
  }
]

Array sale.detail #

[
  {
    "provider": { "uid": "6271a32082193f4b88e292f0", "name": "Genérico" },
    "_id": "628fef9bf062bde6a9fd7986",
    "name": "MALBORO ROJO \"20\"",
    "quantity": 7,
    "subtotal": 4368,
    "total": 0
  },
  {
    "provider": { "uid": "6271a32082193f4b88e292f0", "name": "Genérico" },
    "_id": "628ff19af062bde6a9fd7a3b",
    "name": "MALBORO ARTESANAL \"20\"",
    "quantity": 6,
    "subtotal": 3156,
    "total": 0
  }
]

原实现代码（嵌套循环） #

for (let i = 0; i < detail.length; i++) {
    for (let j = 0; j < sale.detail.length; j++) {
        if (detail[i]['_id'] === sale.detail[j]['_id']) {
            if (detail[i]['quantity'] > sale.detail[j]['quantity']) {
                return res.status(400).json({msg:'No puedes regresar mas de la cantidad original'});
            }
        }
    }
}

高效优化方案 #

方案1：使用普通对象构建映射表 #

通过将sale.detail转换为以_id为键、quantity为值的对象，把嵌套循环的O(n*m)时间复杂度降低到O(n+m)的线性复杂度：

// 构建sale.detail的id-quantity映射
const saleQuantityMap = {};
for (const item of sale.detail) {
  saleQuantityMap[item._id] = item.quantity;
}

// 遍历detail数组完成校验
for (const item of detail) {
  const saleQuantity = saleQuantityMap[item._id];
  // 可根据业务需求处理_id不存在的情况，比如返回错误或跳过
  if (saleQuantity !== undefined && item.quantity > saleQuantity) {
    return res.status(400).json({msg:'No puedes regresar mas de la cantidad original'});
  }
}

方案2：使用ES6 Map构建映射 #

如果需要处理更复杂的键类型（比如非字符串），ES6的Map会更合适，用法和普通对象类似：

// 构建sale.detail的id-quantity映射
const saleQuantityMap = new Map();
for (const item of sale.detail) {
  saleQuantityMap.set(item._id, item.quantity);
}

// 遍历detail数组完成校验
for (const item of detail) {
  const saleQuantity = saleQuantityMap.get(item._id);
  if (saleQuantity !== undefined && item.quantity > saleQuantity) {
    return res.status(400).json({msg:'No puedes regresar mas de la cantidad original'});
  }
}

效率说明 #

原嵌套循环的时间复杂度是O(n*m)，当两个数组的元素数量较大时，性能会急剧下降；优化后的方案通过一次遍历构建映射、一次遍历校验，总时间复杂度为O(n+m)，在数据量越大的场景下，性能提升越明显。

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