Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Simple Moving Average of a list of real numbers (Ozgur Akgun)
2. Re: Simple Moving Average of a list of real numbers
(Michael Orlitzky)
3. Re: Simple Moving Average of a list of real numbers (Kim-Ee Yeoh)
4. Re: IPerf in Haskell doesn't perform (Alexander Morozov)
5. Re: Simple Moving Average of a list of real numbers
(Michael Orlitzky)
6. Re: Simple Moving Average of a list of real numbers
(John Souvestre)
----------------------------------------------------------------------
Message: 1
Date: Tue, 26 Nov 2013 14:47:48 +0000
From: Ozgur Akgun <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Simple Moving Average of a list of
real numbers
Message-ID:
<calzazpbbz9tq_j6jlg7zv_3998hbvvvd4ds7hjce44ygjys...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi Alex.
On 25 November 2013 15:28, Alexandr M <[email protected]> wrote:
> Could anybody explain me how to calculate simple moving average of a list ?
>
> I have found several examples in internet but I completely don't
> understand how it works.
>
> Basically it's necessary to iterate over the list of real numbers and
> calculate average values over last n items in the list.
>
> I just can't imagine how to do it without loops.
>
Maybe we can use "inits" from "Data.List".
Prelude> import Data.List
Prelude Data.List> mapM_ print $ inits [1..10]
[]
[1]
[1,2]
[1,2,3]
[1,2,3,4]
[1,2,3,4,5]
[1,2,3,4,5,6]
[1,2,3,4,5,6,7]
[1,2,3,4,5,6,7,8]
[1,2,3,4,5,6,7,8,9]
[1,2,3,4,5,6,7,8,9,10]
Not a bad start. It gives us all the *initial segments* of a list.
Now we need to keep the last n items for each of these. Let's see. Maybe we
can define a function using "drop" and "length" as follows.
Prelude Data.List> let lastN n xs = drop (length xs - n) xs
This function should drop everything but the last n items in a list. If
there are less than n items, it will return the list unchanged.
Try it on a few inputs to see why this is the case. Also try "drop" on a
few inputs.
And the type of this function seems sensible enough:
Prelude Data.List> :t lastN
lastN :: Int -> [a] -> [a]
Now:
Prelude Data.List> mapM_ print $ map (lastN 3) $ inits [1..10]
[]
[1]
[1,2]
[1,2,3]
[2,3,4]
[3,4,5]
[4,5,6]
[5,6,7]
[6,7,8]
[7,8,9]
[8,9,10]
This seems pretty close to what you want. For each item in the list, we
have a corresponding list of n items that are coming just before it.
If only we had a function to calculate the average of a list of numbers,
then we could:
Prelude Data.List> mapM_ print $ map average $ map (lastN 3) $ inits [1..10]
NaN
1.0
1.5
2.0
3.0
4.0
5.0
6.0
7.0
8.0
9.0
I've defined average locally here to demonstrate the use of it. I'll leave
the definition of it as an exercise to you.
Of course, depending on what you want to do with these averages, you can
implement the same functionality in different ways.
Maybe you only need the last one only or something else. I don't know.
Also you can *fuse* the two maps and use only one map, but I wanted to keep
things explicit.
Hope this helps,
Ozgur.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20131126/678e03a0/attachment-0001.html>
------------------------------
Message: 2
Date: Tue, 26 Nov 2013 12:11:56 -0500
From: Michael Orlitzky <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Simple Moving Average of a list of
real numbers
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
On 11/25/2013 10:28 AM, Alexandr M wrote:
> Hello !
>
> Could anybody explain me how to calculate simple moving average of a list ?
>
> I have found several examples in internet but I completely don't
> understand how it works.
>
> Basically it's necessary to iterate over the list of real numbers and
> calculate average values over last n items in the list.
>
> I just can't imagine how to do it without loops.
When you need to know the position of something in a list, one easy way
to get it is to "zip" the original list with another list of
"positions", [1,2,3,...]. Then when you're processing the list, you're
not just dealing with some element somewhere in the list, you have the
ordered pair (item, position) which you probably know what to do with.
Inline below is some code that uses this idea along with a "scan"
(similar to a fold) to accomplish the moving average. Here it is in action:
Prelude> :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] :: [Double]
*Main> let mavg = moving_average samples
*Main> print mavg
[(1.0,1.0),(1.5,2.0),(2.0,3.0),(2.5,4.0),(3.0,5.0)]
If you only want the averages (and not the positions), the positions are
easy to drop:
*Main> print $ map fst mavg
[1.0,1.5,2.0,2.5,3.0]
Code below. I've tried to avoid line wrapping, but buyer beware.
module Main
where
-- | Create a list whose nth entry is a pair containing the average of
-- the first n elements of the given samples, along with the
-- position n. We use a "scan" to do this; a scan is like a fold
-- except it keeps track of the intermediate values and not just the
-- final one.
--
-- We can use this to our advantage; the nth average is just (n-1)
-- times the previous average, added to the current item, and then
-- divided by n. So we will thread a pair, (average, position),
-- through the list computing each average from the previous one as
-- we go.
--
-- The result should be a list of all averages we generated along
-- the way. If you want to drop the positions from the result, you
-- can simply call `map fst` on it.
--
moving_average :: (Fractional a) => [a] -> [(a,a)]
moving_average [] = []
moving_average samples =
-- scanl1 uses the first entry of samples_pos as the first entry in
-- the result. Since we don't need to do any averaging of the first
-- item (it gets divided by one), this is what we want.
scanl1 average samples_pos
where
-- The indices we'll use for the positions in the list. We use
-- fromIntegral on all of them because we want to be able to
-- divide by them, so they need to be converted to something
-- Fractional (GHC will figure it out).
positions = map fromIntegral [1..]
-- The list samples_pos contains the original samples "zipped" with
-- their position in the list. The entries of samples_pos should be
-- pairs (x,y) where x was te original entry in the list, and y
-- was its position. This lets us know which number we need to
-- divide by for the average
samples_pos = zip samples positions
-- This is the function that does the work. It takes the previous
-- (average, position) pair and the new (value, position) pair and
-- uses them to generate the new (average, position).
average :: (Fractional b) => (b,b) -> (b,b) -> (b,b)
average (prev_avg, prev_pos) (sample, pos) =
(new_avg, pos)
where
prev_sum = prev_avg * prev_pos
new_avg = (prev_sum + sample) / pos
------------------------------
Message: 3
Date: Wed, 27 Nov 2013 00:54:27 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Simple Moving Average of a list of
real numbers
Message-ID:
<CAPY+ZdTp=da8+_vpjei_vza3xif5y5wwmfujz3abngsije6...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
On Wed, Nov 27, 2013 at 12:11 AM, Michael Orlitzky <[email protected]>wrote:
> Inline below is some code that uses this idea along with a "scan"
> (similar to a fold) to accomplish the moving average.
>
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!
-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20131127/6c67d362/attachment-0001.html>
------------------------------
Message: 4
Date: Tue, 26 Nov 2013 23:32:42 +0400
From: Alexander Morozov <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] IPerf in Haskell doesn't perform
Message-ID:
<CALRpspm1GN=FNRedxa+xOR4zdTmT6vgcwo=py4ylzr7-ujz...@mail.gmail.com>
Content-Type: text/plain; charset=windows-1252
If it's still relevant... The problem is that the program sends data
in 8 byte chunks. Every write results in a syscall, context switch and
pushing the chunk through TCP stack, so overhead is great.
BTW, using Bytestring works well enough, my similar program [1] pushes
around 15Gbits through lo interface and saturates 1Gbit ethernet
connection.
[1] https://github.com/alexandermorozov/netperf
Regards,
Alexander
On Sat, Nov 9, 2013 at 5:08 PM, Thomas Bach
<[email protected]> wrote:
> On Thu, 2013-11-07 at 14:55 -0800, Bob Ippolito wrote:
>> I took your code and made a few style cleanups so that hlint wouldn't
>> complain and so that it would be easier to read.
>
> Being able to see those changes you made one by one on github.com was
> very instructive. Thanks!
>
>>
>> The space leak is a strictness issue that is common for Haskell
>> beginners to do. [?]
>
> Interesting. I wouldn't have thought of that.
>
> So, the space leak is avoided. Now, how do I get this thing to perform?
> Profiling the program is probably the way to go. Hopefully I find the
> time for this this week end.
>
>
> Regards,
>
> Thomas.
>>
>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 5
Date: Tue, 26 Nov 2013 21:39:17 -0500
From: Michael Orlitzky <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Simple Moving Average of a list of
real numbers
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
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
------------------------------
Message: 6
Date: Tue, 26 Nov 2013 22:58:28 -0600
From: "John Souvestre" <[email protected]>
To: "'The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell'" <[email protected]>
Subject: Re: [Haskell-beginners] Simple Moving Average of a list of
real numbers
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
> Oh, sorry. Statistics is down the hall =)
There is another often used method which might be worth considering. If you
don't need the absolute accuracy that the "boxcar" moving average gives, then
perhaps a exponentially weighted moving average (aka: exponential filter) will
do. It has the advantage of being easier to code, requiring less CPU power
(normally), and needing only one variable for long term storage.
There a good description at:
http://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average
Simply put, you save only the result, not the individual sample. To update it
with a new sample you first remove the "equivalent" of one sample then add
your new sample. How do you remove the oldest sample? You can't, since you
didn't save it. Instead you remove 1/n'th (for averaging over n samples) of
the previous result, then add the new sample.
If you think about it, the longer a sample has been part of the result, the
less effect it has on the result - exponentially less. This is why I said it
isn't as accurate as the boxcar method. But for many situations (most of the
ones I've run into) it suffices and indeed can be better since it dampens
(filters) step changes.
As an equation:
average_new = average_old - (average_old / n) + (sample_new / n)
Or tweaking for efficiency:
average_new = average_old + ( (sample_new - average_old) / n )
Note: You need to use floating point numbers for the calculation and
resulting average, even if the samples are integers. Also, choosing a binary
number for n should help speed up the division, if the math pack takes
advantage of it.
I realize that this doesn't directly address the question which Alex posed,
but I thought that perhaps it might be of interest as an alternative.
John
??? John Souvestre - New Orleans LA - (504) 454-0899
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 6298 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20131126/1232e1b5/attachment.bin>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 65, Issue 11
*****************************************
