如何高效实现含嵌套文档的两个对象数组的深度合并？

问题 #

我有两个对象数组：publications和documentPrices，结构如下：

const publications = [
  {
    id: "publication1",
    documents: [
      {
        id: "document1",
        priceId: "abc",
      },
      {
        id: "document2",
        priceId: "xyz",
      },
    ],
  },
  {
    id: "publication2",
    documents: [
      {
        id: "document3",
        priceId: "abc",
      },
      {
        id: "document4",
        priceId: "xyz",
      },
    ],
  },
]

const documentPrices = [
  { priceId: "abc", priceUsd: 100, priceEur: 120 },
  { priceId: "xyz", priceUsd: 10, priceEur: 12 },
]

期望输出：

const publicationsFinal = [
  {
    id: "publication1",
    documents: [
      {
        id: "document 1",
        priceId: "abc",
        priceUsd: 100,
        priceEur: 120,
      },
      {
        id: "document 2", 
        priceId: "xyz",
        priceUsd: 10,
        priceEur: 12,
      },
    ],
  },
  {
    id: "publication2",
    documents: [
      {
        id: "document 3",
        priceId: "abc",
        priceUsd: 100,
        priceEur: 120,
      },
      {
        id: "document 4",
        priceId: "xyz",
        priceUsd: 10,
        priceEur: 12,
      },
    ],
  },
]

目前用三层嵌套循环实现，效率极低，求高效实现方式。

高效实现方案 #

核心思路是先把documentPrices转换成以priceId为键的Map，将价格查找的时间复杂度从O(n)降至O(1)，之后只需遍历一次publications数组即可完成数据合并，整体时间复杂度为O(m + n)（m是publications中所有document的总数，n是documentPrices的长度），远优于嵌套循环的O(m*n)。

具体实现步骤：

1. 构建价格映射表：用Map将documentPrices转换为键为priceId、值为对应价格对象的映射结构。
2. 遍历处理publications：对每个出版物的documents数组做批量处理，包括调整id格式、合并对应价格信息。

代码示例：

// 构建价格映射表，O(n)时间复杂度
const priceMap = new Map(documentPrices.map(item => [item.priceId, item]));

// 生成最终结果，O(m)时间复杂度
const publicationsFinal = publications.map(publication => ({
  ...publication,
  documents: publication.documents.map(doc => {
    // 调整document id格式：documentX -> document X
    const formattedId = doc.id.replace(/(\d+)$/, ' $1');
    // 获取对应价格信息，无匹配则返回空对象
    const priceInfo = priceMap.get(doc.priceId) || {};
    // 合并对象，保留原document属性的同时添加价格字段
    return {
      ...doc,
      id: formattedId,
      ...priceInfo
    };
  })
}));

这段代码不会修改原数组，而是生成全新的结果对象，同时保证了高效性，适合处理大规模数据场景。

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