Class: Estimator
- Inherits:
-
Object
- Object
- Estimator
- Defined in:
- lib/estimator.rb
Instance Attribute Summary (collapse)
-
- (Object) invariant
readonly
Returns the value of attribute invariant.
-
- (Object) n
Returns the value of attribute n.
-
- (Object) samples
Returns the value of attribute samples.
Instance Method Summary (collapse)
-
- (Object) compress!
Compresses the internal data-structure.
-
- (Estimator) initialize(invariant)
constructor
Creates a new quantile Estimator object using the provided invariant.
-
- (Object) insert(value)
Inserts a new element into the quantile estimator.
-
- (Object) query(phi)
Queries de estimator for the given rank.
Constructor Details
- (Estimator) initialize(invariant)
Creates a new quantile Estimator object using the provided invariant.
Parameters:
- value
-
An ::Invariant object
16 17 18 19 20 |
# File 'lib/estimator.rb', line 16 def initialize(invariant) @invariant = invariant self.samples = [] self.n = 0 end |
Instance Attribute Details
- (Object) invariant (readonly)
Returns the value of attribute invariant
8 9 10 |
# File 'lib/estimator.rb', line 8 def invariant @invariant end |
- (Object) n
Returns the value of attribute n
7 8 9 |
# File 'lib/estimator.rb', line 7 def n @n end |
- (Object) samples
Returns the value of attribute samples
6 7 8 |
# File 'lib/estimator.rb', line 6 def samples @samples end |
Instance Method Details
- (Object) compress!
Compresses the internal data-structure. O(n), where n is the number of elements of the internal data structure
Parameters:
Returns:
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
# File 'lib/estimator.rb', line 69 def compress! c = Cursor.new(self.samples, self.samples.length - 1) while (~c != nil) && (~c.previous != nil) if ((~c.previous).g + (~c).g + (~c).delta).to_f <= invariant.upper_bound((~c.previous).rank, n) removed = ~c.previous (~c).rank = removed.rank (~c).g += removed.g c.previous.remove! c = c.previous end c = c.previous end self.samples end |
- (Object) insert(value)
Inserts a new element into the quantile estimator. O(n), where n is the number of elements of the internal data structure
Parameters:
- value
-
A Fixnum to observe
Returns:
The number of observations after the insertion
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 |
# File 'lib/estimator.rb', line 32 def insert(value) i = 0 r_i = 0 while(i < samples.length) item = samples[i] break if item.value > value # determines the order r_i = r_i + item.g i += 1 end delta = if (i-1 < 0) || (i == samples.length) 0 else # r_i [0, invariant.upper_bound(r_i, n).floor - 1].max end samples.insert(i, Item.new(value, 1, delta, r_i)) while(i < samples.length) item = samples[i] r_i = r_i + item.g item.rank = r_i i += 1 end self.n += 1 end |
- (Object) query(phi)
Queries de estimator for the given rank. O(n), where n is the number of elements of the internal data structure
Parameters:
- phi
-
A Fixnum between (0, 1) representing the rank to be queried (i.e, 0.5 represents the 50% quantile)
Returns:
The approximate value for the quantile you are checking
97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
# File 'lib/estimator.rb', line 97 def query(phi) if n == 0 nil else rank = 0 c = Cursor.new(samples) phi_n = phi * n last = (~c).value while ~c != nil last = (~c).value break if ~c.next == nil c = c.next if (rank + (~c).g + (~c).delta) > (phi_n + (invariant.upper_bound(phi_n, n) / 2)) return last end rank += (~c).g end return (~c).value end end |