f# - 如何在 F# 中优化此移动平均线计算

Question

我的移动平均线具有以下特点:

• 每个条目都有一个时间戳，这些值在时间上分布不均匀，并且队列长度可能会有很大差异。
• 我没有固定的期限，因此代码必须灵活，因为会请求多个期限。
• 使用的时间段是时间戳，仅使用高于该时间戳的记录。

这是代码:

module PriceMovingAverage =

    // queue duration
    let queueDuration = TimeSpan.FromHours(1.)

    // moving average queue
    let private timestampQueue = Queue<DateTime>()
    let private priceQueue     = Queue<float>()

    // update moving average
    let updateMovingAverage (tradeData: TradeData) =

        // add the new price
        timestampQueue.Enqueue(tradeData.Timestamp)
        priceQueue.Enqueue(float tradeData.Price)

        // remove the items older than the price base period
        let rec dequeueLoop () =
            if timestampQueue.Peek() + queueDuration < tradeData.Timestamp then
                timestampQueue.Dequeue() |> ignore
                priceQueue.Dequeue() |> ignore
                dequeueLoop()

        dequeueLoop()


    // get the moving average
    let getPrice fromTimestamp =

        // count how many records to skip
        let recordsToSkip =
            timestampQueue
            |> Seq.takeWhile (fun t -> t < fromTimestamp)
            |> Seq.length

        // calculate the average of the prices within the time range
        try
            Some (
                priceQueue
                |> Seq.skip recordsToSkip
                |> Seq.average
                |> decimal
            )
        with _ ->
            None

问题是最后一部分:我正在遍历时间戳队列以查找需要跳过的记录数。然后我将查看价格记录来计算平均值。

大量的CPU时间花费在第一部分:

let recordsToSkip =
        timestampQueue
        |> Seq.takeWhile (fun t -> t < fromTimestamp)
        |> Seq.length

遍历序列然后计算长度的速度很慢。

理想情况下，我只使用带有循环缓冲区的数组，但问题是队列的长度可能会根据数据而显着变化，因为索引实际上是时间戳而不是队列中的位置。

我可以把它变成一个列表而不是序列，也许会获得一些速度，但这意味着每次都要复制整个列表。我认为有两个队列来求平均值会更快，但也许这不是真的。

有人知道如何在保持灵活性的同时加快速度(称为 5-10x/秒)吗？

---

编辑:

合并两个队列会产生以下结果:

   let getPrice fromTimestamp =
        try
            Some (
                priceQueue
                |> Seq.toList
                |> List.skipWhile (fun t -> t.Timestamp < fromTimestamp)
                |> List.averageBy (fun t -> t.Price)
                |> decimal
            )
        with _ ->
            None

速度更快，但仍然非常慢。

---

编辑:

• 我在这里制作了一个 Jupyter 笔记本:https://pastebin.com/E3uS6j7T
• 如果您愿意，我还直接在此处粘贴了测试代码:https://pastebin.com/fK18Wyui

Answer 1

一方面，它就像 Asti says in his answer 。另一方面，如果您绝对必须将数据保存在两个单独的队列中，则可以使用 Seq.zip 一次枚举它们:

timestampQueue.Enqueue <| DateTime.Parse("2020-10-08T17:30"); priceQueue.Enqueue 100.
timestampQueue.Enqueue <| DateTime.Parse("2020-10-08T18:00"); priceQueue.Enqueue 110.
timestampQueue.Enqueue <| DateTime.Parse("2020-10-08T18:30"); priceQueue.Enqueue 120.
timestampQueue.Enqueue <| DateTime.Parse("2020-10-08T19:00"); priceQueue.Enqueue 130.

Seq.zip timestampQueue priceQueue
|> Seq.filter (fun (t, _) -> t >= DateTime.Parse("2020-10-08T18:00"))
|> Seq.averageBy snd
(* val it : float = 120.0 *)