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が落ちるケース。
この例の1つは移動平均です。通常、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を継承してMovingAverageQueueを実装する方が良いでしょうか？）
解決
パフォーマンスをあまり気にしない場合、非常に簡単な解決策を以下に示します。
#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]
これに関する難しい部分は、以前の実行合計とNumber N-window を保持することです。次のコードを思いつきました：
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倍高速です。
提案されているHaskellソリューションの（修正済み、希望）F＃バージョンここ。
編集：末尾再帰、高速ではありませんが、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
アルゴリズムの秘Theは、最初のn個の数字の最初の合計と 次に、ウィンドウの先頭を追加して、積算合計を維持します ウィンドウの末尾を減算します。スライディングウィンドウは シーケンスでセルフzipを実行することで、2番目の zipへの引数はウィンドウサイズごとに進みます。
パイプラインの最後で、現在の合計をウィンドウで割るだけです サイズ。
メモスキャンはfoldに似ていますが、状態の各バージョンを生成します シーケンス。
パフォーマンスヒットは可能ですが、さらにエレガントなソリューションは シーケンスをゼロで埋める必要がないという観察をするために 初期合計を計算します。
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
に関連する2番目の間接性が原因で、パフォーマンスが低下する可能性があります 2つのシーケンスのラッピングですが、おそらく重要ではありません ウィンドウのサイズについて
これは私のバージョンです。
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
