F#의 이동 평균 계산
https://stackoverflow.com/questions/295336
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 아직도 F# 사물을 사로 잡기 위해 노력하고 있습니다. 내가 아는 다른 언어에서 번역하는 대신 F#에서 '생각'하는 방법을 알아 내려고 노력하고 있습니다.
나는 최근에 전후 사이에 1 : 1지도가없는 경우에 대해 생각하고 있습니다. List.map이 떨어지는 경우.
이것의 한 예는 움직이는 평균이며, 여기서 일반적으로 N 항목을 평균화 할 때 길이 Len 목록에 대해 LEN-N+1 결과가 있습니다.
거기에있는 전문가에게는 이것이 좋은 방법입니다 ( 조모 피셔)?
//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.]
(아마도 더 나은 방법은 FIFO에서 상속을 통해 MovementAveragequeue를 구현하는 것일 것입니까?)
해결책
성능에 너무 신경 쓰지 않는다면 여기에 매우 간단한 솔루션이 있습니다.
#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를 확인하십시오.
그런 것들을 위해 뒷주머니에있는 것이 편리합니다.
다른 팁
만약 너라면 하다 성능에주의하면 이와 같은 것을 사용하여 이동 평균을 효율적으로 계산할 수 있습니다 (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 배 빠릅니다.
다음은 (수정 된, 희망) F# 버전의 Haskell 솔루션이 제안되었습니다. 여기.
편집 : 이제 Tail Recursive, 더 빠르지는 않지만 N = 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; ...]
성능에 관심이 있고 우아한 코드를 좋아한다면
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
알고리즘의 트릭은 첫 번째 N 숫자 인 첫 번째 합계이며 창의 헤드를 추가하고 창의 꼬리를 빼서 달리기 총계를 유지합니다. 슬라이딩 윈도우는 시퀀스에서 자체 지퍼를 수행하지만 창 크기에 의해 Zip에 대한 두 번째 인수와 함께 달성됩니다.
파이프 라인의 끝에서 우리는 단지 런닝 총계를 창 크기로 나눕니다.
참고 스캔은 접힘과 같지만 각 버전의 상태를 시퀀스로 산출합니다.
성능 히트로 가능하지만 더 우아한 솔루션은 시퀀스를 0으로하면 초기 합을 계산할 필요가 없다는 관찰입니다.
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
두 시퀀스의 포장과 관련된 두 번째 간접로 인해 성능이 발생할 수 있지만 창 크기에 따라 중요하지 않을 수 있습니다.
이것은 내 버전입니다.
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, ...]
내가 볼 수있는 한, 당신의 코드는 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 )
제휴하지 않습니다 StackOverflow
