On 11/26/2013 12:54 PM, Kim-Ee Yeoh wrote:
Hi Michael,
When I read OP's request, I understood it as what Ozgur had interpreted, i.e. last N items for a /constant/ N, also known as a moving window average.
Your running average solution is interesting too!
Oh, sorry. Statistics is down the hall =) You need to modify the scanl1 solution a little bit, but it should still work somewhat-efficiently only making one pass through the list and not using any partial functions. If the "window size" n is fixed, we need more information at each point in the list: 1. The item itself 2. What number we should subtract from the previous sum 3. What the previous divisor was 4. What the new divisor is (I'm assuming you want the first n items to be the running average, i.e. my first implementation.) The divisor that we'll use at each point is, [1, 2, ..., n, n, n...] and that can be zipped with the samples just like before. The other thing that we need is the item that will be "dropped" from the average. If the window is fixed, we'll be dropping one number and adding one number every time we move to a new item in the list (once we've processed n of them, at least). Before we've processed n of them, we don't want to subtract anything from the previous sum -- we want the running average. We can accomplish this by sticking n-1 zeros on the head of the samples, and zipping *that* with the samples. I haven't commented this version, but if you understand the last one, you can figure out what it does. Here's the example Ozgur used: *Main> :l moving_average.hs [1 of 1] Compiling Main ( moving_average.hs, interpreted ) Ok, modules loaded: Main. *Main> let samples = [1,2,3,4,5,6,7,8,9,10] :: [Float] *Main> moving_average 3 samples [1.0,1.5,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0] (They agree.) It can do a million items pretty quickly considering we're in ghci: *Main> let samples = [1..1000000] :: [Float] *Main> :set +s *Main> length $ moving_average 10 samples 1000000 (1.08 secs, 545400640 bytes) -------- module Main where fst3 :: (a,b,c) -> a fst3 (x, _, _) = x moving_average :: (Fractional a) => Int -> [a] -> [a] moving_average _ [] = [] moving_average n samples | n <= 0 = [] | otherwise = map fst3 $ scanl1 average sample_triples where divisors = map fromIntegral $ [1..n] ++ (repeat n) n_agos = (map fromIntegral (replicate (n-1) 0)) ++ samples sample_triples = zip3 samples divisors n_agos average :: (Fractional b) => (b,b,b) -> (b,b,b) -> (b,b,b) average (prev_avg, prev_div, dropme) (sample, divisor, n_ago) = (new_avg, divisor, n_ago) where prev_sum = prev_avg * prev_div new_avg = (prev_sum + sample - dropme) / divisor