Вычисление скользящего среднего в F#
-
08-07-2019 - |
Вопрос
Я все еще работаю над темой 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?)
Решение
Если вы не слишком заботитесь о производительности, вот очень простое решение:
#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:
как удобно иметь в заднем кармане для таких вещей.
Другие советы
Если вы делать заботитесь о производительности, тогда вы можете эффективно рассчитать скользящее среднее, используя что-то вроде этого (при условии, что мы рассчитываем скользящее среднее за трехдневное окно)
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, предложенного здесь .
РЕДАКТИРОВАТЬ: теперь хвостовая рекурсия, не быстрее, но не взрывается при 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 продвинут на размер окна.
В конце конвейера мы просто делим промежуточную сумму на окно размер. Р>
Сканирование заметок похоже на сгиб, но выдает каждую версию состояния в последовательность.
Еще более элегантное решение, которое возможно с потерей производительности, сделать замечание, что если мы обнуляем последовательность нам не нужна рассчитать начальную сумму.
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 )