Can I do two sums in parallel with collection functions, in F#, or generally, optimize the whole thing

user_695498 0
Viewed 64

I have the following code:

// volume queue
let volumeQueue = Queue<float>()
let queueSize = 10 * 500 // 10 events per second, 500 seconds max

// add a signed volume to the queue
let addToVolumeQueue x =
    volumeQueue.Enqueue(x)
    while volumeQueue.Count > queueSize do volumeQueue.TryDequeue() |> ignore

// calculate the direction of the queue, normalized between +1 (buy) and -1 (sell)
let queueDirection length =
    let subQueue =
        volumeQueue
        |> Seq.skip  (queueSize - length)

    let boughtVolume =
        subQueue
        |> Seq.filter (fun l -> l > 0.)
        |> Seq.sum

    let totalVolume =
        subQueue
        |> Seq.sumBy (fun l -> abs l)

    2. * boughtVolume / totalVolume - 1.

What this does is run a fixed length queue to which transaction volumes are added, some positive, some negative.

And then it calculates the cumulative ratio of positive over negative entries and normalizes it between +1 and -1, with 0 meaning the sums are half / half.

There is no optimization right now but this code's performance will matter. So I'd like to make it fast, without compromising readability (it's called roughly every 100ms).

The first thing that comes to mind is to do the two sums at once (the positive numbers and all the numbers) in a single loop. It can easily be done in a for loop, but can it be done with collection functions?

The next option I was thinking about is to get rid of the queue and use a circular buffer, but since the code is run on a part of the buffer (the last 'length' items), I'd have to handle the wrap around part; I guess I could extend the buffer to the size of a power of 2 and get automatic wrap around that way.

Any idea is welcome, but my first original question is: can I do the two sums in a single pass with the collection functions? I can't iterate in the queue with an indexer, so I can't use a for loop (or I guess I'd have to instance an iterator)

f# collections performance
1 Answers

First of all, there is nothing inherently wrong with using mutable variables and loops in F#. Especially at a small scale (e.g. inside a function), this can often be quite readable - or at least, easy to understand if there is a suitable comment.

To do this using a single iteration, you could use fold. This basically calculates the two sums in a single iteration at the cost of some readability:

let queueDirectionFold length =
  let boughtVolume, totalVolume =
      volumeQueue
      |> Seq.skip  (queueSize - length)
      |> Seq.fold (fun (bv, tv) v ->
        (if v > 0.0 then bv else bv + v), tv + abs v) (0.0, 0.0)   
  2. * boughtVolume / totalVolume - 1.

As I mentioned earlier, I would also consider using a loop. The loop itself is quite simple, but some complexity is added by the fact that you need to skip some elements. Still, I think it's quite clear:

let queueDirectionLoop length =
  let mutable i = 0 
  let mutable boughtVolume = 0.
  let mutable totalVolume = 0.
  for v in volumeQueue do
    if i >= queueSize - length then 
      totalVolume <- totalVolume + abs v
      if v > 0. then boughtVolume <- boughtVolume + v
    i <- i + 1
  2. * boughtVolume / totalVolume - 1.

I tested the performance using 4000 elements and here is what I got:

#time 
let rnd = System.Random()
for i in 0 .. 4000 do volumeQueue.Enqueue(rnd.NextDouble())

for i in 0 .. 10000 do ignore(queueDirection 1000)      // ~900 ms 
for i in 0 .. 10000 do ignore(queueDirectionFold 1000)  // ~460 ms
for i in 0 .. 10000 do ignore(queueDirectionLoop 1000)  // ~370 ms

Iterating over the queue just once definitely helps with performance. Doing this in an imperative loop helps the performance even more - this may be worth it if you care about performance. The code may be a bit less readable than the original, but I think it's not much worse than fold.

Tomas_Petricek_335180
Related