CODEWITHSUNDEEP
arrayslistoptimizationf#
Thomas
Thomas

Reputation: 12107

Array vs List in recursive F# function

I have this function:

let calculate (candles: CandleData list) : decimal list =
    let inline range (q: CandleData) = q.High - q.Low
    let inline price (q: CandleData) = range q / 2m + q.Low

    let rec update (candles: CandleData list) (output: decimal list) lastPrice priceTracker rangeTracker stateTracker lambda =
        match candles with
        | [] -> output
        | h::t ->
            let priceTracker' = 0.2m * (price h - 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 * price h + (1m - alpha) * stateTracker
            update t (output @ [decimal stateTracker']) (price h) priceTracker' rangeTracker' stateTracker' lambda

    update candles [] (price candles.Head) 0m (range candles.Head) (price candles.Head) 0.01m

It operates on lists, but I was wondering if it wouldn't make sense to use an array instead since the data originally comes as an array so I have to convert it to a list to then walk through it sequentially, like an array.

But if I convert it to an array, wouldn't the head / tail part recreate the array every time? so then should I keep the array whole and just iterate with the index?

Upvotes: 1

Views: 89

Answers (2)

AMieres
AMieres

Reputation: 5004

An alternative is to use mapFold:

let calculate3 (candles : _[]) =
    let inline range (q: CandleData) = q.High - q.Low
    let inline price (q: CandleData) = range q / 2m + q.Low

    let init = price candles.[0], 0m, range candles.[0], price candles.[0], 0.01m
    (init, candles)
    ||> Array.mapFold (fun (lastPrice, priceTracker, rangeTracker, stateTracker, lambda) candle ->
            let priceTracker' = 0.2m * (price candle - lastPrice) + 0.8m * priceTracker
            let rangeTracker' = 0.1m * (range candle) + 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 * price candle + (1m - alpha) * stateTracker
            stateTracker, (price candle, priceTracker', rangeTracker', stateTracker', lambda) )
    |> fst

It works similar to scan but produces an Array simultaneously.

Upvotes: 1

Brian Berns
Brian Berns

Reputation: 17038

If you want to avoid the cost of converting to list and still keep this as idiomatic F#, you can scan the original array instead of recursing:

let calculate (candles : _[]) =
    let inline range (q: CandleData) = q.High - q.Low
    let inline price (q: CandleData) = range q / 2m + q.Low

    let init = price candles.[0], 0m, range candles.[0], price candles.[0], 0.01m
    (init, candles)
        ||> Seq.scan (fun (lastPrice, priceTracker, rangeTracker, stateTracker, lambda) candle ->
            let priceTracker' = 0.2m * (price candle - lastPrice) + 0.8m * priceTracker
            let rangeTracker' = 0.1m * (range candle) + 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 * price candle + (1m - alpha) * stateTracker
            price candle, priceTracker', rangeTracker', stateTracker', lambda)
        |> Seq.map (fun (lastPrice, priceTracker, rangeTracker, stateTracker, lambda) ->
            stateTracker)
        |> Seq.skip 1
        |> Seq.toArray

Upvotes: 0

Related Questions