如何获取两个数组的增量变化以实现状态回退与前进？

你的思路完全合理：通过记录数组前后状态的增量差异替代全量存储，能有效降低内存消耗，尤其适合元素数量多、操作频繁的场景。下面给出具体的实现方案和优化建议：

核心思路：基于最长公共子序列（LCS）推导差异 #

这类序列比对问题的经典解法是通过**最长公共子序列（LCS）**定位前后数组的公共元素，剩余部分即为需要记录的增删改操作。公共元素无需操作，仅需记录非公共部分的变化。

具体实现步骤 #

1. 计算LCS：找出前后数组中连续/非连续的公共元素序列，这部分是状态不变的核心。
2. 推导差异操作：
   • 遍历原数组，不在LCS中的元素标记为delete操作（索引为原数组中的位置）。
   • 遍历新数组，不在LCS中的元素标记为insert操作（索引为新数组中的位置）。
   • 针对相同索引但内容不同的元素，优先标记为update操作（避免用"删+插"两次操作替代）。

代码示例（JavaScript） #

// 计算数组差异的核心函数
function getArrayDiff(before, after, compare = (a, b) => a === b) {
  const diffs = [];
  const lcs = findLCS(before, after, compare);
  
  let beforeIdx = 0;
  let afterIdx = 0;
  let lcsIdx = 0;

  // 先推导基础的增删操作
  while (beforeIdx < before.length || afterIdx < after.length) {
    const isBeforeInLCS = lcsIdx < lcs.length && compare(before[beforeIdx], lcs[lcsIdx]);
    const isAfterInLCS = lcsIdx < lcs.length && compare(after[afterIdx], lcs[lcsIdx]);

    if (beforeIdx < before.length && !isBeforeInLCS) {
      // 原数组元素不在LCS，标记删除
      diffs.push(['delete', beforeIdx, before[beforeIdx]]);
      beforeIdx++;
    } else if (afterIdx < after.length && !isAfterInLCS) {
      // 新数组元素不在LCS，标记插入
      diffs.push(['insert', afterIdx, after[afterIdx]]);
      afterIdx++;
    } else {
      // 公共元素，同步移动指针
      beforeIdx++;
      afterIdx++;
      lcsIdx++;
    }
  }

  // 补充处理更新操作（替换冗余的删+插）
  const updateMap = new Map();
  // 先收集相同索引但内容不同的元素
  for (let i = 0; i < Math.min(before.length, after.length); i++) {
    if (!compare(before[i], after[i])) {
      updateMap.set(i, [before[i], after[i]]);
    }
  }

  // 过滤掉已被标记为update的删插操作，替换为update
  const filteredDiffs = diffs.filter(diff => {
    if (diff[0] === 'delete' && updateMap.has(diff[1])) {
      const [oldItem, newItem] = updateMap.get(diff[1]);
      diffs.push(['update', diff[1], oldItem, newItem]);
      updateMap.delete(diff[1]);
      return false;
    }
    return true;
  });

  // 补充剩余的update操作
  return filteredDiffs.concat(
    Array.from(updateMap.entries()).map(([idx, [oldItem, newItem]]) => 
      ['update', idx, oldItem, newItem]
    )
  );
}

// 辅助函数：计算最长公共子序列
function findLCS(a, b, compare) {
  const dp = Array(a.length + 1).fill().map(() => Array(b.length + 1).fill(0));
  
  // 填充DP表
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (compare(a[i-1], b[j-1])) {
        dp[i][j] = dp[i-1][j-1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
      }
    }
  }

  // 回溯构建LCS
  let i = a.length, j = b.length;
  const lcs = [];
  while (i > 0 && j > 0) {
    if (compare(a[i-1], b[j-1])) {
      lcs.unshift(a[i-1]);
      i--;
      j--;
    } else if (dp[i-1][j] > dp[i][j-1]) {
      i--;
    } else {
      j--;
    }
  }
  return lcs;
}

// 测试示例
const before = [0,1,2,3];
const after = [1,3,5];
console.log(getArrayDiff(before, after));
// 输出：[ ['delete', 0, 0], ['delete', 2, 2], ['insert', 2, 5] ]

关键优化点 #

• 自定义元素比较：如果数组元素是复杂对象，可传入自定义的compare函数（比如基于对象的id字段对比），避免直接用===导致的误判。
• 性能适配：LCS算法的时间复杂度为O(n*m)，对于100级别的元素完全无压力；若元素数量超过1000，可针对有序数组场景改用线性时间的差分算法。
• 回退/前进逻辑：
  • 回退操作：反向执行diff（delete转为insert，insert转为delete，update恢复旧值）。
  • 前进操作：正向执行diff即可。

对您设计的diff格式的补充建议 #

您定义的[action, index, item]格式清晰可用，建议补充update操作的格式为['update', index, oldItem, newItem]，这样能避免用两次操作表示一次更新，进一步提升效率和可读性。

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