TypeScript实现ZigZag指标：新增Bar时如何避免全量重算？

我正在尝试用TypeScript实现ZigZag指标，我的ZigZagCalculation函数接收Bar[]类型的K线数组和deviation（偏差阈值）作为参数，返回所有ZigZag点的集合。我的K线数组容量固定为x，新增K线时会插入到数组的首个索引位置，同时移除数组末尾的元素。我的问题是：当新增K线时，能否仅计算数组的两个新端点，而非遍历整个数组（O(n)复杂度），以此避免重新计算整个ZigZag指标？目前我的常规实现会返回如下结构的对象：

{
 highPoints: {
  index: number;
  price: Bar
 }[];
 lowPoints: {
  index: number;
  price: Bar
 }[];
}

可以实现增量计算，但不能只单纯计算两个新端点——你需要回溯最近的ZigZag转折点，验证新K线是否能推翻已有的转折点，而非仅处理数组首尾的新元素。以下是具体的实现思路和关键逻辑：

核心思路：维护状态而非全量遍历 #

要避免O(n)的全量计算，你需要额外维护ZigZag的当前状态，包括：

• 最近的一个正式ZigZag转折点（高点/低点）
• 该转折点之后的临时极值（未达到偏差阈值的潜在转折点）
• 已记录的所有高点/低点集合

每次新增K线时，只需要基于这个状态做局部更新，而非重新扫描整个数组。

具体步骤 #

1. 处理新插入的K线（数组首位） #

新K线插入后，所有原有元素的索引都会+1，先批量更新已记录的ZigZag点的索引（这一步是O(k)，k为ZigZag点数量，远小于数组长度n）。

然后根据最近的转折点类型，更新临时极值并验证是否触发新的正式转折点：

• 如果最近是低点：追踪临时高点，若新K线的高点超过当前临时高点则更新；当该高点与最近低点的差值达到deviation时，将临时高点转为正式ZigZag高点，同时开始追踪新的临时低点。
• 如果最近是高点：追踪临时低点，若新K线的低点低于当前临时低点则更新；当该低点与最近高点的差值达到deviation时，将临时低点转为正式ZigZag低点，同时开始追踪新的临时高点。

关键：回溯验证
新生成的正式转折点可能会导致前一个转折点不再满足偏差要求（比如新高点和前前低点的差值不足），这时需要删除前一个转折点，继续向前回溯验证，直到所有相邻转折点都符合阈值。

2. 处理被移除的末尾K线 #

只有当被移除的K线是已记录的ZigZag点时，才需要处理：

• 从highPoints或lowPoints中删除该点
• 从删除点的前一个有效转折点开始，重新追踪后续的临时极值（局部遍历，范围有限）

关键代码示例 #

// 定义ZigZag状态结构
interface ZigZagState {
  lastType: 'high' | 'low' | null; // 最近正式转折点的类型
  lastPoint: { index: number; price: Bar } | null; // 最近正式转折点
  tempExtreme: { index: number; price: Bar } | null; // 当前追踪的临时极值
  highPoints: Array<{ index: number; price: Bar }>; // 所有正式高点
  lowPoints: Array<{ index: number; price: Bar }>; // 所有正式低点
}

// 初始化状态
let zigZagState: ZigZagState = {
  lastType: null,
  lastPoint: null,
  tempExtreme: null,
  highPoints: [],
  lowPoints: []
};

