优化带装饰文本节点合并算法求助：现有低效实现需改进

问题描述 #

需要合并两个带装饰的文本节点数组，每个节点包含文本、装饰（颜色、字体样式等）以及from/to索引，要求保持文本内容不变，同时合并装饰效果。当前算法遍历每个字符并为单个字符创建节点，效率极低，需优化。

当前低效算法代码 #

const getDecorationsByIndex = (nodes, index) => {
  const foundNodes: any[] = [];

  nodes.forEach(node => {
    if (index >= node.from && index < node.to) {
      foundNodes.push(node);
    }
  });

  return foundNodes.flatMap(node => node.textData?.decorations || []);
};

const mergeNodes = (nodes1, nodes2, content) => {
  const mergedNodes = [...content].map((s, index) => {
    const decorations1 = getDecorationsByIndex(nodes1, index);
    const decorations2 = getDecorationsByIndex(nodes2, index);

    return {
      id: '',
      nodes: [],
      type: Node_Type.TEXT,
      textData: {
        decorations: [...decorations1, ...decorations2],
        text: s,
      },
    };
  });

  return mergedNodes;
};

示例场景 #

文本内容为def：

• 第一组节点（加粗效果）：

[
  {
      "type": "TEXT",
      "id": "",
      "nodes": [],
      "textData": {
          "text": "de",
          "decorations": [
              {
                  "type": "BOLD",
                  "fontWeightValue": 700
              }
          ]
      },
      "from": 0,
      "to": 2
  },
  {
      "type": "TEXT",
      "id": "",
      "nodes": [],
      "textData": {
          "text": "f",
          "decorations": []
      },
      "from": 2,
      "to": 3
  }
]

• 第二组节点（颜色效果）：

[
  {
      "id": "",
      "nodes": [],
      "type": "TEXT",
      "textData": {
          "decorations": [
              {
                  "type": "COLOR",
                  "colorData": {
                      "foreground": "#d73a49"
                  }
              }
          ],
          "text": "def"
      },
      "from": 0,
      "to": 3
  }
]

• 期望合并结果：

[
  {
      "type": "TEXT",
      "id": "",
      "nodes": [],
      "textData": {
          "text": "de",
          "decorations": [
              {
                  "type": "BOLD",
                  "fontWeightValue": 700
              },{
                  "type": "COLOR",
                  "colorData": {
                      "foreground": "#d73a49"
                  }
              }
          ]
      },
      "from": 0,
      "to": 2
  },
  {
      "type": "TEXT",
      "id": "",
      "nodes": [],
      "textData": {
          "text": "f",
          "decorations": [{
                  "type": "COLOR",
                  "colorData": {
                      "foreground": "#d73a49"
                  }
              }]
      },
      "from": 2,
      "to": 3
  }
]

优化思路与方案 #

1. 提取关键分割点 #

收集两组节点所有的from和to值，去重排序后得到文本区间的所有分割边界。比如示例中的分割点为0、2、3，这样只需处理分割后的连续区间，而非逐个字符。

2. 批量计算区间装饰 #

对每个分割出的区间[start, end)，一次性筛选覆盖该区间的节点，合并其装饰集合，避免逐个字符查询的冗余操作。

3. 生成合并节点 #

根据区间的起止位置、合并后的装饰集合、对应文本内容，生成最终的合并节点。

优化后代码示例 #

const mergeNodesOptimized = (nodes1, nodes2, content) => {
  // 收集所有分割点
  const splitPoints = new Set<number>();
  [...nodes1, ...nodes2].forEach(node => {
    splitPoints.add(node.from);
    splitPoints.add(node.to);
  });
  // 排序分割点
  const sortedPoints = Array.from(splitPoints).sort((a, b) => a - b);
  
  const mergedNodes = [];
  
  for (let i = 0; i < sortedPoints.length - 1; i++) {
    const start = sortedPoints[i];
    const end = sortedPoints[i + 1];
    if (start >= end) continue; // 跳过无效区间
    
    // 获取当前区间在两组节点中的所有装饰
    const decorations1 = nodes1
      .filter(node => node.from <= start && node.to >= end)
      .flatMap(node => node.textData?.decorations || []);
    
    const decorations2 = nodes2
      .filter(node => node.from <= start && node.to >= end)
      .flatMap(node => node.textData?.decorations || []);
    
    // 合并装饰（可按需添加同类型装饰去重逻辑）
    const mergedDecorations = [...decorations1, ...decorations2];
    
    // 提取区间文本
    const text = content.slice(start, end);
    
    mergedNodes.push({
      id: '',
      nodes: [],
      type: Node_Type.TEXT,
      textData: {
        decorations: mergedDecorations,
        text: text,
      },
      from: start,
      to: end,
    });
  }
  
  return mergedNodes;
};

额外优化点 #

• 装饰去重逻辑：如果存在同类型装饰（如两个COLOR），可按业务规则保留优先级高的（比如nodes2覆盖nodes1），用Map实现：

  const decorationMap = new Map();
  decorations1.forEach(deco => decorationMap.set(deco.type, deco));
  decorations2.forEach(deco => decorationMap.set(deco.type, deco));
  const mergedDecorations = Array.from(decorationMap.values());
  

• 双指针筛选节点：若输入节点数组已按from排序，可使用双指针法快速定位覆盖当前区间的节点，进一步减少遍历次数。

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