حساب المتوسط ​​المتحرك في F#

Question

ما زلت أعمل على تحسين الشيء F# - أحاول معرفة كيفية "التفكير" في F# بدلاً من مجرد الترجمة من اللغات الأخرى التي أعرفها.

لقد فكرت مؤخرًا في الحالات التي لا يكون لديك فيها خريطة 1: 1 بين قبل وبعد.الحالات التي يسقط فيها List.map.

أحد الأمثلة على ذلك هو المتوسطات المتحركة، حيث عادةً ما يكون لديك نتائج len-n+1 لقائمة الطول len عند حساب المتوسط ​​على n من العناصر.

بالنسبة للمعلمين، هل هذه طريقة جيدة للقيام بذلك (باستخدام قائمة الانتظار المضغوطة من جومو فيشر)?

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

(ربما تكون الطريقة الأفضل هي تنفيذ MovingAverageQueue عن طريق الوراثة من Fifo؟)

Answer 1

إذا كنت لا تهتم كثيراً بالأداء، فإليك الحل البسيط للغاية:

#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

يؤدي هذا إلى إعادة حساب متوسط ​​كل "نافذة" من الصفر، لذلك يكون الأمر سيئًا إذا كانت النوافذ كبيرة.

على أية حال، تحقق من Seq.windowed:

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

لأنه من السهل أن يكون لديك في جيبك الخلفي لمثل هذه الأشياء.

Answer 2

اذا أنت يفعل إذا كنت تهتم بالأداء، فيمكنك حساب المتوسط ​​المتحرك بكفاءة باستخدام شيء من هذا القبيل (بافتراض أننا نحسب المتوسط ​​المتحرك خلال نافذة مدتها 3 أيام)

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]

الجزء الصعب في هذا الأمر هو الاحتفاظ بإجمالي ورقم التشغيل السابق_{نافذة N}.لقد توصلت إلى الكود التالي:

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

لا يبدو هذا الإصدار جميلًا مثل كود Haskell، لكنه يجب أن يتجنب مشكلات الأداء المرتبطة بإعادة حساب "النافذة" الخاصة بك في كل تشغيل.فهو يحتفظ بإجمالي قيد التشغيل ويحتفظ بالأرقام المستخدمة مسبقًا في قائمة الانتظار، لذلك يجب أن يكون سريعًا جدًا.

من باب التسلية فقط كتبت معيارًا بسيطًا:

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

نتائج:

princessAverage: 1670.791800
windowAverage: 2986.146900

الإصدار الخاص بي أسرع بـ 1.79 مرة تقريبًا.

Answer 3

وهنا هو ل(تصحيح، وآمل) F # نسخة من الحل المقترح هاسكل هنا .

وتحرير: الآن الذيل عودي، وليس أي أسرع، ولكن لا تنفجر مع ن = 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

إذا كنت تهتم الأداء ومثل الرمز أنيقة ثم حاول

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 يمكننا اختبار

 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

والحيلة من الخوارزمية هي مجموع أول أعداد ن الأولى و ثم الحفاظ على تشغيل إجمالي بإضافة الرأس من النافذة وطرح الذيل من النافذة. نافذة انزلاق هو تحقيق ذلك من خلال القيام البريدي النفس على تسلسل ولكن مع ثاني حجة لالبريدي التي تقدمت بها حجم النافذة.

في نهاية خط الأنابيب نحن فقط تقسيم المجموع على التوالي من النافذة بحجم.

ملحوظة المسح هو تماما مثل أضعاف، ولكنه سيحقق كل إصدار من الدولة إلى تسلسل.

وحلا حتى أكثر أناقة على الرغم possibley مع ضرب الأداء لجعل الملاحظة أنه إذا كنا الصفر لوحة تسلسل نحن لسنا بحاجة لحساب المبلغ الأولي.

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

ويمكن أن يكون هناك أداء إصابة بسبب المراوغة الثاني تتعلق التفاف تسلسل اثنين ولكن ربما ليس كبيرا اعتمادا على حجم النافذة

Answer 5

وهذا هو الإصدار بلدي.

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

مثال:

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

Answer 6

بقدر ما أستطيع أن أرى، التعليمات البرمجية الخاصة بك مليئة let صياغات.لست على دراية بـ F# ولكني قمت ببعض أعمال Haskell.النموذج الوظيفي يعني عدم التفكير في "كيف" بل في "ماذا":أنت تعتقد أن Fifo، ولكن يجب عليك في الواقع تحديد دلالات المتوسط ​​المتحرك.

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