如何将逐笔实时数据转多周期K线？优化代码至O(N)时间复杂度

我写了一段代码，用来把1分钟级别的实时K线数据转换为5分钟、10分钟、15分钟及30分钟周期的K线，但这段代码的时间复杂度是O(N*M)，处理实时数据时速度偏慢，想知道能不能优化到O(N)时间复杂度。

原代码 #

const arbitaryMinCandles = new Map();
["ITC_EQ"].forEach(instrument => {
    arbitaryMinCandles.set(instrument, []); 
});

for(const [symbol,ticks] of oneMinCandle.entries()){

    let stack = [ticks[0]];
    let high = -Infinity 
    let low = Infinity
    let open = 0;
    let close = 0;
    for(let i = 0; i < ticks.length; i++){
        if(ticks[i].timestamp - stack[0].timestamp <= 300){
            high = Math.max(high, ticks[i].high);
            low = Math.min(low, ticks[i].low);
        }

        if(ticks[i].timestamp - stack[0].timestamp === 500){
            let temp = stack.pop();
            open = temp.open;
            close = ticks[i].close;
            stack.push(ticks[i + 1]);
            arbitaryMinCandles.get(symbol).push({open, high, low, close, isComplete: true})
            high = -Infinity;
            low = Infinity;
            open = 0;
            close = 0;
        }
    }

}
console.log(arbitaryMinCandles);

输入示例 #

const oneMinCandle = new Map([
  [
    'ITC_EQ',
    [
      {
        open: 424.10,
        high: 424.60,
        low: 422.50,
        close: 422.95,
        timestamp: 1683712800 
        // 9:15
      },
      {
        // 9:16
        open: 422.95,
        high: 424.45,
        low: 422.95,
        close: 424.45,
        timestamp: 1683712860
      },
      {
        // 9:17
        open: 424.30,
        high: 425.00,
        low: 424.15,
        close: 424.40,
        timestamp: 1683712920 
      },
      {
        // 9:18
        open: 424.40,
        high: 425.00,
        low: 424.15,
        close: 424.95,
        timestamp: 1683712980 
      },
      {
        // 9:19
        open: 424.95,
        high: 425.65,
        low: 424.80,
        close: 425.25,
        timestamp: 1683713040
      },
      {
        // 9:20
        open: 425.20,
        high: 425.75,
        low: 425.10,
        close: 425.45,
        timestamp: 1683713100 
      },
        {
            // 9:21
        open: 425.60,
        high: 425.60,
        low: 424.55,
        close: 425.25,
        timestamp: 1683713160 
      },
         {
            // 9:22
        open: 425.35,
        high: 425.80,
        low: 425.20,
        close: 425.60,
        timestamp: 1683713160 
      },
         {
            // 9:23
        open: 425.60,
        high: 426.00,
        low: 425.60,
        close: 426.00,
        timestamp: 1683713280 
      },
        {
            // 9:24
        open: 425.90,
        high: 426.00,
        low: 425.70,
        close: 425.70,
        timestamp: 1683713340 
      },
       {
        // 9:25
        open: 425.70,
        high: 425.70,
        low: 425.20,
        close: 425.50,
        timestamp: 1683713400 
      },
       {
        // 9:26
        open: 425.45,
        high: 425.45,
        low: 425.00,
        close: 425.25,
        timestamp: 1683713460 
      },
       {
        // 9:27
        open: 425.20,
        high: 425.40,
        low: 425.20,
        close: 425.25,
        timestamp: 1683713520 
      },
       {
        // 9:28
        open: 425.25,
        high: 425.75,
        low: 425.20,
        close: 425.70,
        timestamp: 1683713580 
      },
       {
        // 9:29
        open: 425.70,
        high: 425.90,
        low: 425.60,
        close: 425.70,
        timestamp: 1683713640 
      },
       {
        // 9:30
        open: 425.80,
        high: 425.80,
        low: 425.50,
        close: 425.65,
        timestamp: 1683713700 
      },
       {
        // 9:31
        open: 425.60,
        high: 425.85,
        low: 425.60,
        close: 425.80,
        timestamp: 1683713760 
      },
       {
        // 9:32
        open: 425.60,
        high: 425.75,
        low: 425.25,
        close: 425.25,
        timestamp: 1683713820 
      },
       {
        // 9:33
        open: 425.10,
        high: 425.65,
        low: 425.10,
        close: 425.45,
        timestamp: 1683713880 
      },
       {
        // 9:34
        open: 425.50,
        high: 426.10,
        low: 425.50,
        close: 425.55,
        timestamp: 1683713940 
      },
       {
        // 9:35
        open: 425.75,
        high: 425.95,
        low: 425.70,
        close: 425.70,
        timestamp: 1683714000 
      },
       {
        // 9:36
        open: 425.70,
        high: 425.85,
        low: 425.20,
        close: 425.20,
        timestamp: 1683714060 
      },
    ]
  ],
]);

