class Estimator

Attributes

invariant[R]
n[RW]
samples[RW]

Public Class Methods

new(invariant) click to toggle source

Creates a new quantile Estimator object using the provided invariant.

Parameters:

value

An Invariant object

# File lib/estimator.rb, line 16
def initialize(invariant)
  @invariant = invariant
  self.samples = []
  self.n = 0
end

Public Instance Methods

compress!() click to toggle source

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
# 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) click to toggle source

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

# 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) click to toggle source

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

# 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