algorithm - promedio - medias moviles analisis tecnico

Cálculo de una media móvil en F#

Question

Todavía estoy trabajando en descifrar lo de F #, tratando de encontrar la manera de ''pensar'' en F # en lugar de solo traducir desde 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 donde List.map se cae.

Un ejemplo de esto son los promedios móviles, donde normalmente obtendrá resultados len-n + 1 para una lista de longitudes de longitud al promediar más de n elementos.

Para los gurús que hay, ¿es esta una buena manera de hacerlo (utilizando 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.]

(¿Tal vez una forma mejor sería implementar una MovingAverageQueue heredando de Fifo?)

Answer 1

Por lo que puedo ver, tu código está lleno de declaraciones de let . No estoy familiarizado con F # pero hice algo de Haskell. El paradigma funcional significa no pensar en "cómo" sino en "qué": piensas en 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 )

Answer 2

Si no le 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 recalcula el promedio de cada ''ventana'' desde cero, por lo que es pobre si las ventanas son grandes.

En cualquier caso, revisa Seq.windowed:

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

ya que es útil tenerlo en el bolsillo trasero para esas cosas.

Answer 3

Si le importa el rendimiento, puede calcular una media móvil de manera eficiente usando algo como esto (suponiendo que estamos calculando una media móvil en un período 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 retener 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 reajuste de su "ventana" en cada ejecución. Mantiene un total acumulado y mantiene los números usados ​​anteriormente en una cola, por lo que debe 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 4

Si te preocupa el rendimiento y te gusta el código elegante, prueba

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 mantener un total acumulado sumando el encabezado de la ventana y restando la cola de la ventana. La ventana deslizante se logra 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, solo dividimos el total acumulado por el tamaño de la ventana.

El escaneo de notas es como doblar pero produce cada versión del estado en una secuencia.

Una solución aún más elegante, aunque posible con el rendimiento alcanzado es hacer la observación de que si no rellenamos la secuencia, no necesitamos 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 golpe de rendimiento debido a la segunda indirección relacionada con el ajuste de las dos secuencias, pero tal vez no sea significativo dependiendo del 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

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

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

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