Calculer une moyenne mobile en F #

Question

Je travaille toujours sur le thème F # pour tenter de comprendre comment "penser" en fa # plutôt que de traduire à partir d'autres langues que je connais.

J'ai récemment pensé aux cas où vous n'avez pas de carte 1: 1 entre avant et après. Cas où List.map tombe en panne.

Un exemple de ceci est les moyennes mobiles, où vous aurez généralement des résultats len-n + 1 pour une liste de longueur len lors de la moyenne de n éléments.

Pour les gourous, est-ce un bon moyen de le faire (en utilisant la file d'attente pincée dans 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.]

(Peut-être qu'un meilleur moyen serait de mettre en œuvre une MovingAverageQueue en héritant de Fifo?)

Answer 1

Si les performances ne vous intéressent pas trop, voici une solution très simple:

#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

Ceci recalcule la moyenne de chaque "fenêtre" à partir de zéro. Il est donc médiocre si les fenêtres sont grandes.

Dans tous les cas, consultez Seq.windowed:

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

comme il est pratique d'avoir dans sa poche arrière pour de telles choses.

Answer 2

Si vous tenez compte des performances, vous pouvez calculer efficacement une moyenne mobile en utilisant quelque chose comme ceci (en supposant que nous calculons une moyenne mobile sur une fenêtre de 3 jours)

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 difficulté réside dans le maintien de votre précédent total et de votre numéro _N-window . Je suis venu avec le code suivant:

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())
    }

Cette version n’est pas aussi jolie que le code Haskell, mais elle devrait éviter les problèmes de performances associés au recalcul de votre & window; fenêtre " à chaque course. Il conserve un total cumulé et contient les numéros précédemment utilisés dans une file d'attente. Il devrait donc être très rapide.

Juste pour le plaisir, j’ai écrit un repère simple:

#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"

Résultats:

princessAverage: 1670.791800
windowAverage: 2986.146900

Ma version est environ 1,79 fois plus rapide.

Answer 3

Voici une version F # (corrigée, j'espère) de la solution proposée par Haskell ici .

EDIT: Maintenant, queue-récursive, pas plus rapide, mais n’explose pas avec n = 50000. (voir l'historique d'édition pour la version non-queue-récursive)

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

Si vous vous souciez de la performance et aimez le code élégant, essayez

.

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

En utilisant FSUnit, nous pouvons le tester

 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

Le truc de l’algorithme est la première somme des n premiers nombres et puis maintenez un total cumulé en ajoutant la tête de la fenêtre et soustraire la queue de la fenêtre. La fenêtre coulissante est réalisé en faisant un auto-zip sur la séquence mais avec le second argument à zip avancé par la taille de la fenêtre.

À la fin du pipeline, il suffit de diviser le total cumulé par la fenêtre Taille.

Remarque: le scan est comme pli, mais donne chaque version de l’état en une séquence.

Une solution encore plus élégante, si possible avec succès, est pour faire l'observation que si nous zéro pad la séquence nous n'avons pas besoin calculer la somme initiale.

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

Il pourrait y avoir un impact négatif sur les performances en raison de la deuxième indirection liée au l’enveloppement des deux séquences mais peut-être que cela n’est pas significatif selon sur la taille de la fenêtre

Answer 5

Ceci est ma version.

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

Exemple:

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

Answer 6

Autant que je sache, votre code est rempli d'instructions let . Je ne suis pas familier avec F # mais j'ai fait du Haskell. Le paradigme fonctionnel signifie ne pas penser au "comment". mais à propos de "quoi": vous pensez Fifo, mais vous devriez en fait simplement spécifier la sémantique de la moyenne 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 )