Calcolo di una media mobile in F #

Question

Sto ancora lavorando per risolvere il problema di F #, cercando di capire come "pensare" in F # piuttosto che semplicemente tradurre da altre lingue che conosco.

Di recente ho pensato ai casi in cui non hai una mappa 1: 1 tra prima e dopo. Casi in cui List.map cade.

Un esempio di ciò sono le medie mobili, in cui in genere si ottengono risultati len-n + 1 per un elenco di lunghezze len quando si fa la media su n articoli.

Per i guru là fuori, è un buon modo per farlo (usando la coda pizzicata da Jomo Fisher )?

//Immutable queue, with added Length member
type Fifo<'a> =
    new()={xs=[];rxs=[]}
    new(xs,rxs)={xs=xs;rxs=rxs}

    val xs: 'a list;
    val rxs: 'a list;

    static member Empty() = new Fifo<'a>()
    member q.IsEmpty = (q.xs = []) && (q.rxs = [])
    member q.Enqueue(x) = Fifo(q.xs,x::q.rxs)
    member q.Length() = (List.length q.xs) + (List.length q.rxs)
    member q.Take() =
        if q.IsEmpty then failwith "fifo.Take: empty queue"
        else match q.xs with
                | [] -> (Fifo(List.rev q.rxs,[])).Take()
                | y::ys -> (Fifo(ys, q.rxs)),y

//List module, add function to split one list into two parts (not safe if n > lst length)
module List =
    let splitat n lst =
        let rec loop acc n lst =
            if List.length acc = n then
                (List.rev acc, lst)
            else
                loop (List.hd lst :: acc) n (List.tl lst)
        loop [] n lst

//Return list with moving average accross len elements of lst
let MovingAverage (len:int) (lst:float list) = 
    //ugly mean - including this in Fifo kills genericity
    let qMean (q:Fifo<float>) = ((List.sum q.xs) + (List.sum q.rxs))/(float (q.Length()))

    //get first part of list to initialise queue
    let (init, rest) = List.splitat len lst

    //initialise queue with first n items
    let q = new Fifo<float>([], init)

    //loop through input list, use fifo to push/pull values as they come
    let rec loop (acc:float list) ls (q:Fifo<float>) =
        match ls with
        | [] -> List.rev acc
        | h::t -> 
            let nq = q.Enqueue(h) //enqueue new value
            let (nq, _) = nq.Take() //drop old value
            loop ((qMean nq)::acc) t nq //tail recursion

    loop [qMean q] rest q

//Example usage    
MovingAverage 3 [1.;1.;1.;1.;1.;2.;2.;2.;2.;2.]

(Forse un modo migliore sarebbe implementare MovingAverageQueue ereditando da Fifo?)

Answer 1

Se non ti importa troppo delle prestazioni, ecco una soluzione molto semplice:

#light

let MovingAverage n s =
   Seq.windowed n s
   |> Seq.map Array.average

let avgs = MovingAverage 5000 (Seq.map float [|1..999999|])

for avg in avgs do
    printfn "%f" avg
    System.Console.ReadKey() |> ignore

Questo ricalcola la media di ogni 'finestra' da zero, quindi è scadente se le finestre sono grandi.

In ogni caso, controlla Seq.windowed:

http: // research.microsoft.com/projects/cambridge/fsharp/manual/FSharp.Core/Microsoft.FSharp.Collections.Seq.html

come è utile avere nella tasca posteriore per tali cose.

Answer 2

Se ti preoccupi delle prestazioni, puoi calcolare una media mobile in modo efficiente usando qualcosa del genere (supponendo che stiamo calcolando una media mobile su una finestra di 3 giorni)

Numbers[n]    Running Total[n]
---------     ---------------
n[0] = 7       7 = Numbers[0]
n[1] = 1       8 = RunningTotal[1-1] + Numbers[1]
n[2] = 2      10 = RunningTotal[2-1] + Numbers[2]
n[3] = 8      11 = RunningTotal[3-1] + Numbers[3] - Numbers[3-3]
n[4] = 4      14 = RunningTotal[4-1] + Numbers[4] - Numbers[4-3]
n[5] = 1      13 = RunningTotal[5-1] + Numbers[5] - Numbers[5-3] 
n[6] = 9      14 = RunningTotal[6-1] + Numbers[6] - Numbers[6-3]
...
N             RunningTotal[N] = RunningTotal[N-1] + Numbers[N] - Numbers[N-3]

La parte difficile di questo è trattenere il totale corrente precedente e il numero _N-window . Ho trovato il seguente codice:

let movingAverage days l =
    seq {
        let queue = new Queue<_>(days : int)
        let divisor = decimal days

        let total = ref 0m
        for cur in l do
            queue.Enqueue(cur)
            total := !total + cur
            if queue.Count < days then
                yield (cur, 0m)
            else
                yield (cur, !total / divisor)
                total := !total - (queue.Dequeue())
    }

Questa versione non è così bella come il codice Haskell, ma dovrebbe evitare problemi di prestazioni associati al ricalcolo della "finestra" " ad ogni corsa. Mantiene un totale parziale e contiene i numeri utilizzati in precedenza in una coda, quindi dovrebbe essere molto veloce.

Solo per divertimento, ho scritto un semplice benchmark:

#light
open System
open System.Collections.Generic
open System.Diagnostics;

