class CountMinSketch::Counter

Constants

MAX_FIXNUM

Attributes

data[R]
k[R]
m[R]

Public Class Methods

new(k=10, m=100000) click to toggle source
# File lib/count_min_sketch/counter.rb, line 11
def initialize(k=10, m=100000)
  @k = k
  @m = m
  @data = Array.new(k) { Array.new(m,0) }
  @seeds = Array.new(k) { rand(MAX_FIXNUM + 1) }
end

Public Instance Methods

get_count(x) click to toggle source
# File lib/count_min_sketch/counter.rb, line 18
def get_count(x)
  insert(x, 0)
end
insert(x, n=1) click to toggle source
# File lib/count_min_sketch/counter.rb, line 22
def insert(x, n=1)
  min_count = Float::INFINITY
  hashes_of_x = @seeds.map { |s| CityHash.hash64(x, s) }
  hashes_of_x.each_with_index do |hash, i|
    j = hash % m
    count = @data[i][j] += n
    min_count = count if count < min_count
  end
  min_count
end