And maybe another one to show deviation problem ? testRunningMeansDeviation | result1 result2 col1 col2 | col1 := #(0.3s1 1s1 0.1s1 0.3s1 1s1 0.1s1 0.3s1 1s1 0.1s1). result1 := col1 runningMeans: 2. col2 := #(0.3 1 0.1 0.3 1 0.1 0.3 1 0.1). result2 := col2 runningMeans: 2. self assert: result1 first equals: result1 fourth. "presence of a rounding error" self deny: result2 first equals: result2 fourth. self assert: result2 first closeTo: result2 fourth.
Le 13 avr. 2020 à 10:48, Cédrick Béler <cdrick65@gmail.com> a écrit :
What about this test (in OrderedCollectionTest - it suggests a Trait too) ?
testRunningMeans
| result col | col := #(1 1 2 2 3 3) asOrderedCollection. result := col runningMeans: 2.
self assert: (result = {1. (3/2). 2. (5/2). 3}).
self assert: (result class = Array).
self assert: result size <= (col size). "Running means with 1 has little interest ?"
self should: [ col runningMeans: 7 ] raise: SubscriptOutOfBounds. self should: [ col runningMeans: -2 ] raise: SubscriptOutOfBounds. self should: [ col runningMeans: 1.3 ] raise: Error withExceptionDo: [ :anException | self assert: anException messageText equals: 'primitive #basicNew: in Array class failedâ ]
Cheers, Cédrick
Le 13 avr. 2020 à 04:47, Richard O'Keefe <raoknz@gmail.com> a écrit :
I did mention that it was one of eight implementations that I tried. In fact you broke it with your change. It is important ***NOT*** to keep a running sum but a running MEAN. The line m := ((self at: i) - (self at: d)) / width + m was written that way for a reason.
I did think of renaming the variables for general use, but decided to display the actual code that I tested. If you want polished code, here it is.
runningMeans: width "This returns an array of running means as if the receiver were broken into overlapping segments 'width' long and the mean of each calculated. This uses an adaptation of Welford's algorithm for stably updating the mean; it is important to maintain a current MEAN not a current SUM. This has been tested against 7 other algorithms. It was the most accurate of the faster ones. The result is an Array no matter what kind of sequence the receiver is. If the receiver is a tree (like a virtual concatenation) or a singly or doubly linked list you should convert the receiver to an Array first. Note that there is no explicit check that width is an Integer or is in range; none is needed because those checks happen anyway." |result mean resultIndex| result := Array new: self size - width + 1. mean := 0. 1 to: width do: [:i | mean := (self at: i) + mean]. mean := mean / width. resultIndex := 1. result at: resultIndex put: mean. width + 1 to: self size do: [:i | mean := ((self at: i) - (self at: resultIndex)) / width + mean. resultIndex := resultIndex + 1. result at: resultIndex put: mean]. ^result
On Mon, 13 Apr 2020 at 00:23, Sven Van Caekenberghe <sven@stfx.eu> wrote:
On 12 Apr 2020, at 13:53, Cédrick Béler <cdrick65@gmail.com> wrote:
Beautiful ^^
I also like it.
But why the single letter variable names ? Why not:
SequenceableCollection>>#runningMeans: width | means sum index | means := Array new: self size - width + 1. sum := 0. 1 to: width do: [ :each | sum := sum + (self at: each) ]. index := 1. means at: index put: sum / width. width + 1 to: self size do: [ :each | sum := sum - (self at: index) + (self at: each). index := index + 1. means at: index put: sum / width ]. ^ means
A good comment, a correct initial bounds check and unit tests are also needed.
I would vote for inclusion in the base image ? With your explanation as comments.
Iâll play with it.
Thanks Cedrick
Le 12 avr. 2020 à 12:19, Richard O'Keefe <raoknz@gmail.com> a écrit :
 I have coded and benchmarked 8 different running mean algorithms. In the presence of inexact numbers it is not as accurate as redoing the sums, but it's pretty close, and it's fast. If "width" is not an integer or is out of range, an error will be reported by #new: or #at:[put:]. It's based on Welford's stable update.
Of course this approach does NOT work for trimmed or Winsorised means or for medians or any kind of robust estimate of location.
SequenceableCollection methods for: 'summarising' runningMeans: width |a m d| a := Array new: self size - width + 1. m := 0. 1 to: width do: [:i | m := (self at: i) + m]. m := m / width. d := 1. a at: d put: m. width + 1 to: self size do: [:i | m := ((self at: i) - (self at: d)) / width + m. d := d + 1. a at: d put: m]. ^a