// 增量更新ZigZag的函数
function updateZigZag(newBar: Bar, deviation: number, barArray: Bar[]): ZigZagState {
  // 更新已有ZigZag点的索引（新Bar插在首位，旧元素索引+1）
  zigZagState.highPoints.forEach(p => p.index += 1);
  zigZagState.lowPoints.forEach(p => p.index += 1);

  const newIndex = 0;
  // 初始状态处理
  if (!zigZagState.lastPoint) {
    zigZagState.tempExtreme = { index: newIndex, price: newBar };
    return zigZagState;
  }

  // 根据最近转折点类型处理新Bar
  if (zigZagState.lastType === 'low') {
    // 追踪临时高点
    if (newBar.high > zigZagState.tempExtreme!.price.high) {
      zigZagState.tempExtreme = { index: newIndex, price: newBar };
    }
    // 检查是否达到偏差阈值
    const priceDiff = zigZagState.tempExtreme!.price.high - zigZagState.lastPoint.price.low;
    if (priceDiff >= deviation) {
      // 转为正式高点
      const newHigh = { ...zigZagState.tempExtreme! };
      zigZagState.highPoints.unshift(newHigh);
      zigZagState.lastType = 'high';
      zigZagState.lastPoint = newHigh;
      zigZagState.tempExtreme = { index: newIndex, price: newBar };

      // 回溯验证前一个低点是否有效
      while (zigZagState.lowPoints.length && zigZagState.highPoints.length) {
        const prevLow = zigZagState.lowPoints[zigZagState.lowPoints.length - 1];
        const currentHigh = zigZagState.highPoints[0];
        if (currentHigh.price.high - prevLow.price.low < deviation) {
          zigZagState.lowPoints.pop();
          zigZagState.lastPoint = zigZagState.lowPoints[zigZagState.lowPoints.length - 1] || null;
          zigZagState.lastType = zigZagState.lastPoint ? 'low' : null;
        } else {
          break;
        }
      }
    }
  } else if (zigZagState.lastType === 'high') {
    // 追踪临时低点
    if (newBar.low < zigZagState.tempExtreme!.price.low) {
      zigZagState.tempExtreme = { index: newIndex, price: newBar };
    }
    const priceDiff = zigZagState.lastPoint.price.high - zigZagState.tempExtreme!.price.low;
    if (priceDiff >= deviation) {
      const newLow = { ...zigZagState.tempExtreme! };
      zigZagState.lowPoints.unshift(newLow);
      zigZagState.lastType = 'low';
      zigZagState.lastPoint = newLow;
      zigZagState.tempExtreme = { index: newIndex, price: newBar };

      // 回溯验证前一个高点是否有效
      while (zigZagState.highPoints.length && zigZagState.lowPoints.length) {
        const prevHigh = zigZagState.highPoints[zigZagState.highPoints.length - 1];
        const currentLow = zigZagState.lowPoints[0];
        if (prevHigh.price.high - currentLow.price.low < deviation) {
          zigZagState.highPoints.pop();
          zigZagState.lastPoint = zigZagState.highPoints[zigZagState.highPoints.length - 1] || null;
          zigZagState.lastType = zigZagState.lastPoint ? 'high' : null;
        } else {
          break;
        }
      }
    }
  }

  // 处理被移除的末尾Bar
  const removedIndex = barArray.length - 1;
  const removedBar = barArray[removedIndex];

  // 检查是否是高点
  const highIdx = zigZagState.highPoints.findIndex(p => p.index === removedIndex);
  if (highIdx !== -1) {
    zigZagState.highPoints.splice(highIdx, 1);
    resetTempExtreme(removedIndex, barArray, deviation);
  }

  // 检查是否是低点
  const lowIdx = zigZagState.lowPoints.findIndex(p => p.index === removedIndex);
  if (lowIdx !== -1) {
    zigZagState.lowPoints.splice(lowIdx, 1);
    resetTempExtreme(removedIndex, barArray, deviation);
  }

  return zigZagState;
}

// 移除ZigZag点后重置临时极值
function resetTempExtreme(removedIndex: number, barArray: Bar[], deviation: number) {
  zigZagState.lastPoint = zigZagState.highPoints[zigZagState.highPoints.length - 1] 
    || zigZagState.lowPoints[zigZagState.lowPoints.length - 1] 
    || null;
  zigZagState.lastType = zigZagState.lastPoint 
    ? (zigZagState.highPoints.includes(zigZagState.lastPoint) ? 'high' : 'low') 
    : null;

  if (!zigZagState.lastPoint) {
    zigZagState.tempExtreme = { index: 0, price: barArray[0] };
    return;
  }

  zigZagState.tempExtreme = zigZagState.lastPoint;
  // 从最近转折点向前遍历，重新找临时极值
  for (let i = zigZagState.lastPoint.index - 1; i >= 0; i--) {
    const bar = barArray[i];
    if (zigZagState.lastType === 'low') {
      if (bar.high > zigZagState.tempExtreme!.price.high) {
        zigZagState.tempExtreme = { index: i, price: bar };
      }
      if (zigZagState.tempExtreme!.price.high - zigZagState.lastPoint.price.low >= deviation) {
        break;
      }
    } else if (zigZagState.lastType === 'high') {
      if (bar.low < zigZagState.tempExtreme!.price.low) {
        zigZagState.tempExtreme = { index: i, price: bar };
      }
      if (zigZagState.lastPoint.price.high - zigZagState.tempExtreme!.price.low >= deviation) {
        break;
      }
    }
  }
}

性能说明 #

这种增量方式的时间复杂度是O(k)，其中k是回溯的ZigZag点数量。由于ZigZag点的数量远小于K线数组的长度，性能远优于全量遍历的O(n)。只有当被移除的K线是ZigZag点时，才会触发局部的重新遍历，但这种场景出现的频率较低，对整体性能影响极小。

内容的提问来源于stack exchange，提问作者Dan B.N.