diff options
| -rw-r--r-- | go.mod | 7 | ||||
| -rw-r--r-- | go.sum | 4 | ||||
| -rw-r--r-- | ma/ma.go | 76 | ||||
| -rw-r--r-- | ms/ms.go | 117 | ||||
| -rw-r--r-- | ms/ms_test.go | 83 | ||||
| -rw-r--r-- | utilities/utilities.go | 23 | ||||
| -rw-r--r-- | utilities/utilities_test.go | 13 |
7 files changed, 239 insertions, 84 deletions
@@ -4,7 +4,10 @@ go 1.18 require ( golang.org/x/net v0.0.0-20220225172249-27dd8689420f - golang.org/x/sys v0.0.0-20220728004956-3c1f35247d10 + golang.org/x/sys v0.1.0 ) -require golang.org/x/text v0.3.7 // indirect +require ( + golang.org/x/exp v0.0.0-20221031165847-c99f073a8326 + golang.org/x/text v0.3.7 // indirect +) @@ -1,6 +1,10 @@ +golang.org/x/exp v0.0.0-20221031165847-c99f073a8326 h1:QfTh0HpN6hlw6D3vu8DAwC8pBIwikq0AI1evdm+FksE= +golang.org/x/exp v0.0.0-20221031165847-c99f073a8326/go.mod h1:CxIveKay+FTh1D0yPZemJVgC/95VzuuOLq5Qi4xnoYc= golang.org/x/net v0.0.0-20220225172249-27dd8689420f h1:oA4XRj0qtSt8Yo1Zms0CUlsT3KG69V2UGQWPBxujDmc= golang.org/x/net v0.0.0-20220225172249-27dd8689420f/go.mod h1:CfG3xpIq0wQ8r1q4Su4UZFWDARRcnwPjda9FqA0JpMk= golang.org/x/sys v0.0.0-20220728004956-3c1f35247d10 h1:WIoqL4EROvwiPdUtaip4VcDdpZ4kha7wBWZrbVKCIZg= golang.org/x/sys v0.0.0-20220728004956-3c1f35247d10/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg= +golang.org/x/sys v0.1.0 h1:kunALQeHf1/185U1i0GOB/fy1IPRDDpuoOOqRReG57U= +golang.org/x/sys v0.1.0/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg= golang.org/x/text v0.3.7 h1:olpwvP2KacW1ZWvsR7uQhoyTYvKAupfQrRGBFM352Gk= golang.org/x/text v0.3.7/go.mod h1:u+2+/6zg+i71rQMx5EYifcz6MCKuco9NR6JIITiCfzQ= diff --git a/ma/ma.go b/ma/ma.go deleted file mode 100644 index 2d9749f..0000000 --- a/ma/ma.go +++ /dev/null @@ -1,76 +0,0 @@ -/* - * 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 ma - -import ( - "github.com/network-quality/goresponsiveness/saturating" - "github.com/network-quality/goresponsiveness/utilities" -) - -// Convert this to a Type Parameterized interface when they are available -// in Go (1.18). -type MovingAverage struct { - intervals int - instants []float64 - index int - divisor *saturating.SaturatingInt -} - -func NewMovingAverage(intervals int) *MovingAverage { - return &MovingAverage{ - instants: make([]float64, intervals), - intervals: intervals, - divisor: saturating.NewSaturatingInt(intervals), - } -} - -func (ma *MovingAverage) AddMeasurement(measurement float64) { - ma.instants[ma.index] = measurement - ma.divisor.Add(1) - // Invariant: ma.index always points to the oldest measurement - ma.index = (ma.index + 1) % ma.intervals -} - -func (ma *MovingAverage) CalculateAverage() float64 { - total := float64(0) - for i := 0; i < ma.intervals; i++ { - total += ma.instants[i] - } - return float64(total) / float64(ma.divisor.Value()) -} - -func (ma *MovingAverage) AllSequentialIncreasesLessThan(limit float64) bool { - - // If we have not yet accumulated a complete set of intervals, - // this is false. - if ma.divisor.Value() != ma.intervals { - return false - } - - // Invariant: ma.index always points to the oldest (see AddMeasurement - // above) - oldestIndex := ma.index - previous := ma.instants[oldestIndex] - for i := 1; i < ma.intervals; i++ { - currentIndex := (oldestIndex + i) % ma.intervals - current := ma.instants[currentIndex] - percentChange := utilities.SignedPercentDifference(current, previous) - previous = current - if percentChange > limit { - return false - } - } - return true -} diff --git a/ms/ms.go b/ms/ms.go new file mode 100644 index 0000000..8214025 --- /dev/null +++ b/ms/ms.go @@ -0,0 +1,117 @@ +/* + * 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 ms + +import ( + "math" + + "github.com/network-quality/goresponsiveness/saturating" + "github.com/network-quality/goresponsiveness/utilities" + "golang.org/x/exp/constraints" +) + +type MathematicalSeries[T constraints.Float | constraints.Integer] struct { + elements_count int + elements []T + index int + divisor *saturating.SaturatingInt +} + +func NewMathematicalSeries[T constraints.Float | constraints.Integer](instants_count int) *MathematicalSeries[T] { + return &MathematicalSeries[T]{ + elements: make([]T, instants_count), + elements_count: instants_count, + divisor: saturating.NewSaturatingInt(instants_count), + } +} + +func (ma *MathematicalSeries[T]) AddElement(measurement T) { + ma.elements[ma.index] = measurement + ma.divisor.Add(1) + // Invariant: ma.index always points to the oldest measurement + ma.index = (ma.index + 1) % ma.elements_count +} + +func (ma *MathematicalSeries[T]) CalculateAverage() float64 { + total := T(0) + for i := 0; i < ma.elements_count; i++ { + total += ma.elements[i] + } + return float64(total) / float64(ma.divisor.Value()) +} + +func (ma *MathematicalSeries[T]) AllSequentialIncreasesLessThan(limit float64) (_ bool, maximumSequentialIncrease float64) { + + // If we have not yet accumulated a complete set of intervals, + // this is false. + if ma.divisor.Value() != ma.elements_count { + return false, 0 + } + + // Invariant: ma.index always points to the oldest (see AddMeasurement + // above) + oldestIndex := ma.index + previous := ma.elements[oldestIndex] + maximumSequentialIncrease = 0 + for i := 1; i < ma.elements_count; i++ { + currentIndex := (oldestIndex + i) % ma.elements_count + current := ma.elements[currentIndex] + percentChange := utilities.SignedPercentDifference(current, previous) + previous = current + if percentChange > limit { + return false, percentChange + } + } + return true, maximumSequentialIncrease +} + +func (ma *MathematicalSeries[T]) StandardDeviationLessThan(limit T) (bool, T) { + + // If we have not yet accumulated a complete set of intervals, + // we are always false. + if ma.divisor.Value() != ma.elements_count { + return false, T(0) + } + + // From https://www.mathsisfun.com/data/standard-deviation-calculator.html + // Yes, for real! + + // Calculate the average of the numbers ... + average := ma.CalculateAverage() + + // Calculate the square of each of the elements' differences from the mean. + differences_squared := make([]float64, ma.elements_count) + for index, value := range ma.elements { + differences_squared[index] = math.Pow(float64(value-T(average)), 2) + } + + // The variance is the average of the squared differences. + // So, we need to ... + + // Accumulate all those squared differences. + sds := float64(0) + for _, dss := range differences_squared { + sds += dss + } + + // And then divide that total by the number of elements + variance := sds / float64(ma.divisor.Value()) + + // Finally, the standard deviation is the square root + // of the variance. + sd := T(math.Sqrt(variance)) + + return T(sd) < limit, sd +} diff --git a/ms/ms_test.go b/ms/ms_test.go new file mode 100644 index 0000000..0ba6da6 --- /dev/null +++ b/ms/ms_test.go @@ -0,0 +1,83 @@ +package ms + +import ( + "testing" + + "github.com/network-quality/goresponsiveness/utilities" +) + +func Test_TooFewInstantsSequentialIncreasesLessThanAlwaysFalse(test *testing.T) { + series := NewMathematicalSeries[float64](500) + series.AddElement(0.0) + if islt, _ := series.AllSequentialIncreasesLessThan(6.0); islt { + test.Fatalf("Too few instants should always yield false when asking if sequential increases are less than a value.") + } +} + +func Test_SequentialIncreasesAlwaysLessThan(test *testing.T) { + series := NewMathematicalSeries[float64](40) + previous := float64(1.0) + for _ = range utilities.Iota(1, 80) { + previous *= 1.059 + series.AddElement(float64(previous)) + } + if islt, maxSeqIncrease := series.AllSequentialIncreasesLessThan(6.0); !islt { + test.Fatalf("Sequential increases are not always less than 6.0 (%f).", maxSeqIncrease) + } +} + +func Test_SequentialIncreasesAlwaysLessThanWithWraparound(test *testing.T) { + series := NewMathematicalSeries[float64](20) + previous := float64(1.0) + for range utilities.Iota(1, 20) { + previous *= 1.15 + series.AddElement(float64(previous)) + } + + // All those measurements should be ejected by the following + // loop! + for range utilities.Iota(1, 20) { + previous *= 1.10 + series.AddElement(float64(previous)) + } + + if islt, maxSeqIncrease := series.AllSequentialIncreasesLessThan(11.0); !islt { + test.Fatalf("Sequential increases are not always less than 11.0 in wraparound situation (%f v 11.0).", maxSeqIncrease) + } +} + +func Test_SequentialIncreasesAlwaysLessThanWithWraparoundInverse(test *testing.T) { + series := NewMathematicalSeries[float64](20) + previous := float64(1.0) + for range utilities.Iota(1, 20) { + previous *= 1.15 + series.AddElement(float64(previous)) + } + + // *Not* all those measurements should be ejected by the following + // loop! + for range utilities.Iota(1, 15) { + previous *= 1.10 + series.AddElement(float64(previous)) + } + + if islt, maxSeqIncrease := series.AllSequentialIncreasesLessThan(11.0); islt { + test.Fatalf("Sequential increases are (unexpectedly) always less than 11.0 in wraparound situation: %f v 11.0.", maxSeqIncrease) + } +} + +func Test_StandardDeviationLessThan_Float(test *testing.T) { + series := NewMathematicalSeries[float64](5) + // 5.7, 1.0, 8.6, 7.4, 2.2 + series.AddElement(5.7) + series.AddElement(1.0) + series.AddElement(8.6) + series.AddElement(7.4) + series.AddElement(2.2) + + if islt, sd := series.StandardDeviationLessThan(2.94); !islt { + test.Fatalf("Standard deviation max calculation failed: %v.", sd) + } else { + test.Logf("Standard deviation calculation result: %v", sd) + } +} diff --git a/utilities/utilities.go b/utilities/utilities.go index 5143da5..01e2cdd 100644 --- a/utilities/utilities.go +++ b/utilities/utilities.go @@ -24,23 +24,34 @@ import ( "strings" "sync/atomic" "time" + + "golang.org/x/exp/constraints" ) +func Iota(low int, high int) (made []int) { + + made = make([]int, high-low) + for counter := low; counter < high; counter++ { + made[counter-low] = counter + } + return +} + func IsInterfaceNil(ifc interface{}) bool { return ifc == nil || (reflect.ValueOf(ifc).Kind() == reflect.Ptr && reflect.ValueOf(ifc).IsNil()) } -func SignedPercentDifference( - current float64, - previous float64, +func SignedPercentDifference[T constraints.Float | constraints.Integer]( + current T, + previous T, ) (difference float64) { //return ((current - previous) / (float64(current+previous) / 2.0)) * float64( //100, // ) - return ((current - previous) / previous) * float64( - 100, - ) + fCurrent := float64(current) + fPrevious := float64(previous) + return ((fCurrent - fPrevious) / fPrevious) * 100.0 } func AbsPercentDifference( diff --git a/utilities/utilities_test.go b/utilities/utilities_test.go index 107c2d2..3a84d76 100644 --- a/utilities/utilities_test.go +++ b/utilities/utilities_test.go @@ -14,11 +14,24 @@ package utilities import ( + "log" "sync" "testing" "time" ) +func TestIota(t *testing.T) { + r := Iota(6, 15) + + l := 6 + for _, vr := range r { + if vr != l { + log.Fatalf("Iota failed: expected %d, got %d\n", l, vr) + } + l++ + } +} + func TestReadAfterCloseOnBufferedChannel(t *testing.T) { communication := make(chan int, 100) |