5分钟周期输出示例 #

Map(1) {
  'ITC_EQ' => [
    {
      open: 424.1,
      high: 425.65,
      low: 422.5,
      close: 425.25,
      isComplete: true
    },
    {
      open: 425.2,
      high: 426,
      low: 424.55,
      close: 425.7,
      isComplete: true
    },
    {
      open: 425.7,
      high: 425.9,
      low: 425,
      close: 425.7,
      isComplete: true
    },
    {
      open: 425.8,
      high: 426.1,
      low: 425.1,
      close: 425.55,
      isComplete: true
    }
  ]
}

可以优化至O(N)时间复杂度 #

原代码存在逻辑错误（如错误判断时间差为500秒）且冗余，导致时间复杂度偏高。优化核心是利用输入数据的时间有序性，一次遍历完成所有周期的K线构建，每个tick仅被处理一次，时间复杂度等价于O(N)。

优化后的代码 #

// 定义需要转换的周期（单位：秒）
const periods = [300, 600, 900, 1800]; // 5、10、15、30分钟
// 存储所有周期的转换结果
const multiPeriodCandles = new Map();

// 初始化每个标的的各周期K线数组
["ITC_EQ"].forEach(instrument => {
    multiPeriodCandles.set(instrument, {});
    periods.forEach(period => {
        multiPeriodCandles.get(instrument)[period] = [];
    });
});

for (const [symbol, ticks] of oneMinCandle.entries()) {
    if (!ticks.length) continue;

    // 为每个周期维护当前正在构建的K线
    const currentCandles = {};
    periods.forEach(period => {
        // 计算第一个tick所属的周期起始时间
        const firstPeriodStart = Math.floor(ticks[0].timestamp / period) * period;
        currentCandles[period] = {
            open: ticks[0].open,
            high: ticks[0].high,
            low: ticks[0].low,
            close: ticks[0].close,
            periodStart: firstPeriodStart,
            isComplete: false
        };
    });

    for (const tick of ticks) {
        for (const period of periods) {
            const candle = currentCandles[period];
            const tickPeriodStart = Math.floor(tick.timestamp / period) * period;

            if (tickPeriodStart !== candle.periodStart) {
                // 当前tick属于新周期，先把上一个周期的K线标记为完成并存入
                candle.isComplete = true;
                multiPeriodCandles.get(symbol)[period].push({...candle});
                // 初始化新周期的K线
                currentCandles[period] = {
                    open: tick.open,
                    high: tick.high,
                    low: tick.low,
                    close: tick.close,
                    periodStart: tickPeriodStart,
                    isComplete: false
                };
            } else {
                // 更新当前周期的K线数据
                candle.high = Math.max(candle.high, tick.high);
                candle.low = Math.min(candle.low, tick.low);
                candle.close = tick.close;
            }
        }
    }

    // 处理每个周期最后一个未完成的K线（可根据需求决定是否标记为完成）
    periods.forEach(period => {
        const candle = currentCandles[period];
        if (!candle.isComplete) {
            multiPeriodCandles.get(symbol)[period].push({...candle});
        }
    });
}

// 以5分钟周期为例输出结果
console.log("5分钟K线结果：", multiPeriodCandles.get("ITC_EQ")[300]);

优化说明 #

1. 时间复杂度：每个tick仅遍历一次，周期处理为固定常数级操作，整体时间复杂度为O(N)。
2. 逻辑正确性：通过Math.floor(tick.timestamp / period) * period计算周期起始时间，确保tick被分配到正确的时间窗口，避免原代码的时间差判断错误。
3. 扩展性：支持同时生成多个周期的K线，无需重复遍历数据。
4. 实时适配：实时流场景下，只需维护各周期的currentCandles状态，新tick到来时直接更新对应周期的K线，无需重新遍历历史数据。

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