如何在JS中高效合并时间戳不匹配的多组时间序列数组？

方案选型说明 #

针对单数组已按时间戳升序排列、时间轴非完全对齐的合并场景，有两种高性能实现方案：

• 哈希映射法：代码实现极简，适合中小数据量（总数据点<100万），时间复杂度O(N)，N为所有数组的总数据点数
• 多指针归并法：无额外哈希、排序开销，内存占用更低，适合超大规模数据量，时间复杂度同样O(N)

方案1：哈希映射实现（推荐大部分场景使用） #

实现逻辑：遍历所有数组，以时间戳为键存储对应位置的数值，最后将所有时间戳升序排序后转成结果数组即可。

function mergeTimeSeries(arrays) {
  const tsMap = new Map();
  const arrayCount = arrays.length;

  // 遍历所有数组填充映射表
  for (let arrIndex = 0; arrIndex < arrayCount; arrIndex++) {
    const currentArr = arrays[arrIndex];
    for (const [timestamp, value] of currentArr) {
      if (!tsMap.has(timestamp)) {
        tsMap.set(timestamp, new Array(arrayCount).fill(null));
      }
      tsMap.get(timestamp)[arrIndex] = value;
    }
  }

  // 按时间戳升序输出结果
  return Array.from(tsMap.entries())
    .sort((a, b) => a[0] - b[0])
    .map(([timestamp, values]) => [timestamp, ...values]);
}

// 测试示例
const arr1 = [
  [1637837518000, 1.7],
  [1637837519000, 0.1],
  [1637837520000, 1.3],
  [1637837521000, 6.4],
  [1637837522000, 2.2],
  [1637837523000, 2.1]
];
const arr2 = [
  [1637837517000, 600.32],
  [1637837520000, 578.98],
  [1637837523000, 612.76]
];
const arr3 = [
  [1637837518000, 45.3],
  [1637837520000, 34.8],
  [1637837522000, 40.0],
  [1637837524000, 41.5]
];

const result = mergeTimeSeries([arr1, arr2, arr3]);
console.log(result); // 输出完全匹配预期结果

方案2：多指针归并实现（适合超大数据量场景） #

实现逻辑：利用单数组已排序的特性，采用K路归并思路，每个数组维护一个遍历指针，每次取所有指针当前指向的最小时间戳，填充对应位置的数值后移动匹配到的指针，全程无额外排序开销。

function mergeTimeSeriesKWay(arrays) {
  const arrayCount = arrays.length;
  const pointers = new Array(arrayCount).fill(0);
  const result = [];

  while (true) {
    let minTimestamp = Infinity;
    // 查找当前所有指针指向的最小时间戳
    for (let i = 0; i < arrayCount; i++) {
      if (pointers[i] < arrays[i].length) {
        const currentTs = arrays[i][pointers[i]][0];
        if (currentTs < minTimestamp) minTimestamp = currentTs;
      }
    }
    // 所有数组遍历完成则退出循环
    if (minTimestamp === Infinity) break;

    const row = new Array(arrayCount).fill(null);
    // 填充当前时间戳对应数值，移动匹配到的指针
    for (let i = 0; i < arrayCount; i++) {
      if (pointers[i] < arrays[i].length && arrays[i][pointers[i]][0] === minTimestamp) {
        row[i] = arrays[i][pointers[i]][1];
        pointers[i]++;
      }
    }
    result.push([minTimestamp, ...row]);
  }
  return result;
}

性能对比 #

• 哈希法：代码易维护，中小数据量下性能表现优异，仅在总时间戳量级超过百万级时，最后的排序步骤会产生额外开销
• 多指针归并法：无哈希存储和排序开销，数据量越大性能优势越明显，输入数组数量少于10个时是最优选择

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