Class: Estimator

Inherits:
Object
  • Object
show all
Defined in:
lib/estimator.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(invariant) ⇒ Estimator

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

#invariant ⇒ Object (readonly)

Returns the value of attribute invariant.



8
9
10
 
# File 'lib/estimator.rb', line 8

def invariant
  @invariant
end

#n ⇒ Object

Returns the value of attribute n.



7
8
9
 
# File 'lib/estimator.rb', line 7

def n
  @n
end

#samples ⇒ Object

Returns the value of attribute samples.



6
7
8
 
# File 'lib/estimator.rb', line 6

def samples
  @samples
end

Instance Method Details

#compress! ⇒ Object

Compresses the internal data-structure. O(n), where n is the number of elements of the internal data structure

Parameters:

Returns:

The new size of the data-structure



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.length
end

#insert(value) ⇒ Object

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

#query(phi) ⇒ Object

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