递归F#函数处理序列数据时Array与List的选型疑问

你担心拆分数组头尾会重复重建数组的顾虑完全正确，这种场景下不要用拆分数组的方式实现递归，应该保留完整数组、用索引遍历实现递归，完全可以避免多余的数组重建开销，同时还能省去原始Array转List的O(n)转换成本。

另外你原来的List实现还有一个隐性性能问题：每次用output @ [stateTracker']拼接列表，每次拼接的时间复杂度和当前output长度成正比，整体计算时间会达到O(n²)，数据量大的时候性能退化非常明显，改成数组实现的时候可以一并优化。

改写后的Array版本实现参考：

let calculate (candles: CandleData array) : decimal array =
    if candles.Length = 0 then [||]
    else
        let inline range (q: CandleData) = q.High - q.Low
        let inline price (q: CandleData) = range q / 2m + q.Low

        let firstPrice = price candles[0]
        // 预分配和输入等长的容量，避免后续扩容开销
        let output = ResizeArray<decimal>(candles.Length)
        // 索引递归实现，全程不修改/复制原始数组
        let rec update (index: int) lastPrice priceTracker rangeTracker stateTracker lambda =
            if index >= candles.Length then output.ToArray()
            else
                let h = candles[index]
                let currentPrice = price h
                let priceTracker' = 0.2m * (currentPrice - lastPrice) + 0.8m * priceTracker
                let rangeTracker' = 0.1m * (range h) + 0.8m * rangeTracker
                let lambda = if rangeTracker <> 0m then abs(priceTracker / rangeTracker) else lambda
                let sqr = decimal (sqrt (double (lambda * lambda * lambda * lambda + 16m * lambda * lambda)))
                let alpha = (-lambda * lambda + sqr) / 8m
                let stateTracker' = alpha * currentPrice + (1m - alpha) * stateTracker
                output.Add(stateTracker')
                update (index + 1) currentPrice priceTracker' rangeTracker' stateTracker' lambda

        update 0 firstPrice 0m (range candles[0]) firstPrice 0.01m

该实现的核心优势：

• 全程操作原始输入数组，仅传递当前遍历索引，没有任何额外的数组/列表拆分、复制开销
• 输出用预分配了容量的ResizeArray累积结果，添加操作均摊O(1)，整体时间复杂度为严格O(n)
• 补充了空输入的边界处理，避免原代码访问空集合Head的异常
• 如果需要返回list类型，最后把output.ToArray()改成output |> List.ofSeq即可，比原实现的列表拼接性能高很多

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