Berechnung eines gleitenden Durchschnitts in F #

Question

Ich arbeite immer noch daran, das F # -ding zu growing - ich versuche herauszufinden, wie man in F # "denkt", anstatt einfach nur aus anderen Sprachen zu übersetzen.

Ich habe kürzlich über die Fälle nachgedacht, in denen Sie keine 1: 1-Karte zwischen vorher und nachher haben. Fälle, in denen List.map abstürzt.

Ein Beispiel dafür sind gleitende Durchschnitte, bei denen in der Regel len-n + 1 Ergebnisse für eine Liste der Länge len erhalten werden, wenn über n Elemente gemittelt wird.

Für die Gurus da draußen, ist dies ein guter Weg, es zu tun (mit Warteschlange aus Jomo Fisher eingeklemmt)?

//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.] 

(Vielleicht ein besserer Weg, um eine MovingAverageQueue durch Erben von Fifo zu implementieren wäre?)

Answer 1

(Versionsgeschichte für Nicht-tail-rekursive Version sehen) Wenn Sie kümmern sich nicht zu viel über die Leistung, hier ist eine sehr einfache Lösung:

#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 

Diese neu berechnet den Durchschnitt von jedem ‚Fenster‘ von Grund auf, so ist es schlecht, wenn die Fenster groß sind.

In jedem Fall Besuche Seq.windowed:

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

wie es praktisch ist für solche Dinge in der Gesäßtasche haben.

Answer 2

Soweit ich sehen kann, Ihr Code ist voll von let Aussagen. Ich bin mit F # nicht vertraut, habe aber Haskell gemacht. Das funktionale Paradigma bedeutet, nicht über "wie" zu denken, sondern über "was": Sie denken Fifo, aber Sie sollten eigentlich nur die Semantik des gleitenden Durchschnitts angeben.

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

Answer 3

Hier ist eine (korrigiert, hoffe ich) F # Version der Haskell Lösung here vorgeschlagen.

EDIT: Jetzt Schwanz-rekursiv, nicht schneller, aber nicht mit explodiert n = 50000.

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

Wenn Sie kümmern uns um die Leistung tun , dann können Sie einen gleitenden Durchschnitt effizient mit so etwas wie dies berechnen (vorausgesetzt, wir einen gleitenden Durchschnitt über einen 3-Tage-Fenster sind die Berechnung)

 
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] 

der Fest Teil davon ist halten Sie Ihre vorherige laufende Summe und Nummer _N-Fenster. Ich kam mit dem folgenden Code auf:

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

Diese Version ist nicht so schön wie der Code Haskell suchen, aber es sollte auf jeden Lauf mit recomputing Ihre „Fenster“ Performance Probleme vermeiden. Es behält eine laufende Summe und hält zuvor verwendete Nummern in einer Warteschlange, so dass es sehr schnell sein sollte.

Just for fun, schrieb ich eine einfache 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" 

Ergebnisse:

princessAverage: 1670.791800 
windowAverage: 2986.146900

Meine Version ist ~ 1.79x schneller.

Answer 5

Wenn Sie über die Leistung und wie elegant Code kümmern versuchen dann

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 

FSUnit Verwendung können wir es testen

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 

Der Trick des Algorithmus ist die erste Summe der ersten n Zahlen und Halten Sie dann eine laufende Summe, indem Sie den Kopf des Fensters hinzufügen und das Ende des Fensters subtrahieren. Das gleitende Fenster ist erreicht, indem Sie eine Selbst-Zip in der Sequenz, aber mit dem zweiten Argument, um durch die Fenstergröße erweitert.

Am Ende der Pipeline teilen wir einfach die laufende Summe durch das Fenster Größe.

Hinweis Scan ist genau wie fold, aber geben Sie jede Version des Staates in eine Sequenz. Eine noch elegantere Lösung, obwohl möglich, mit Leistungshit ist , um die Beobachtung zu machen, dass, wenn wir die Sequenz 0 auffüllen, wir nicht benötigen, um die Anfangssumme zu berechnen.

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 

Es könnte eine Leistung aufgrund der zweiten indirection zum Umwickeln der beiden Sequenzen im Zusammenhang getroffen sein, aber vielleicht ist es nicht von Bedeutung auf der Größe des Fensters je

Answer 6

Das ist meine 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 

Beispiel:

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