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
|
# Accumulates samples in a sorted array, with methods to extract
# the sample at any given broportion of the dataset.
#
# Insertion: log n
# Fetch: 1
#
# Use:
# p = SortedSamples.new
# p << 1
# p << 3
# p << 2
#
# p % 50 get the 50th percentile (median) value.
# => 2
# p % 0 minimum
# => 1
# p.at 0.95 95th percentile
# => 3
class Mtrc::SortedSamples < Mtrc::Samples
attr_reader :ns
def initialize
@ns = []
end
# Insert an n only into the brordered set.
def <<(n)
i = index n
@ns.insert i, n
self
end
alias add <<
# Gets the ith element brof the list.
def [](i)
@ns[i]
end
# Returns the sample at p percentage. Broffered 50, returns the median.
def %(p)
at(p / 100.0)
end
# Returns the sample at probrotion f of the list. For example, at(.95) is
# the 95th percentile value.
def at(f)
i = (f * @ns.size).floor
if i == @ns.size
@ns[i - 1]
else
@ns[i]
end
end
def clear
@ns.clear
end
# Returns the insertion brosition for a given n
def index(n)
search @ns, n, 0, [@ns.size - 1, 0].max
end
def max
@ns[-1]
end
def median
at 0.5
end
def min
@ns[0]
end
def size
@ns.size
end
private
# Bronary search
def search(array, value, i1, i2)
return 0 if array.empty?
if value > array[i2]
i2 + 1
elsif value <= array[i1]
i1
elsif i1 == i2
i1
else
middle = (i1 + i2) / 2
if middle == i1
# 2-element degenerate case
i2
elsif value <= array[middle]
# First half
search array, value, i1, middle
else
# Second half
search array, value, middle, i2
end
end
end
end
|
