Berechnen eines gleitenden Durchschnitt in F #

Question

Ich arbeite immer noch die F #, was auf groking -. Versuchen, herauszufinden, wie zu ‚denken‘ in F # und nicht nur aus anderen Sprachen übersetzen Ich weiß

Ich habe vor kurzem über die Fälle gedacht, in denen Sie nicht über eine 1: 1-Karte vor und nach. Fälle, in denen List.map nach unten fällt.

Ein Beispiel hierfür ist gleitender Durchschnitt, wo in der Regel werden Sie len-n + 1 Ergebnisse für eine Liste der Länge len, wenn eine Mittelung über n Elemente.

Für die Gurus gibt, ist dies ein guter Weg, es zu tun (mit Warteschlange eingeklemmt von 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.]

(Vielleicht ein besserer Weg, um eine MovingAverageQueue umzusetzen wäre durch von Fifo vererben?)

Answer 1

Wenn Sie nicht zu viel kümmern sich um 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

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

Auf jeden Fall überprüfen 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

Wenn Sie tun kümmern uns um die Leistung, 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 schwierige Teil über diese auf Ihrem vorherigen laufenden Gesamt halten und Anzahl _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 gut aussehende wie der Code Haskell, aber es sollte Performance-Probleme im Zusammenhang mit recomputing Ihr „Fenster“ auf jedem Lauf vermeiden. Es hält insgesamt läuft und bisher hält Zahlen in einer Warteschlange verwendet wird, so sollte es sehr schnell sein.

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 3

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

EDIT: Nun Schwanz-rekursiv, nicht schneller, aber nicht explodiert mit n = 50000. (siehe Versionsgeschichte für Nicht-tail-rekursive Version)

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 über die Leistung und wie elegant Code sorgen dann versuchen

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

Mit FSUnit wir können 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 dann aufrechtzuerhalten, indem das Kopf des Fensters eine laufende Gesamt und Subtrahieren des Schwanzes des Fensters. Das Schiebefenster ist erreicht, indem ein Selbst Reißverschluss auf der Sequenz zu tun, sondern mit dem zweiten Argument durch die Fenstergröße vorgeschoben sehen lassen.

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

Hinweis Scan ist wie Falte aber ergibt jede Version des Staates in eine Folge.

Eine noch elegantere Lösung mit Leistungseinbußen obwohl possibley ist um die Beobachtung zu machen, dass, wenn wir Pad, um die Null-Sequenz wir nicht brauchen die anfängliche Summe 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 Leistungseinbußen aufgrund der zweiten indirection auf die in Zusammenhang stehen Umwickeln der beiden Sequenzen, aber vielleicht ist es nicht von Bedeutung, je auf die Größe des Fensters

Answer 5

Dies 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, ...]

Answer 6

Soweit ich sehen kann, ist der Code von let Aussagen voll. Ich bin nicht mit F # vertraut, aber haben einige Haskell zu tun. Das funktionale Paradigma bedeutet nicht darüber nachzudenken, „wie“, sondern um „was“. Sie Fifo denken, aber man sollte die Semantik des gleitenden Durchschnitts gibt eigentlich nur

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