F #

Question

içinde bir hareketli ortalama hesaplamak Hala F # şey grotting üzerinde çalışıyorum - biliyorum sadece diğer dillerden çeviri yerine F # düşünmek için çalışıyoruz çalışıyor.

Son zamanlarda, önce ve sonra arasında 1: 1 haritasının olmadığı durumlarda düşündüm. List.map'in düştüğü durumlar.

Bunun bir örneği, n öğelerinin ortalaması alınırken uzunluk uzunluğunun listesi için genellikle len-n + 1 sonuçlarına sahip olduğunuz ortalamaları hareket ettirmektir.

Dışarıdaki gurular için, bunu yapmanın iyi bir yolu var (Jomo Fisher numaralı sorguç dizilimi kullanılarak)?

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

(Belki daha iyi bir yol FIFO devralmasını tarafından MovingAverageQueue uygulamak olurdu?)

Answer 1

(non-kuyruk-özyinelemeli sürüm ilişkin düzenleme geçmişini bakınız) performansı hakkında çok fazla, burada çok basit bir çözümdür:

#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 

Bu sıfırdan her 'penceresinin' ortalamasını recomputes, bu yüzden pencereler büyükse o kötü. Her durumda

, Seq.windowed check out:

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

böyle şeyler için arka cebinde olması kullanışlı olduğu gibi.

Answer 2

Bildiğim kadarıyla gördüğünüz gibi, kodunuz let tabloların doludur. F # ile aşina değilim ama bazı Haskell yaptım. İşlevsel paradigma, "nasıl", ama "ne" hakkında düşünmemek demektir: Fifo'yu düşünüyorsunuz, fakat aslında, sadece hareketli ortalamanın anlamlarını belirtmelisiniz. İşte

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

here önerdi Haskell çözümün bir (Umarım düzeltilmiş) F # versiyonu. DÜZENLEME

: Artık kuyruk özyinelemeli değil daha hızlı, fakat patlamaz n = Umrunda yoksa 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

Eğer performansı hakkında umurumda , o zaman böyle bir hareketli ortalama verimli kullanarak bir şey

 
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] 

sert (biz 3 günlük pencere üzerinde hareketli ortalamasını hesaplayarak varsayarsak) hesaplayabilirsiniz bununla ilgili bölüm, önceki çalışan toplamınızda ve _{N pencerede} numaralı numarada tutulmaktadır.

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

Bu sürüm Haskell kodu olarak seyir kadar güzel değil ama her kaçarak "pencere" recomputing ile ilişkili performans sorunları önlemek olmalıdır: Aşağıdaki kod ile gündeme geldi. Çalışan bir toplam tutar ve daha önce kullanılan numaraları bir sıraya tutar, bu yüzden çok hızlı olmalıdır.

#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" 

Sonuçlar::

princessAverage: 1670.791800 
windowAverage: 2986.146900

Benim versiyon 1.79x daha hızlı ~ olan

Sadece eğlence için, basit bir kriter yazdı.

Answer 5

sonra FSUnit kullanma

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 

deneyin performansı hakkında ve zarif kodu gibi veriyorsan biz algoritmanın hüner ilk toplamı ilk n sayı ve olduğunu o

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 

test edebilirsiniz Daha sonra pencerenin başlığını ekleyerek ve pencerenin kuyruğunu çıkararak çalışan bir toplamı koruyun. Kayan pencere, sekans üzerinde bir öz zip yapılarak elde edilen 'dir, ancak pencere boyutu tarafından ilerletilen zip için ikinci argümanı ile elde edilir.

Boru hattının sonunda, çalışan toplamı sadece boyutundaki pencereye böleriz.

Not taraması sadece katlama gibidir, ancak durumun her bir sürümünü dizisine verin.

bir daha zarif bir çözüm da performans düşüşüne sahip possibley biz pedi sıfır ise sekans biz ilk toplamını hesaplamak için gerekmez gözlem yapmak için olup.

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 

iki dizinin sarma ile ilgili ikinci dolaylama nedeniyle vurmak bir performans var olabilir ama belki de bu benim sürümüdür pencerede

Answer 6

boyutuna bağlı önemli değildir.

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 

Örnek:

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