let windowAverage days (l : #seq<decimal>) = Seq.windowed days l |> Seq.map (Seq.average)

let princessAverage days l =
    seq {
        let queue = new Queue<_>(days : int)
        let divisor = decimal days

        let total = ref 0m
        for cur in l do
            queue.Enqueue(cur)
            total := !total + cur
            if queue.Count < days then
                yield (cur, 0m)
            else
                yield (cur, !total / divisor)
                total := !total - (queue.Dequeue())
    }

let testData =
    let rnd = new System.Random()
    seq { for a in 1 .. 1000000 -> decimal (rnd.Next(1000)) }

let benchmark msg f iterations =
    let rec loop = function
        | 0 -> ()
        | n -> f 3 testData |> ignore; loop (n - 1)

    let stopWatch = Stopwatch.StartNew()
    loop iterations
    stopWatch.Stop()
    printfn "%s: %f" msg stopWatch.Elapsed.TotalMilliseconds

let _ =
    let iterations = 10000000
    benchmark "princessAverage" princessAverage iterations
    benchmark "windowAverage" windowAverage iterations
    printfn "Done"

Risultati:

princessAverage: 1670.791800
windowAverage: 2986.146900

La mia versione è ~ 1.79x più veloce.

Answer 3

Ecco una versione (corretta, spero) F # della soluzione Haskell proposta qui .

EDIT: ora ricorsivo della coda, non più veloce, ma non esplode con n = 50000. (vedi cronologia delle modifiche per la versione non ricorsiva della coda)

let LimitedAverage n ls = 
    let rec loop acc i n ls = 
        match i with
        | 0 -> acc //i counts down from n to 0, when we hit 0 we stop
        | _ -> match ls with
               | [] -> acc //if we hit empty list before end of n, we stop too
               | x::xs -> (loop (acc + (x / float n)) (i - 1) n xs) //divide this value by n, perform average on 'rest' of list
    loop 0. n n ls

LimitedAverage 50000 (List.map float [1..9999999])
//>val it : float = 25000.5

let rec MovingAverage3 n ls = 
    let rec acc loop i n ls = 
        match i with 
        | 0 -> List.rev acc //i counts down from n to 0, when we hit 0 we stop
        | _ -> match ls with
                | [] -> List.rev acc //if we hit empty list before end of n, we stop too
                | x::xs -> loop (LimitedAverage2 n ls :: acc) (i - 1) n xs // limited average on whole list, then moving average on tail
    loop [] (n + 1) n ls 

MovingAverage3 50000 (List.map float [1..9999999])
//>val it : float list = [25000.5; 25001.5; 25002.5; ...]

Answer 4

Se ti interessano le prestazioni e ti piace il codice elegante, prova

module MovingAverage = 
    let selfZip n l =
        Seq.skip n l |> Seq.zip l 

    let runTotal i z =
        Seq.scan ( fun sum (s, e) -> sum - s + e ) i z

    let average n l:seq<'a> =
        Seq.skip n l
        |> selfZip n
        |> runTotal (l |> Seq.take n |> Seq.sum)
        |> Seq.map ( fun sum -> decimal sum / decimal n ) 

 let ma = MovingAverage.average 2 myseq

Usando FSUnit possiamo provarlo

 let myseq = seq { for i in 0..10 do yield i }

 Seq.nth 0 ma |> should equal 0.5
    Seq.nth 1 ma |> should equal 1.5
    Seq.nth 2 ma |> should equal 2.5
    Seq.nth 3 ma |> should equal 3.5

Il trucco dell'algoritmo è la prima somma dei primi n numeri e quindi mantenere un totale parziale aggiungendo la testa della finestra e sottraendo la coda della finestra. La finestra scorrevole è ottenuto facendo un auto zip sulla sequenza ma con il secondo argomento da comprimere avanzato in base alla dimensione della finestra.

Alla fine della pipeline dividiamo semplicemente il totale parziale per la finestra taglia.

La scansione delle note è proprio come piega ma restituisce ciascuna versione dello stato una sequenza.

Una soluzione ancora più elegante, sebbene possibile con hit di performance è per fare l'osservazione che se azzeriamo la sequenza non abbiamo bisogno per calcolare la somma iniziale.

namespace Utils

module MovingAverage = 
    let selfZip n l =
        Seq.skip n l |> Seq.zip l 

    let rec zeros = 
        seq { yield 0.0; yield! zeros} 

    // Create a running total given
    let runTotal z =
        Seq.scan (fun sum (s,e) -> sum - s + e ) 0.0 z

    let average n l =
        Seq.concat [(Seq.take n zeros); l]
        |> selfZip n
        |> runTotal
        |> Seq.map ( fun sum -> sum / float n ) 
        |> Seq.skip n

Potrebbe esserci un impatto sulle prestazioni a causa della seconda indiretta correlata a avvolgimento delle due sequenze ma forse non è significativo a seconda sulla dimensione della finestra

Answer 5

Questa è la mia versione.

let sma list n =
    let len = List.length list
    let rec loop acc sum cnt =
        if cnt >= len then List.rev acc
        else if cnt < n-1 then loop (0.0::acc) (sum + List.nth list cnt) (cnt+1)
        else loop (((sum + List.nth list cnt)/(float n))::acc) (sum + (List.nth list cnt) - (List.nth list (cnt-n+1))) (cnt+1)
    loop [] 0.0 0

Esempio:

sma (List.map float [5..50]) 5
[0, 0, 0, 0, 7, 8, 9, ...]

Answer 6

Per quanto posso vedere, il tuo codice è pieno di let . Non ho familiarità con F # ma ho fatto un po 'di Haskell. Il paradigma funzionale significa non pensare a "come" ma su " cosa " ;: pensi Fifo, ma in realtà dovresti semplicemente specificare la semantica della media mobile.

-- the limited average of a list
limitedaverage 0 _ = 0
limited verage n (x:xs) = (x/n) + ( limited average (n-1) xs )

-- a list, transformed into a sequence of moving averages of 
movingaverages n [] = []
movingaverages n (x:xs) = ( movingaverage n (x:xs) : movingaverages n xs )