Class: Estimator

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

Instance Attribute Summary (collapse)

Instance Method Summary (collapse)

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