Class: FastExists::Probabilistic::CountMinSketch

Inherits:
Object
  • Object
show all
Defined in:
lib/fast_exists/probabilistic/count_min_sketch.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(epsilon: 0.001, confidence: 0.99) ⇒ CountMinSketch

Returns a new instance of CountMinSketch.



11
12
13
14
15
16
 
# File 'lib/fast_exists/probabilistic/count_min_sketch.rb', line 11

def initialize(epsilon: 0.001, confidence: 0.99)
  @width = (Math::E / epsilon).ceil
  @depth = Math.log(1.0 / (1.0 - confidence)).ceil
  @table = Array.new(@depth) { Array.new(@width, 0) }
  @mutex = Mutex.new
end

Instance Attribute Details

#depth ⇒ Object (readonly)

Returns the value of attribute depth.



9
10
11
 
# File 'lib/fast_exists/probabilistic/count_min_sketch.rb', line 9

def depth
  @depth
end

#width ⇒ Object (readonly)

Returns the value of attribute width.



9
10
11
 
# File 'lib/fast_exists/probabilistic/count_min_sketch.rb', line 9

def width
  @width
end

Instance Method Details

#add(element, count = 1) ⇒ Object 



18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/fast_exists/probabilistic/count_min_sketch.rb', line 18

def add(element, count = 1)
  key = element.to_s
  indexes = hash_indexes(key)

  @mutex.synchronize do
    indexes.each_with_index do |col, row|
      @table[row][col] += count
    end
  end
  true
end

#clear ⇒ Object 



39
40
41
42
43
44
 
# File 'lib/fast_exists/probabilistic/count_min_sketch.rb', line 39

def clear
  @mutex.synchronize do
    @table.each { |row| row.fill(0) }
  end
  true
end

#estimate(element) ⇒ Object 



30
31
32
33
34
35
36
37
 
# File 'lib/fast_exists/probabilistic/count_min_sketch.rb', line 30

def estimate(element)
  key = element.to_s
  indexes = hash_indexes(key)

  @mutex.synchronize do
    indexes.each_with_index.map { |col, row| @table[row][col] }.min
  end
end

#stats ⇒ Object 



46
47
48
49
50
51
52
53
 
# File 'lib/fast_exists/probabilistic/count_min_sketch.rb', line 46

def stats
  {
    type: :count_min_sketch,
    width: @width,
    depth: @depth,
    memory_cells: @width * @depth
  }
end