Class: FastExists::Bloom::Counting

Inherits:
Object
  • Object
show all
Defined in:
lib/fast_exists/bloom/counting.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(expected_elements: 10_000, false_positive_rate: 0.001) ⇒ Counting

Returns a new instance of Counting.



11
12
13
14
15
16
17
18
19
20
 
# File 'lib/fast_exists/bloom/counting.rb', line 11

def initialize(expected_elements: 10_000, false_positive_rate: 0.001)
  @expected_elements = expected_elements
  @false_positive_rate = false_positive_rate
  @count = 0
  @mutex = Mutex.new

  @bit_size = (-(expected_elements * Math.log(false_positive_rate)) / (Math.log(2)**2)).ceil
  @hash_count = [((@bit_size.to_f / expected_elements) * Math.log(2)).round, 1].max
  @counters = Array.new(@bit_size, 0)
end

Instance Attribute Details

#count ⇒ Object (readonly)

Returns the value of attribute count.



9
10
11
 
# File 'lib/fast_exists/bloom/counting.rb', line 9

def count
  @count
end

#counter_size ⇒ Object (readonly)

Returns the value of attribute counter_size.



9
10
11
 
# File 'lib/fast_exists/bloom/counting.rb', line 9

def counter_size
  @counter_size
end

#expected_elements ⇒ Object (readonly)

Returns the value of attribute expected_elements.



9
10
11
 
# File 'lib/fast_exists/bloom/counting.rb', line 9

def expected_elements
  @expected_elements
end

#false_positive_rate ⇒ Object (readonly)

Returns the value of attribute false_positive_rate.



9
10
11
 
# File 'lib/fast_exists/bloom/counting.rb', line 9

def false_positive_rate
  @false_positive_rate
end

Instance Method Details

#add(element) ⇒ Object 



22
23
24
25
26
27
28
29
30
31
 
# File 'lib/fast_exists/bloom/counting.rb', line 22

def add(element)
  indexes = hash_indexes(element.to_s)
  @mutex.synchronize do
    indexes.each do |idx|
      @counters[idx] += 1 if @counters[idx] < 255
    end
    @count += 1
  end
  true
end

#clear ⇒ Object 



53
54
55
56
57
58
59
 
# File 'lib/fast_exists/bloom/counting.rb', line 53

def clear
  @mutex.synchronize do
    @counters.fill(0)
    @count = 0
  end
  true
end

#contains?(element) ⇒ Boolean

Returns:

  • (Boolean) 


33
34
35
36
37
38
 
# File 'lib/fast_exists/bloom/counting.rb', line 33

def contains?(element)
  indexes = hash_indexes(element.to_s)
  @mutex.synchronize do
    indexes.all? { |idx| @counters[idx] > 0 }
  end
end

#delete(element) ⇒ Object 



40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/fast_exists/bloom/counting.rb', line 40

def delete(element)
  return false unless contains?(element)

  indexes = hash_indexes(element.to_s)
  @mutex.synchronize do
    indexes.each do |idx|
      @counters[idx] -= 1 if @counters[idx] > 0
    end
    @count = [@count - 1, 0].max
  end
  true
end

#stats ⇒ Object 



61
62
63
64
65
66
67
68
69
70
71
 
# File 'lib/fast_exists/bloom/counting.rb', line 61

def stats
  @mutex.synchronize do
    {
      type: :counting_bloom,
      inserted_items: @count,
      bit_size: @bit_size,
      hash_count: @hash_count,
      memory_usage_bytes: @counters.size
    }
  end
end