JavaScript高效合并日期时间序列算法（适配AnyChart）

核心思路：多指针归并法 #

由于输入的每个时间序列都是按日期升序排列的，我们可以利用这一特性，采用多指针归并的方式实现线性时间复杂度的合并，避免先聚合再排序的额外开销。

具体步骤 #

1. 为每个时间序列初始化一个指针，初始值为0，用于追踪当前遍历到的位置。
2. 循环获取所有指针指向的有效日期（指针未越界的序列），找出其中最小的日期作为当前行的基准日期。
3. 针对该基准日期，遍历所有时间序列：
   • 如果当前序列的指针未越界且日期等于基准日期，取对应数值并将指针后移一位
   • 否则填充null
4. 将当前行加入结果数组，重复上述步骤，直到所有序列的指针都遍历完毕。

代码实现 #

function mergeTimeSeries(...series) {
  // 初始化每个序列的指针
  const pointers = Array(series.length).fill(0);
  const result = [];

  while (true) {
    // 收集所有当前指针指向的有效日期
    const currentDates = [];
    for (let i = 0; i < series.length; i++) {
      if (pointers[i] < series[i].length) {
        currentDates.push(series[i][pointers[i]][0]);
      }
    }

    // 所有序列都遍历完，退出循环
    if (currentDates.length === 0) break;

    // 找到最小的日期作为当前行的基准
    const minDate = Math.min(...currentDates);

    // 构建当前行
    const row = [minDate];
    for (let i = 0; i < series.length; i++) {
      const ptr = pointers[i];
      if (ptr < series[i].length && series[i][ptr][0] === minDate) {
        row.push(series[i][ptr][1]);
        pointers[i]++; // 指针后移
      } else {
        row.push(null);
      }
    }

    result.push(row);
  }

  return result;
}

// 测试用例
const ts1 = [
  ['2023-01-20', 1],
  ['2023-01-21', 2],
  ['2023-01-22', 3],
  ['2023-01-23', 4],
];

const ts2 = [
  ['2023-01-18', 5],
  ['2023-01-19', 6],
  ['2023-01-20', 7],
  ['2023-01-21', 8]
];

const ts3 = [
  ['2023-01-21', 9],
  ['2023-01-22', 10],
  ['2023-01-23', 11],
  ['2023-01-24', 12]
];

const output = mergeTimeSeries(ts1, ts2, ts3);
console.log(output);

复杂度分析 #

• 时间复杂度：O(M)，其中M是所有时间序列的元素总数。每个元素只会被访问一次，指针移动的总次数等于M。
• 空间复杂度：O(K)，K是合并后不同日期的数量（结果数组的行数），主要用于存储最终结果。

适配AnyChart tableData格式 #

上述代码的输出直接符合AnyChart要求的tableData结构，第一列为日期，后续列对应各时间序列的数值，缺失值用null填充，可直接用于图表渲染。

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