summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ms/ms.go51
-rw-r--r--ms/ms_test.go80
-rw-r--r--stabilizer/rev3.go12
3 files changed, 120 insertions, 23 deletions
diff --git a/ms/ms.go b/ms/ms.go
index 76b4b0a..0a91e04 100644
--- a/ms/ms.go
+++ b/ms/ms.go
@@ -16,35 +16,48 @@ package ms
import (
"math"
+ "sort"
"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 {
+type MathematicalSeries[T constraints.Float | constraints.Integer] interface {
+ AddElement(T)
+ CalculateAverage() float64
+ AllSequentialIncreasesLessThan(float64) (bool, float64)
+ StandardDeviation() (bool, T)
+ IsNormallyDistributed() bool
+ Size() int
+ Values() []T
+ Percentile(int) T
+}
+
+type CappedMathematicalSeries[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]{
+func NewCappedMathematicalSeries[T constraints.Float | constraints.Integer](instants_count int) MathematicalSeries[T] {
+ return &CappedMathematicalSeries[T]{
elements: make([]T, instants_count),
elements_count: instants_count,
divisor: saturating.NewSaturatingInt(instants_count),
+ index: 0,
}
}
-func (ma *MathematicalSeries[T]) AddElement(measurement T) {
+func (ma *CappedMathematicalSeries[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 {
+func (ma *CappedMathematicalSeries[T]) CalculateAverage() float64 {
total := T(0)
for i := 0; i < ma.elements_count; i++ {
total += ma.elements[i]
@@ -52,7 +65,7 @@ func (ma *MathematicalSeries[T]) CalculateAverage() float64 {
return float64(total) / float64(ma.divisor.Value())
}
-func (ma *MathematicalSeries[T]) AllSequentialIncreasesLessThan(limit float64) (_ bool, maximumSequentialIncrease float64) {
+func (ma *CappedMathematicalSeries[T]) AllSequentialIncreasesLessThan(limit float64) (_ bool, maximumSequentialIncrease float64) {
// If we have not yet accumulated a complete set of intervals,
// this is false.
@@ -80,7 +93,7 @@ func (ma *MathematicalSeries[T]) AllSequentialIncreasesLessThan(limit float64) (
/*
* N.B.: Overflow is possible -- use at your discretion!
*/
-func (ma *MathematicalSeries[T]) StandardDeviation() (bool, T) {
+func (ma *CappedMathematicalSeries[T]) StandardDeviation() (bool, T) {
// If we have not yet accumulated a complete set of intervals,
// we are always false.
@@ -120,7 +133,7 @@ func (ma *MathematicalSeries[T]) StandardDeviation() (bool, T) {
return true, sd
}
-func (ma *MathematicalSeries[T]) IsNormallyDistributed() bool {
+func (ma *CappedMathematicalSeries[T]) IsNormallyDistributed() bool {
valid, stddev := ma.StandardDeviation()
// If there are not enough values in our series to generate a standard
// deviation, then we cannot do this calculation either.
@@ -139,10 +152,28 @@ func (ma *MathematicalSeries[T]) IsNormallyDistributed() bool {
return within/float64(ma.divisor.Value()) >= 0.68
}
-func (ma *MathematicalSeries[T]) Values() []T {
+func (ma *CappedMathematicalSeries[T]) Values() []T {
return ma.elements
}
-func (ma *MathematicalSeries[T]) Size() int {
+func (ma *CappedMathematicalSeries[T]) Size() int {
return len(ma.elements)
}
+
+func (ma *CappedMathematicalSeries[T]) Percentile(p int) (result T) {
+ result = T(0)
+ if p < 0 || p > 100 {
+ return
+ }
+
+ // Because we need to sort the list to perform the percentile calculation,
+ // we have to make a copy of the list so that we don't disturb
+ // the time-relative ordering of the elements.
+
+ kopy := make([]T, len(ma.elements))
+ copy(kopy, ma.elements)
+ sort.Slice(kopy, func(l int, r int) bool { return kopy[l] < kopy[r] })
+ pindex := int64((float64(p) / float64(100)) * float64(ma.elements_count))
+ result = kopy[pindex]
+ return
+}
diff --git a/ms/ms_test.go b/ms/ms_test.go
index 6f1e807..988b647 100644
--- a/ms/ms_test.go
+++ b/ms/ms_test.go
@@ -8,7 +8,7 @@ import (
)
func Test_TooFewInstantsSequentialIncreasesLessThanAlwaysFalse(test *testing.T) {
- series := NewMathematicalSeries[float64](500)
+ series := NewCappedMathematicalSeries[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.")
@@ -16,7 +16,7 @@ func Test_TooFewInstantsSequentialIncreasesLessThanAlwaysFalse(test *testing.T)
}
func Test_SequentialIncreasesAlwaysLessThan(test *testing.T) {
- series := NewMathematicalSeries[float64](40)
+ series := NewCappedMathematicalSeries[float64](40)
previous := float64(1.0)
for _ = range utilities.Iota(1, 80) {
previous *= 1.059
@@ -28,7 +28,7 @@ func Test_SequentialIncreasesAlwaysLessThan(test *testing.T) {
}
func Test_SequentialIncreasesAlwaysLessThanWithWraparound(test *testing.T) {
- series := NewMathematicalSeries[float64](20)
+ series := NewCappedMathematicalSeries[float64](20)
previous := float64(1.0)
for range utilities.Iota(1, 20) {
previous *= 1.15
@@ -48,7 +48,7 @@ func Test_SequentialIncreasesAlwaysLessThanWithWraparound(test *testing.T) {
}
func Test_SequentialIncreasesAlwaysLessThanWithWraparoundInverse(test *testing.T) {
- series := NewMathematicalSeries[float64](20)
+ series := NewCappedMathematicalSeries[float64](20)
previous := float64(1.0)
for range utilities.Iota(1, 20) {
previous *= 1.15
@@ -68,7 +68,7 @@ func Test_SequentialIncreasesAlwaysLessThanWithWraparoundInverse(test *testing.T
}
func Test_StandardDeviationCalculation(test *testing.T) {
- series := NewMathematicalSeries[float64](5)
+ series := NewCappedMathematicalSeries[float64](5)
// 5.7, 1.0, 8.6, 7.4, 2.2
series.AddElement(5.7)
series.AddElement(1.0)
@@ -84,7 +84,7 @@ func Test_StandardDeviationCalculation(test *testing.T) {
}
func Test_RotatingValues(test *testing.T) {
- series := NewMathematicalSeries[int](5)
+ series := NewCappedMathematicalSeries[int](5)
series.AddElement(1)
series.AddElement(2)
@@ -100,7 +100,7 @@ func Test_RotatingValues(test *testing.T) {
}
}
func Test_Size(test *testing.T) {
- series := NewMathematicalSeries[int](5)
+ series := NewCappedMathematicalSeries[int](5)
series.AddElement(1)
series.AddElement(2)
@@ -115,3 +115,69 @@ func Test_Size(test *testing.T) {
test.Fatalf("Series size calculations failed.")
}
}
+
+func Test_degenerate_percentile_too_high(test *testing.T) {
+ series := NewCappedMathematicalSeries[int](21)
+ if series.Percentile(101) != 0 {
+ test.Fatalf("Series percentile of 101 failed.")
+ }
+}
+func Test_degenerate_percentile_too_low(test *testing.T) {
+ series := NewCappedMathematicalSeries[int](21)
+ if series.Percentile(-1) != 0 {
+ test.Fatalf("Series percentile of -1 failed.")
+ }
+}
+func Test_90_percentile(test *testing.T) {
+ series := NewCappedMathematicalSeries[int](10)
+ series.AddElement(10)
+ series.AddElement(9)
+ series.AddElement(8)
+ series.AddElement(7)
+ series.AddElement(6)
+ series.AddElement(5)
+ series.AddElement(4)
+ series.AddElement(3)
+ series.AddElement(2)
+ series.AddElement(1)
+
+ if series.Percentile(90) != 10 {
+ test.Fatalf("Series 90th percentile of 0 ... 10 failed: Expected 10 got %v.", series.Percentile(90))
+ }
+}
+
+func Test_90_percentile_reversed(test *testing.T) {
+ series := NewCappedMathematicalSeries[int64](10)
+ series.AddElement(1)
+ series.AddElement(2)
+ series.AddElement(3)
+ series.AddElement(4)
+ series.AddElement(5)
+ series.AddElement(6)
+ series.AddElement(7)
+ series.AddElement(8)
+ series.AddElement(9)
+ series.AddElement(10)
+
+ if series.Percentile(90) != 10 {
+ test.Fatalf("Series 90th percentile of 0 ... 10 failed: Expected 10 got %v.", series.Percentile(90))
+ }
+}
+
+func Test_50_percentile_jumbled(test *testing.T) {
+ series := NewCappedMathematicalSeries[int64](10)
+ series.AddElement(7)
+ series.AddElement(2)
+ series.AddElement(15)
+ series.AddElement(27)
+ series.AddElement(5)
+ series.AddElement(52)
+ series.AddElement(18)
+ series.AddElement(23)
+ series.AddElement(11)
+ series.AddElement(12)
+
+ if series.Percentile(50) != 15 {
+ test.Fatalf("Series 50 percentile of a jumble of numbers failed: Expected 15 got %v.", series.Percentile(50))
+ }
+}
diff --git a/stabilizer/rev3.go b/stabilizer/rev3.go
index 2e29626..79f5f27 100644
--- a/stabilizer/rev3.go
+++ b/stabilizer/rev3.go
@@ -11,8 +11,8 @@ import (
)
type DataPointStabilizer struct {
- instantaneousMeasurements *ms.MathematicalSeries[float64]
- movingAverages *ms.MathematicalSeries[float64]
+ instantaneousMeasurements ms.MathematicalSeries[float64]
+ movingAverages ms.MathematicalSeries[float64]
stabilityStandardDeviation float64
m sync.Mutex
dbgLevel debug.DebugLevel
@@ -30,8 +30,8 @@ type ThroughputStabilizer DataPointStabilizer
// moving averages of a measurement.
func NewProbeStabilizer(i int, k int, s float64, debugLevel debug.DebugLevel, debug *debug.DebugWithPrefix) ProbeStabilizer {
- return ProbeStabilizer{instantaneousMeasurements: ms.NewMathematicalSeries[float64](i),
- movingAverages: ms.NewMathematicalSeries[float64](k),
+ return ProbeStabilizer{instantaneousMeasurements: ms.NewCappedMathematicalSeries[float64](i),
+ movingAverages: ms.NewCappedMathematicalSeries[float64](k),
stabilityStandardDeviation: s,
dbgConfig: debug,
dbgLevel: debugLevel}
@@ -97,8 +97,8 @@ func (r3 *ProbeStabilizer) IsStable() bool {
}
func NewThroughputStabilizer(i int, k int, s float64, debugLevel debug.DebugLevel, debug *debug.DebugWithPrefix) ThroughputStabilizer {
- return ThroughputStabilizer{instantaneousMeasurements: ms.NewMathematicalSeries[float64](i),
- movingAverages: ms.NewMathematicalSeries[float64](k),
+ return ThroughputStabilizer{instantaneousMeasurements: ms.NewCappedMathematicalSeries[float64](i),
+ movingAverages: ms.NewCappedMathematicalSeries[float64](k),
stabilityStandardDeviation: s,
dbgConfig: debug,
dbgLevel: debugLevel}
generated by cgit v1.2.3 (git 2.51.0) at 2025-11-19 17:56:12 +0000