Calcular un promedio móvil en F #

Question

Todavía estoy trabajando en asimilar lo de F #, tratando de averiguar cómo 'pensar' en F # en lugar de solo traducir de otros idiomas que conozco.

Recientemente he estado pensando en los casos en los que no tienes un mapa 1: 1 entre antes y después. Casos en los que se cae List.map.

Un ejemplo de esto son los promedios móviles, donde normalmente tendrá resultados len-n + 1 para una lista de longitud len cuando promedia más de n elementos.

Para los gurús, esta es una buena manera de hacerlo (usando la cola pellizcada de 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.]

(¿Quizás una mejor manera sería implementar un MovingAverageQueue heredando de Fifo?)

Answer 1

Si no te importa demasiado el rendimiento, aquí hay una solución muy 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

Esto vuelve a calcular el promedio de cada 'ventana' desde cero, por lo que es pobre si las ventanas son grandes.

En cualquier caso, echa un vistazo a Seq.windowed:

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

ya que es útil tener en el bolsillo trasero para tales cosas.

Answer 2

Si te importa el rendimiento, entonces puedes calcular un promedio móvil de manera eficiente usando algo como esto (suponiendo que estemos calculando un promedio móvil en una ventana de 3 días)

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 difícil de esto es mantener el total acumulado anterior y el número _N-window . Se me ocurrió el siguiente código:

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

Esta versión no es tan bonita como el código Haskell, pero debería evitar los problemas de rendimiento asociados con el cálculo de su " ventana " en cada carrera. Mantiene un total acumulado y contiene los números utilizados anteriormente en una cola, por lo que debería ser muy rápido.

Solo por diversión, escribí un punto de referencia 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"

Resultados:

princessAverage: 1670.791800
windowAverage: 2986.146900

Mi versión es ~ 1.79x más rápida.

Answer 3

Aquí hay una versión (corregida, espero) F # de la solución de Haskell propuesta aquí .

EDITAR: ahora recursivo de cola, no más rápido, pero no explota con n = 50000. (vea el historial de edición para la versión no recursiva de cola)

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 le importa el rendimiento y le gusta el código elegante, intente

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 podemos probarlo

 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

El truco del algoritmo es la primera suma de los primeros n números y luego mantenga un total acumulado agregando el encabezado de la ventana y restando la cola de la ventana. La ventana corredera es logrado haciendo un auto zip en la secuencia pero con el segundo argumento para comprimir avanzado por el tamaño de la ventana.

Al final de la tubería, simplemente dividimos el total acumulado por la ventana tamaño.

Note que el escaneo es como doblar pero produce cada versión del estado en una secuencia.

Una solución aún más elegante, aunque posiblemente con éxito en el rendimiento es para hacer la observación de que si ponemos a cero la secuencia no necesitamos para calcular la suma inicial.

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

Podría haber un impacto en el rendimiento debido a la segunda indirección relacionada con el ajuste de las dos secuencias pero quizás no sea significativo dependiendo sobre el tamaño de la ventana

Answer 5

Esta es mi versión.

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

Ejemplo:

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

Answer 6

Hasta donde puedo ver, su código está lleno de declaraciones let . No estoy familiarizado con F # pero hice algo de Haskell. El paradigma funcional significa no pensar en "cómo". pero acerca de "qué": piensas Fifo, pero en realidad solo debes especificar la semántica de la media móvil.

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