Calculer une moyenne mobile en F #
-
08-07-2019 - |
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?)
La solution
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:
comme il est pratique d'avoir dans sa poche arrière pour de telles choses.
Autres conseils
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.
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; ...]
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
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, ...]
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 )