diff options
Diffstat (limited to 'series')
| -rw-r--r-- | series/message.go | 19 | ||||
| -rw-r--r-- | series/series.go | 280 | ||||
| -rw-r--r-- | series/series_test.go | 846 | ||||
| -rw-r--r-- | series/statistics.go | 74 |
4 files changed, 1219 insertions, 0 deletions
diff --git a/series/message.go b/series/message.go new file mode 100644 index 0000000..fa0b096 --- /dev/null +++ b/series/message.go @@ -0,0 +1,19 @@ +package series + +import ( + "github.com/network-quality/goresponsiveness/utilities" + "golang.org/x/exp/constraints" +) + +type SeriesMessageType int + +const ( + SeriesMessageReserve SeriesMessageType = iota + SeriesMessageMeasure SeriesMessageType = iota +) + +type SeriesMessage[Data any, BucketType constraints.Ordered] struct { + Type SeriesMessageType + Bucket BucketType + Measure utilities.Optional[Data] +} diff --git a/series/series.go b/series/series.go new file mode 100644 index 0000000..0084007 --- /dev/null +++ b/series/series.go @@ -0,0 +1,280 @@ +/* + * This file is part of Go Responsiveness. + * + * Go Responsiveness is free software: you can redistribute it and/or modify it under + * the terms of the GNU General Public License as published by the Free Software Foundation, + * either version 2 of the License, or (at your option) any later version. + * Go Responsiveness is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A + * PARTICULAR PURPOSE. See the GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with Go Responsiveness. If not, see <https://www.gnu.org/licenses/>. + */ +package series + +import ( + "fmt" + + "github.com/network-quality/goresponsiveness/utilities" + "golang.org/x/exp/constraints" +) + +type WindowSeriesDuration int + +const ( + Forever WindowSeriesDuration = iota + WindowOnly WindowSeriesDuration = iota +) + +type WindowSeries[Data any, Bucket constraints.Ordered] interface { + fmt.Stringer + + Reserve(b Bucket) error + Fill(b Bucket, d Data) error + + Count() (some int, none int) + + ForEach(func(Bucket, *utilities.Optional[Data])) + + GetValues() []utilities.Optional[Data] + Complete() bool + GetType() WindowSeriesDuration +} + +type windowSeriesWindowOnlyImpl[Data any, Bucket constraints.Ordered] struct { + windowSize int + data []utilities.Pair[Bucket, utilities.Optional[Data]] + latestIndex int + empty bool +} + +/* + * Beginning of WindowSeries interface methods. + */ + +func (wsi *windowSeriesWindowOnlyImpl[Data, Bucket]) Reserve(b Bucket) error { + if !wsi.empty && b <= wsi.data[wsi.latestIndex].First { + return fmt.Errorf("reserving must be monotonically increasing") + } + + if wsi.empty { + /* Special case if we are empty: The latestIndex is where we want this value to go! */ + wsi.data[wsi.latestIndex] = utilities.Pair[Bucket, utilities.Optional[Data]]{ + First: b, Second: utilities.None[Data](), + } + } else { + /* Otherwise, bump ourselves forward and place the new reservation there. */ + wsi.latestIndex = wsi.nextIndex(wsi.latestIndex) + wsi.data[wsi.latestIndex] = utilities.Pair[Bucket, utilities.Optional[Data]]{ + First: b, Second: utilities.None[Data](), + } + } + wsi.empty = false + return nil +} + +func (wsi *windowSeriesWindowOnlyImpl[Data, Bucket]) Fill(b Bucket, d Data) error { + iterator := wsi.latestIndex + for { + if wsi.data[iterator].First == b { + wsi.data[iterator].Second = utilities.Some[Data](d) + return nil + } + iterator = wsi.nextIndex(iterator) + if iterator == wsi.latestIndex { + break + } + } + return fmt.Errorf("attempting to fill a bucket that does not exist") +} + +func (wsi *windowSeriesWindowOnlyImpl[Data, Bucket]) Count() (some int, none int) { + some = 0 + none = 0 + for _, v := range wsi.data { + if utilities.IsSome[Data](v.Second) { + some++ + } else { + none++ + } + } + return +} + +func (wsi *windowSeriesWindowOnlyImpl[Data, Bucket]) Complete() bool { + for _, v := range wsi.data { + if utilities.IsNone(v.Second) { + return false + } + } + return true +} + +func (wsi *windowSeriesWindowOnlyImpl[Data, Bucket]) nextIndex(currentIndex int) int { + return (currentIndex + 1) % wsi.windowSize +} + +func (wsi *windowSeriesWindowOnlyImpl[Data, Bucket]) previousIndex(currentIndex int) int { + nextIndex := currentIndex - 1 + if nextIndex < 0 { + nextIndex += wsi.windowSize + } + return nextIndex +} + +func (wsi *windowSeriesWindowOnlyImpl[Data, Bucket]) toArray() []utilities.Optional[Data] { + result := make([]utilities.Optional[Data], wsi.windowSize) + + iterator := wsi.latestIndex + parallelIterator := 0 + for { + result[parallelIterator] = wsi.data[iterator].Second + iterator = wsi.previousIndex(iterator) + parallelIterator++ + if iterator == wsi.latestIndex { + break + } + } + return result +} + +func (wsi *windowSeriesWindowOnlyImpl[Data, Bucket]) GetValues() []utilities.Optional[Data] { + return wsi.toArray() +} + +func (wsi *windowSeriesWindowOnlyImpl[Data, Bucket]) GetType() WindowSeriesDuration { + return WindowOnly +} + +func (wsi *windowSeriesWindowOnlyImpl[Data, Bucket]) ForEach(eacher func(b Bucket, d *utilities.Optional[Data])) { + for _, v := range wsi.data { + eacher(v.First, &v.Second) + } +} + +func (wsi *windowSeriesWindowOnlyImpl[Data, Bucket]) String() string { + result := fmt.Sprintf("Window series (window (%d) only, latest index: %v): ", wsi.windowSize, wsi.latestIndex) + for _, v := range wsi.data { + valueString := "None" + if utilities.IsSome[Data](v.Second) { + valueString = fmt.Sprintf("%v", utilities.GetSome[Data](v.Second)) + } + result += fmt.Sprintf("%v: %v; ", v.First, valueString) + } + return result +} + +func newWindowSeriesWindowOnlyImpl[Data any, Bucket constraints.Ordered]( + windowSize int, +) *windowSeriesWindowOnlyImpl[Data, Bucket] { + result := windowSeriesWindowOnlyImpl[Data, Bucket]{windowSize: windowSize, latestIndex: 0, empty: true} + + result.data = make([]utilities.Pair[Bucket, utilities.Optional[Data]], windowSize) + + return &result +} + +/* + * End of WindowSeries interface methods. + */ + +type windowSeriesForeverImpl[Data any, Bucket constraints.Ordered] struct { + data []utilities.Pair[Bucket, utilities.Optional[Data]] + empty bool +} + +func (wsi *windowSeriesForeverImpl[Data, Bucket]) Reserve(b Bucket) error { + if !wsi.empty && b <= wsi.data[len(wsi.data)-1].First { + return fmt.Errorf("reserving must be monotonically increasing") + } + + wsi.empty = false + wsi.data = append(wsi.data, utilities.Pair[Bucket, utilities.Optional[Data]]{First: b, Second: utilities.None[Data]()}) + return nil +} + +func (wsi *windowSeriesForeverImpl[Data, Bucket]) Fill(b Bucket, d Data) error { + for i := range wsi.data { + if wsi.data[i].First == b { + wsi.data[i].Second = utilities.Some[Data](d) + return nil + } + } + return fmt.Errorf("attempting to fill a bucket that does not exist") +} + +func (wsi *windowSeriesForeverImpl[Data, Bucket]) GetValues() []utilities.Optional[Data] { + result := make([]utilities.Optional[Data], len(wsi.data)) + + for i, v := range utilities.Reverse(wsi.data) { + result[i] = v.Second + } + + return result +} + +func (wsi *windowSeriesForeverImpl[Data, Bucket]) Count() (some int, none int) { + some = 0 + none = 0 + for _, v := range wsi.data { + if utilities.IsSome[Data](v.Second) { + some++ + } else { + none++ + } + } + return +} + +func (wsi *windowSeriesForeverImpl[Data, Bucket]) Complete() bool { + for _, v := range wsi.data { + if utilities.IsNone(v.Second) { + return false + } + } + return true +} + +func (wsi *windowSeriesForeverImpl[Data, Bucket]) GetType() WindowSeriesDuration { + return Forever +} + +func newWindowSeriesForeverImpl[Data any, Bucket constraints.Ordered]() *windowSeriesForeverImpl[Data, Bucket] { + result := windowSeriesForeverImpl[Data, Bucket]{empty: true} + + result.data = nil + + return &result +} + +func (wsi *windowSeriesForeverImpl[Data, Bucket]) ForEach(eacher func(b Bucket, d *utilities.Optional[Data])) { + for _, v := range wsi.data { + eacher(v.First, &v.Second) + } +} + +func (wsi *windowSeriesForeverImpl[Data, Bucket]) String() string { + result := "Window series (forever): " + for _, v := range wsi.data { + valueString := "None" + if utilities.IsSome[Data](v.Second) { + valueString = fmt.Sprintf("%v", utilities.GetSome[Data](v.Second)) + } + result += fmt.Sprintf("%v: %v; ", v.First, valueString) + } + return result +} + +/* + * End of WindowSeries interface methods. + */ + +func NewWindowSeries[Data any, Bucket constraints.Ordered](tipe WindowSeriesDuration, windowSize int) WindowSeries[Data, Bucket] { + if tipe == WindowOnly { + return newWindowSeriesWindowOnlyImpl[Data, Bucket](windowSize) + } else if tipe == Forever { + return newWindowSeriesForeverImpl[Data, Bucket]() + } + panic("") +} diff --git a/series/series_test.go b/series/series_test.go new file mode 100644 index 0000000..5d2ab57 --- /dev/null +++ b/series/series_test.go @@ -0,0 +1,846 @@ +/* + * This file is part of Go Responsiveness. + * + * Go Responsiveness is free software: you can redistribute it and/or modify it under + * the terms of the GNU General Public License as published by the Free Software Foundation, + * either version 2 of the License, or (at your option) any later version. + * Go Responsiveness is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A + * PARTICULAR PURPOSE. See the GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with Go Responsiveness. If not, see <https://www.gnu.org/licenses/>. + */ +package series + +import ( + "reflect" + "testing" + + "github.com/network-quality/goresponsiveness/utilities" +) + +func TestNextIndex(t *testing.T) { + wsi := newWindowSeriesWindowOnlyImpl[int, int](4) + + idx := wsi.nextIndex(wsi.latestIndex) + if idx != 1 { + t.Fatalf("nextIndex is wrong (1)") + } + wsi.latestIndex = idx + + idx = wsi.nextIndex(wsi.latestIndex) + if idx != 2 { + t.Fatalf("nextIndex is wrong (2)") + } + wsi.latestIndex = idx + + idx = wsi.nextIndex(wsi.latestIndex) + if idx != 3 { + t.Fatalf("nextIndex is wrong (3)") + } + wsi.latestIndex = idx + + idx = wsi.nextIndex(wsi.latestIndex) + if idx != 0 { + t.Fatalf("nextIndex is wrong (0)") + } + wsi.latestIndex = idx + + idx = wsi.nextIndex(wsi.latestIndex) + if idx != 1 { + t.Fatalf("nextIndex is wrong (1)") + } + wsi.latestIndex = idx +} + +func TestSimpleWindowComplete(t *testing.T) { + wsi := newWindowSeriesWindowOnlyImpl[int, int](4) + if wsi.Complete() { + t.Fatalf("Window should not be complete.") + } + wsfImpl := newWindowSeriesForeverImpl[int, int]() + wsfImpl.Reserve(1) + if wsfImpl.Complete() { + t.Fatalf("Window should not be complete.") + } +} + +func TestSimpleReserve(t *testing.T) { + wswoImpl := newWindowSeriesWindowOnlyImpl[int, int](4) + result := wswoImpl.Reserve(0) + if result != nil { + t.Fatalf("Reserving 1 should be a-ok!") + } + wsfImpl := newWindowSeriesForeverImpl[int, int]() + result = wsfImpl.Reserve(0) + if result != nil { + t.Fatalf("Reserving 1 should be a-ok!") + } +} + +func Test_ForeverValues(test *testing.T) { + series := newWindowSeriesForeverImpl[float64, int]() + shouldMatch := make([]utilities.Optional[float64], 0) + previous := float64(1.0) + for i := range utilities.Iota(1, 81) { + previous *= 1.059 + series.Reserve(i) + series.Fill(i, float64(previous)) + shouldMatch = append(shouldMatch, utilities.Some[float64](previous)) + } + + if !reflect.DeepEqual(utilities.Reverse(shouldMatch), series.GetValues()) { + test.Fatalf("Values() on infinite mathematical series does not work.") + } +} + +func Test_WindowOnlySequentialIncreasesAlwaysLessThan(test *testing.T) { + series := newWindowSeriesWindowOnlyImpl[float64, int](10) + previous := float64(1.0) + for i := range utilities.Iota(1, 11) { + previous *= 1.5 + series.Reserve(i) + series.Fill(i, float64(previous)) + } + if complete, islt, maxSeqIncrease := AllSequentialIncreasesLessThan[float64, int](series, + 100); !complete || maxSeqIncrease != 50.0 || !islt { + test.Fatalf( + "(Window Only) Sequential increases are not always less than 100 (%v, %v, %f ).", + complete, islt, maxSeqIncrease, + ) + } +} + +func Test_WindowOnlyTooFewInstantsSequentialIncreasesLessThanAlwaysFalse(test *testing.T) { + series := newWindowSeriesWindowOnlyImpl[float64, int](500) + series.Reserve(1) + series.Fill(1, 0.0) + if complete, islt, _ := AllSequentialIncreasesLessThan[float64, int](series, 0.0); complete || islt { + test.Fatalf( + "(Window Only) 0 elements in a series should always yield false when asking if sequential increases are less than a value.", + ) + } +} + +func Test_Forever_Complete(test *testing.T) { + series := newWindowSeriesForeverImpl[int, int]() + series.Reserve(1) + series.Fill(1, 10) + if !series.Complete() { + test.Fatalf("(infinite) Series with one element and a window size of 1 is not complete.") + } +} + +func Test_Forever_CompleteN(test *testing.T) { + series := newWindowSeriesWindowOnlyImpl[float64, int](10) + previous := float64(1.0) + for i := range utilities.Iota(1, 11) { + previous *= 1.5 + series.Reserve(i) + series.Fill(i, float64(previous)) + } + if !series.Complete() { + test.Fatalf("(infinite) Series with one element and a window size of 2 is complete.") + } +} + +func Test_Forever_degenerate_percentile_too_high(test *testing.T) { + series := newWindowSeriesForeverImpl[int, int]() + if complete, result := Percentile[int, int](series, 101); !complete || result != 0.0 { + test.Fatalf("(infinite) Series percentile of 101 failed.") + } +} + +func Test_Forever_degenerate_percentile_too_low(test *testing.T) { + series := newWindowSeriesForeverImpl[int, int]() + if complete, result := Percentile[int, int](series, -1); !complete || result != 0.0 { + test.Fatalf("(infinite) Series percentile of -1 failed.") + } +} + +/////////// + +func Test_Forever90_percentile(test *testing.T) { + var expected int = 10 + series := newWindowSeriesForeverImpl[int, int]() + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + series.Reserve(6) + series.Reserve(7) + series.Reserve(8) + series.Reserve(9) + series.Reserve(10) + + series.Fill(10, 10) + series.Fill(9, 9) + series.Fill(8, 8) + series.Fill(7, 7) + series.Fill(6, 6) + series.Fill(5, 5) + series.Fill(4, 4) + series.Fill(3, 3) + series.Fill(2, 2) + series.Fill(1, 1) + + if complete, result := Percentile[int, int](series, 90); !complete || result != expected { + test.Fatalf( + "Series 90th percentile of 0 ... 10 failed: (Complete: %v) Expected %v got %v.", complete, expected, result) + } +} + +func Test_Forever90_WindowOnly_percentile(test *testing.T) { + var expected int = 10 + series := newWindowSeriesForeverImpl[int, int]() + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + series.Reserve(6) + series.Reserve(7) + series.Reserve(8) + series.Reserve(9) + series.Reserve(10) + + series.Fill(10, 10) + series.Fill(9, 9) + series.Fill(8, 8) + series.Fill(7, 7) + series.Fill(6, 6) + series.Fill(5, 5) + series.Fill(4, 4) + series.Fill(3, 3) + series.Fill(2, 2) + series.Fill(1, 1) + + if complete, result := Percentile[int, int](series, 90); !complete || result != expected { + test.Fatalf( + "Series 90th percentile of 0 ... 10 failed: (Complete: %v) Expected %v got %v.", complete, expected, result) + } +} + +func Test_Forever90_percentile_reversed(test *testing.T) { + var expected int = 10 + series := newWindowSeriesForeverImpl[int, int]() + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + series.Reserve(6) + series.Reserve(7) + series.Reserve(8) + series.Reserve(9) + series.Reserve(10) + + series.Fill(10, 1) + series.Fill(9, 2) + series.Fill(8, 3) + series.Fill(7, 4) + series.Fill(6, 5) + series.Fill(5, 6) + series.Fill(4, 7) + series.Fill(3, 8) + series.Fill(2, 9) + series.Fill(1, 10) + + if complete, result := Percentile[int, int](series, 90); !complete || result != expected { + test.Fatalf( + "Series 90th percentile of 0 ... 10 failed: (Complete: %v) Expected %v got %v.", complete, expected, result) + } +} + +func Test_Forever50_percentile_jumbled(test *testing.T) { + var expected int64 = 15 + series := newWindowSeriesForeverImpl[int64, int]() + + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + series.Reserve(6) + series.Reserve(7) + series.Reserve(8) + series.Reserve(9) + series.Reserve(10) + + series.Fill(1, 7) + series.Fill(2, 2) + series.Fill(3, 15) + series.Fill(4, 27) + series.Fill(5, 5) + series.Fill(6, 52) + series.Fill(7, 18) + series.Fill(8, 23) + series.Fill(9, 11) + series.Fill(10, 12) + + if complete, result := Percentile[int64, int](series, 50); !complete || result != expected { + test.Fatalf( + "Series 50 percentile of a jumble of numbers failed: (Complete: %v) Expected %v got %v.", complete, expected, result) + } +} + +func Test_Forever90_partial_percentile(test *testing.T) { + var expected int = 10 + series := newWindowSeriesForeverImpl[int, int]() + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + series.Reserve(6) + series.Reserve(7) + series.Reserve(8) + series.Reserve(9) + series.Reserve(10) + + series.Fill(10, 10) + series.Fill(9, 9) + series.Fill(8, 8) + series.Fill(7, 7) + series.Fill(6, 6) + series.Fill(5, 5) + series.Fill(4, 4) + series.Fill(3, 3) + series.Fill(2, 2) + series.Fill(1, 1) + + if complete, result := Percentile[int, int](series, 90); !complete || result != expected { + test.Fatalf( + "Series 90th percentile of 0 ... 10 failed: (Complete: %v) Expected %v got %v.", complete, expected, result) + } +} + +func Test_Forever90_partial_percentile_reversed(test *testing.T) { + var expected int = 10 + series := newWindowSeriesForeverImpl[int, int]() + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + series.Reserve(6) + series.Reserve(7) + series.Reserve(8) + series.Reserve(9) + series.Reserve(10) + + series.Fill(10, 1) + series.Fill(9, 2) + series.Fill(8, 3) + series.Fill(7, 4) + series.Fill(6, 5) + series.Fill(5, 6) + series.Fill(4, 7) + series.Fill(3, 8) + series.Fill(2, 9) + series.Fill(1, 10) + + if complete, result := Percentile[int, int](series, 90); !complete || result != expected { + test.Fatalf( + "Series 90th percentile of 0 ... 10 failed: (Complete: %v) Expected %v got %v.", complete, expected, result) + } +} + +func Test_Forever50_partial_percentile_jumbled(test *testing.T) { + var expected int64 = 15 + series := newWindowSeriesForeverImpl[int64, int]() + + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + series.Reserve(6) + series.Reserve(7) + series.Reserve(8) + series.Reserve(9) + series.Reserve(10) + + series.Fill(1, 7) + series.Fill(2, 2) + series.Fill(3, 15) + series.Fill(4, 27) + series.Fill(5, 5) + series.Fill(6, 52) + series.Fill(7, 18) + series.Fill(8, 23) + series.Fill(9, 11) + series.Fill(10, 12) + + if complete, result := Percentile[int64, int](series, 50); !complete || result != expected { + test.Fatalf( + "Series 50 percentile of a jumble of numbers failed: (Complete: %v) Expected %v got %v.", complete, expected, result) + } +} + +/////////////////////// + +func Test_WindowOnlySequentialIncreasesAlwaysLessThanWithWraparound(test *testing.T) { + series := newWindowSeriesWindowOnlyImpl[float64, int](20) + previous := float64(1.0) + for i := range utilities.Iota(1, 21) { + previous *= 1.15 + series.Reserve(i) + series.Fill(1, float64(previous)) + } + + // All those measurements should be ejected by the following + // loop! + for i := range utilities.Iota(1, 21) { + previous *= 1.10 + series.Reserve(i + 20) + series.Fill(i+20, float64(previous)) + } + + if complete, islt, maxSeqIncrease := AllSequentialIncreasesLessThan[float64, int](series, + 11.0); !complete || !islt || !utilities.ApproximatelyEqual(maxSeqIncrease, 10, 0.1) { + test.Fatalf( + "Sequential increases are not always less than 11.0 in wraparound situation (%f v 11.0).", + maxSeqIncrease, + ) + } +} + +func Test_WindowOnlySequentialIncreasesAlwaysLessThanWithWraparoundInverse(test *testing.T) { + series := newWindowSeriesWindowOnlyImpl[float64, int](20) + previous := float64(1.0) + i := 0 + for i = range utilities.Iota(1, 21) { + previous *= 1.15 + series.Reserve(i) + series.Fill(i, float64(previous)) + } + + // *Not* all those measurements should be ejected by the following + // loop! + for j := range utilities.Iota(1, 16) { + previous *= 1.10 + series.Reserve(i + j) + series.Fill(i+j, float64(previous)) + } + + if complete, islt, maxSeqIncrease := AllSequentialIncreasesLessThan[float64, int](series, 11.0); complete == false || islt { + test.Fatalf( + "Sequential increases are (unexpectedly) always less than 11.0 in wraparound situation: %f v 11.0.", + maxSeqIncrease, + ) + } +} + +func Test_WindowOnlyStandardDeviationIncompleteCalculation(test *testing.T) { + expected := 2.93 + series := newWindowSeriesWindowOnlyImpl[float64, int](6) + // 5.7, 1.0, 8.6, 7.4, 2.2 + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + + series.Fill(1, 5.7) + series.Fill(2, 1.0) + series.Fill(3, 8.6) + series.Fill(4, 7.4) + series.Fill(5, 2.2) + + if complete, sd := SeriesStandardDeviation[float64, int](series); complete != false || + !utilities.ApproximatelyEqual(sd, expected, 0.01) { + test.Fatalf("Standard deviation max calculation failed: Expected: %v; Actual: %v.", expected, sd) + } else { + test.Logf("Standard deviation calculation result: %v", sd) + } +} + +func Test_WindowOnlyStandardDeviationCalculation(test *testing.T) { + expected := 2.93 + series := newWindowSeriesWindowOnlyImpl[float64, int](5) + // 5.7, 1.0, 8.6, 7.4, 2.2 + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + series.Reserve(6) + series.Reserve(7) + series.Reserve(8) + series.Reserve(9) + series.Reserve(10) + series.Reserve(11) + series.Reserve(12) + series.Reserve(13) + + series.Fill(1, 5.7) + series.Fill(2, 5.7) + series.Fill(3, 5.7) + series.Fill(4, 5.7) + series.Fill(5, 5.7) + series.Fill(6, 5.7) + series.Fill(7, 5.7) + series.Fill(8, 5.7) + series.Fill(9, 5.7) + series.Fill(10, 1.0) + series.Fill(11, 8.6) + series.Fill(12, 7.4) + series.Fill(13, 2.2) + + if complete, sd := SeriesStandardDeviation[float64, int](series); complete != true || + !utilities.ApproximatelyEqual(sd, expected, 0.01) { + test.Fatalf("Standard deviation max calculation failed: Expected: %v; Actual: %v.", expected, sd) + } +} + +func Test_WindowOnlyStandardDeviationCalculation2(test *testing.T) { + expected := 1.41 + series := newWindowSeriesWindowOnlyImpl[float64, int](5) + + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + + series.Fill(1, 8) + series.Fill(2, 9) + series.Fill(3, 10) + series.Fill(4, 11) + series.Fill(5, 12) + + if _, sd := SeriesStandardDeviation[float64, int](series); !utilities.ApproximatelyEqual(sd, expected, 0.01) { + test.Fatalf("Standard deviation max calculation failed: Expected: %v; Actual: %v.", expected, sd) + } else { + test.Logf("Standard deviation calculation result: %v", sd) + } +} + +func Test_WindowOnlyRotatingValues(test *testing.T) { + series := newWindowSeriesWindowOnlyImpl[int, int](5) + + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + + series.Reserve(6) + series.Reserve(7) + + series.Fill(1, 1) + series.Fill(2, 2) + series.Fill(3, 3) + series.Fill(4, 4) + series.Fill(5, 5) + + series.Fill(6, 6) + series.Fill(7, 7) + + actual := utilities.Fmap(series.GetValues(), func(i utilities.Optional[int]) int { + return utilities.GetSome[int](i) + }) + if !reflect.DeepEqual([]int{7, 6, 5, 4, 3}, actual) { + test.Fatalf("Adding values does not properly erase earlier values.") + } +} + +func Test_WindowOnly_degenerate_percentile_too_high(test *testing.T) { + series := newWindowSeriesWindowOnlyImpl[int, int](21) + if complete, p := Percentile[int, int](series, 101); complete != false || p != 0 { + test.Fatalf("Series percentile of 101 failed.") + } +} + +func Test_WindowOnly_degenerate_percentile_too_low(test *testing.T) { + series := newWindowSeriesWindowOnlyImpl[int, int](21) + if complete, p := Percentile[int, int](series, -1); complete != false || p != 0 { + test.Fatalf("Series percentile of -1 failed.") + } +} + +func Test_WindowOnly90_percentile(test *testing.T) { + var expected int = 10 + series := newWindowSeriesWindowOnlyImpl[int, int](10) + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + series.Reserve(6) + series.Reserve(7) + series.Reserve(8) + series.Reserve(9) + series.Reserve(10) + + series.Fill(10, 10) + series.Fill(9, 9) + series.Fill(8, 8) + series.Fill(7, 7) + series.Fill(6, 6) + series.Fill(5, 5) + series.Fill(4, 4) + series.Fill(3, 3) + series.Fill(2, 2) + series.Fill(1, 1) + + if complete, result := Percentile[int, int](series, 90); !complete || result != expected { + test.Fatalf( + "Series 90th percentile of 0 ... 10 failed: (Complete: %v) Expected %v got %v.", complete, expected, result) + } +} + +func Test_WindowOnly90_percentile_reversed(test *testing.T) { + var expected int = 10 + series := newWindowSeriesWindowOnlyImpl[int, int](10) + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + series.Reserve(6) + series.Reserve(7) + series.Reserve(8) + series.Reserve(9) + series.Reserve(10) + + series.Fill(10, 1) + series.Fill(9, 2) + series.Fill(8, 3) + series.Fill(7, 4) + series.Fill(6, 5) + series.Fill(5, 6) + series.Fill(4, 7) + series.Fill(3, 8) + series.Fill(2, 9) + series.Fill(1, 10) + + if complete, result := Percentile[int, int](series, 90); !complete || result != expected { + test.Fatalf( + "Series 90th percentile of 0 ... 10 failed: (Complete: %v) Expected %v got %v.", complete, expected, result) + } +} + +func Test_WindowOnly50_percentile_jumbled(test *testing.T) { + var expected int64 = 15 + series := newWindowSeriesWindowOnlyImpl[int64, int](10) + + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + series.Reserve(6) + series.Reserve(7) + series.Reserve(8) + series.Reserve(9) + series.Reserve(10) + + series.Fill(1, 7) + series.Fill(2, 2) + series.Fill(3, 15) + series.Fill(4, 27) + series.Fill(5, 5) + series.Fill(6, 52) + series.Fill(7, 18) + series.Fill(8, 23) + series.Fill(9, 11) + series.Fill(10, 12) + + if complete, result := Percentile[int64, int](series, 50); !complete || result != expected { + test.Fatalf( + "Series 50 percentile of a jumble of numbers failed: (Complete: %v) Expected %v got %v.", complete, expected, result) + } +} + +func Test_WindowOnly90_partial_percentile(test *testing.T) { + var expected int = 10 + series := newWindowSeriesWindowOnlyImpl[int, int](20) + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + series.Reserve(6) + series.Reserve(7) + series.Reserve(8) + series.Reserve(9) + series.Reserve(10) + + series.Fill(10, 10) + series.Fill(9, 9) + series.Fill(8, 8) + series.Fill(7, 7) + series.Fill(6, 6) + series.Fill(5, 5) + series.Fill(4, 4) + series.Fill(3, 3) + series.Fill(2, 2) + series.Fill(1, 1) + + if complete, result := Percentile[int, int](series, 90); complete != false || result != expected { + test.Fatalf( + "Series 90th percentile of 0 ... 10 failed: (Complete: %v) Expected %v got %v.", complete, expected, result) + } +} + +func Test_WindowOnly90_partial_percentile_reversed(test *testing.T) { + var expected int = 10 + series := newWindowSeriesWindowOnlyImpl[int, int](20) + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + series.Reserve(6) + series.Reserve(7) + series.Reserve(8) + series.Reserve(9) + series.Reserve(10) + + series.Fill(10, 1) + series.Fill(9, 2) + series.Fill(8, 3) + series.Fill(7, 4) + series.Fill(6, 5) + series.Fill(5, 6) + series.Fill(4, 7) + series.Fill(3, 8) + series.Fill(2, 9) + series.Fill(1, 10) + + if complete, result := Percentile[int, int](series, 90); complete != false || result != expected { + test.Fatalf( + "Series 90th percentile of 0 ... 10 failed: (Complete: %v) Expected %v got %v.", complete, expected, result) + } +} + +func Test_WindowOnly50_partial_percentile_jumbled(test *testing.T) { + var expected int64 = 15 + series := newWindowSeriesWindowOnlyImpl[int64, int](20) + + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + series.Reserve(6) + series.Reserve(7) + series.Reserve(8) + series.Reserve(9) + series.Reserve(10) + + series.Fill(1, 7) + series.Fill(2, 2) + series.Fill(3, 15) + series.Fill(4, 27) + series.Fill(5, 5) + series.Fill(6, 52) + series.Fill(7, 18) + series.Fill(8, 23) + series.Fill(9, 11) + series.Fill(10, 12) + + if complete, result := Percentile[int64, int](series, 50); complete != false || result != expected { + test.Fatalf( + "Series 50 percentile of a jumble of numbers failed: (Complete: %v) Expected %v got %v.", complete, expected, result) + } +} + +/* + +func Test_WindowOnlyDoubleSidedTrimmedMean_jumbled(test *testing.T) { + expected := 8 + series := newWindowSeriesWindowOnlyImpl[int64, int](10) + series.AddElement(7) + series.AddElement(2) + series.AddElement(15) + series.AddElement(27) + series.AddElement(5) + series.AddElement(5) + series.AddElement(52) + series.AddElement(18) + series.AddElement(23) + series.AddElement(11) + series.AddElement(12) + + trimmed := series.DoubleSidedTrim(10) + + if trimmed.Len() != expected { + test.Fatalf( + "WindowOnly series is not of the proper size. Expected %v and got %v", + expected, + trimmed.Len(), + ) + } + + prev := int64(0) + for _, v := range trimmed.Values() { + if !(prev <= v) { + test.Fatalf("Not sorted: %v is not less than or equal to %v\n", prev, v) + } + prev = v + } +} + +func Test_WindowOnlyAverage(test *testing.T) { + expected := 1.0082230220488836e+08 + series := newWindowSeriesWindowOnlyImpl[float64, int](4) + series.AddElement(9.94747772516195e+07) + series.AddElement(9.991286984703423e+07) + series.AddElement(1.0285437111086299e+08) + series.AddElement(1.0104719061003672e+08) + if average := series.CalculateAverage(); !utilities.ApproximatelyEqual(average, 0.01, expected) { + test.Fatalf( + "Expected: %v; Actual: %v.", average, expected, + ) + } +} +*/ + +func Test_ForeverStandardDeviationIncompleteCalculation(test *testing.T) { + foreverExpected := 2.90 + series := newWindowSeriesForeverImpl[float64, int]() + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + series.Reserve(6) + + series.Fill(1, 5.7) + series.Fill(2, 1.0) + series.Fill(3, 8.6) + series.Fill(4, 7.4) + series.Fill(5, 2.2) + series.Fill(6, 8.0) + + if complete, sd := SeriesStandardDeviation[float64, int](series); !complete || + !utilities.ApproximatelyEqual(sd, foreverExpected, 0.01) { + test.Fatalf("Standard deviation max calculation failed: Expected: %v; Actual: %v.", foreverExpected, sd) + } +} + +func Test_ForeverStandardDeviationCalculation2(test *testing.T) { + expected := 1.41 + series := newWindowSeriesForeverImpl[float64, int]() + + series.Reserve(1) + series.Reserve(2) + series.Reserve(3) + series.Reserve(4) + series.Reserve(5) + + series.Fill(1, 8) + series.Fill(2, 9) + series.Fill(3, 10) + series.Fill(4, 11) + series.Fill(5, 12) + + if _, sd := SeriesStandardDeviation[float64, int](series); !utilities.ApproximatelyEqual(sd, expected, 0.01) { + test.Fatalf("Standard deviation(series) max calculation(series) failed: Expected: %v; Actual: %v.", expected, sd) + } +} diff --git a/series/statistics.go b/series/statistics.go new file mode 100644 index 0000000..2742aa7 --- /dev/null +++ b/series/statistics.go @@ -0,0 +1,74 @@ +package series + +import ( + "github.com/network-quality/goresponsiveness/utilities" + "golang.org/x/exp/constraints" +) + +func SeriesStandardDeviation[Data utilities.Number, Bucket constraints.Ordered](s WindowSeries[Data, Bucket]) (bool, float64) { + complete := s.Complete() + + inputValues := s.GetValues() + + actualValues := utilities.Filter(inputValues, func(d utilities.Optional[Data]) bool { + return utilities.IsSome[Data](d) + }) + values := utilities.Fmap(actualValues, func(d utilities.Optional[Data]) Data { return utilities.GetSome[Data](d) }) + + return complete, utilities.CalculateStandardDeviation[Data](values) +} + +func Percentile[Data utilities.Number, Bucket constraints.Ordered](s WindowSeries[Data, Bucket], p int) (bool, Data) { + complete := s.Complete() + + inputValues := s.GetValues() + + actualValues := utilities.Filter(inputValues, func(d utilities.Optional[Data]) bool { + return utilities.IsSome[Data](d) + }) + values := utilities.Fmap(actualValues, func(d utilities.Optional[Data]) Data { return utilities.GetSome[Data](d) }) + + return complete, utilities.CalculatePercentile(values, p) +} + +func AllSequentialIncreasesLessThan[Data utilities.Number, Bucket constraints.Ordered](s WindowSeries[Data, Bucket], limit float64, +) (bool, bool, float64) { + complete := s.Complete() + + inputValues := s.GetValues() + + actualValues := utilities.Filter(utilities.Reverse(inputValues), func(d utilities.Optional[Data]) bool { + return utilities.IsSome[Data](d) + }) + values := utilities.Fmap(actualValues, func(d utilities.Optional[Data]) Data { return utilities.GetSome[Data](d) }) + + result, actualLimit := utilities.AllSequentialIncreasesLessThan(values, limit) + return complete, result, actualLimit +} + +func CalculateAverage[Data utilities.Number, Bucket constraints.Ordered](s WindowSeries[Data, Bucket]) (bool, float64) { + complete := s.Complete() + + inputValues := s.GetValues() + + actualValues := utilities.Filter(inputValues, func(d utilities.Optional[Data]) bool { + return utilities.IsSome[Data](d) + }) + values := utilities.Fmap(actualValues, func(d utilities.Optional[Data]) Data { return utilities.GetSome[Data](d) }) + + return complete, utilities.CalculateAverage(values) +} + +func TrimmedMean[Data utilities.Number, Bucket constraints.Ordered](s WindowSeries[Data, Bucket], trim int) (bool, float64, []Data) { + complete := s.Complete() + + inputValues := s.GetValues() + + actualValues := utilities.Filter(inputValues, func(d utilities.Optional[Data]) bool { + return utilities.IsSome[Data](d) + }) + values := utilities.Fmap(actualValues, func(d utilities.Optional[Data]) Data { return utilities.GetSome[Data](d) }) + + trimmedMean, trimmedElements := utilities.TrimmedMean(values, trim) + return complete, trimmedMean, trimmedElements +} |