title: How to optimize this moving average calculation, in F#
body: <p>I have a moving average that has the following particularities:</p>
  <ul>
  <li>Each entry has a timestamp, the values are not evenly distributed in time and the queue length can vary significantly.</li>
  <li>I do not have a fixed period, so the code must be flexible as several periods will be requested.</li>
  <li>The period used is a timestamp and only records above that timestamp are to be used.</li>
  </ul>
  <p>This is the code:</p>
  <pre><code>module PriceMovingAverage =
  
      // queue duration
      let queueDuration = TimeSpan.FromHours(1.)
  
      // moving average queue
      let private timestampQueue = Queue&lt;DateTime&gt;()
      let private priceQueue     = Queue&lt;float&gt;()
  
      // 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 &lt; tradeData.Timestamp then
                  timestampQueue.Dequeue() |&gt; ignore
                  priceQueue.Dequeue() |&gt; ignore
                  dequeueLoop()
  
          dequeueLoop()
  
  
      // get the moving average
      let getPrice fromTimestamp =
  
          // count how many records to skip
          let recordsToSkip =
              timestampQueue
              |&gt; Seq.takeWhile (fun t -&gt; t &lt; fromTimestamp)
              |&gt; Seq.length
  
          // calculate the average of the prices within the time range
          try
              Some (
                  priceQueue
                  |&gt; Seq.skip recordsToSkip
                  |&gt; Seq.average
                  |&gt; decimal
              )
          with _ -&gt;
              None
  </code></pre>
  <p>The issue is the last part:
  I'm iterating through the timestamp queue to find how many records I need to skip. Then I'm going through the price records to calculate the average.</p>
  <p>A lot of the CPU time is spent on the first part:</p>
  <pre><code>let recordsToSkip =
          timestampQueue
          |&gt; Seq.takeWhile (fun t -&gt; t &lt; fromTimestamp)
          |&gt; Seq.length
  </code></pre>
  <p>going through the sequence and then calculating the length is slow.</p>
  <p>Ideally, I'd just use an array with a circular buffer, but the problem is that the length of the queue can vary significantly based on the data as the index is really the timestamp and not the position in the queue.</p>
  <p>I could turn this into a list instead of a sequence and maybe gain some speed, but that means copying the whole list each time.
  I assumed it would be faster to have two queues in order to do the average, but maybe this is not true.</p>
  <p>Does anyone have an idea how to make this fast (it's called 5-10x / sec) while keeping the flexibility?</p>
  <hr />
  <p>Edit:</p>
  <p>Merging the two queues yields this:</p>
  <pre><code>   let getPrice fromTimestamp =
          try
              Some (
                  priceQueue
                  |&gt; Seq.toList
                  |&gt; List.skipWhile (fun t -&gt; t.Timestamp &lt; fromTimestamp)
                  |&gt; List.averageBy (fun t -&gt; t.Price)
                  |&gt; decimal
              )
          with _ -&gt;
              None
  </code></pre>
  <p>It's faster, but it's still super slow.</p>
  <hr />
  <p>Edit:</p>
  <ul>
  <li>I made a Jupyter notebook here: <a href="https://pastebin.com/E3uS6j7T" rel="nofollow noreferrer">https://pastebin.com/E3uS6j7T</a></li>
  <li>If you prefer, I also pasted test code directly here: <a href="https://pastebin.com/fK18Wyui" rel="nofollow noreferrer">https://pastebin.com/fK18Wyui</a></li>
  </ul>