-
Notifications
You must be signed in to change notification settings - Fork 5.6k
/
algorithms.go
108 lines (88 loc) · 2.18 KB
/
algorithms.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
package quantile
import (
"math"
"sort"
"github.com/caio/go-tdigest"
)
type algorithm interface {
Add(value float64) error
Quantile(q float64) float64
}
func newTDigest(compression float64) (algorithm, error) {
return tdigest.New(tdigest.Compression(compression))
}
type exactAlgorithmR7 struct {
xs []float64
sorted bool
}
func newExactR7(_ float64) (algorithm, error) {
return &exactAlgorithmR7{xs: make([]float64, 0, 100), sorted: false}, nil
}
func (e *exactAlgorithmR7) Add(value float64) error {
e.xs = append(e.xs, value)
e.sorted = false
return nil
}
func (e *exactAlgorithmR7) Quantile(q float64) float64 {
size := len(e.xs)
// No information
if len(e.xs) == 0 {
return math.NaN()
}
// Sort the array if necessary
if !e.sorted {
sort.Float64s(e.xs)
e.sorted = true
}
// Get the quantile index and the fraction to the neighbor
// Hyndman & Fan; Sample Quantiles in Statistical Packages; The American Statistician vol 50; pp 361-365; 1996 -- R7
// Same as Excel and Numpy.
n := q * (float64(size) - 1)
i, gamma := math.Modf(n)
j := int(i)
if j < 0 {
return e.xs[0]
}
if j >= size {
return e.xs[size-1]
}
// Linear interpolation
return e.xs[j] + gamma*(e.xs[j+1]-e.xs[j])
}
type exactAlgorithmR8 struct {
xs []float64
sorted bool
}
func newExactR8(_ float64) (algorithm, error) {
return &exactAlgorithmR8{xs: make([]float64, 0, 100), sorted: false}, nil
}
func (e *exactAlgorithmR8) Add(value float64) error {
e.xs = append(e.xs, value)
e.sorted = false
return nil
}
func (e *exactAlgorithmR8) Quantile(q float64) float64 {
size := len(e.xs)
// No information
if size == 0 {
return math.NaN()
}
// Sort the array if necessary
if !e.sorted {
sort.Float64s(e.xs)
e.sorted = true
}
// Get the quantile index and the fraction to the neighbor
// Hyndman & Fan; Sample Quantiles in Statistical Packages; The American Statistician vol 50; pp 361-365; 1996 -- R8
n := q*(float64(size)+1.0/3.0) - (2.0 / 3.0) // Indices are zero-base here but one-based in the paper
i, gamma := math.Modf(n)
j := int(i)
if j < 0 {
return e.xs[0]
}
if j >= size {
return e.xs[size-1]
}
// Linear interpolation
return e.xs[j] + gamma*(e.xs[j+1]-e.xs[j])
}