Class: FastExists::Bloom::Filter

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

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(expected_elements: 1_000_000, false_positive_rate: 0.001, bit_array: nil) ⇒ Filter

Returns a new instance of Filter.

Raises:



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

def initialize(expected_elements: 1_000_000, false_positive_rate: 0.001, bit_array: nil)
  raise InvalidArgumentError, "expected_elements must be > 0" if expected_elements <= 0
  raise InvalidArgumentError, "false_positive_rate must be between 0 and 1" if false_positive_rate <= 0 || false_positive_rate >= 1

  @expected_elements = expected_elements
  @false_positive_rate = false_positive_rate
  @count = 0
  @mutex = Mutex.new

  @bit_size = calculate_bit_size(expected_elements, false_positive_rate)
  @hash_count = calculate_hash_count(@bit_size, expected_elements)
  @bit_array = bit_array || FastExists::BitArray.new(@bit_size)
end

Instance Attribute Details

#bit_array ⇒ Object (readonly)

Returns the value of attribute bit_array.



107
108
109
 
# File 'lib/fast_exists/bloom/filter.rb', line 107

def bit_array
  @bit_array
end

#bit_size ⇒ Object (readonly)

Returns the value of attribute bit_size.



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

def bit_size
  @bit_size
end

#count ⇒ Object (readonly)

Returns the value of attribute count.



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

def count
  @count
end

#expected_elements ⇒ Object (readonly)

Returns the value of attribute expected_elements.



9
10
11
 
# File 'lib/fast_exists/bloom/filter.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/filter.rb', line 9

def false_positive_rate
  @false_positive_rate
end

#hash_count ⇒ Object (readonly)

Returns the value of attribute hash_count.



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

def hash_count
  @hash_count
end

Class Method Details

.load(dump_data) ⇒ Object 



97
98
99
100
101
102
103
104
105
 
# File 'lib/fast_exists/bloom/filter.rb', line 97

def self.load(dump_data)
  filter = new(
    expected_elements: dump_data[:expected_elements],
    false_positive_rate: dump_data[:false_positive_rate]
  )
  filter.instance_variable_set(:@count, dump_data[:count])
  filter.bit_array.to_s_load(dump_data[:bytes])
  filter
end

Instance Method Details

#add(element) ⇒ Object 



25
26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/fast_exists/bloom/filter.rb', line 25

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

  indexes.each do |idx|
    @bit_array.set(idx)
  end

  @mutex.synchronize do
    @count += 1
  end
  true
end

#capacity ⇒ Object 



54
55
56
 
# File 'lib/fast_exists/bloom/filter.rb', line 54

def capacity
  @expected_elements
end

#clear ⇒ Object 



46
47
48
49
50
51
52
 
# File 'lib/fast_exists/bloom/filter.rb', line 46

def clear
  @mutex.synchronize do
    @bit_array.clear
    @count = 0
  end
  true
end

#contains?(element) ⇒ Boolean

Returns:

  • (Boolean) 


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

def contains?(element)
  key = element.to_s
  indexes = hash_indexes(key)

  indexes.all? { |idx| @bit_array.set?(idx) }
end

#dump ⇒ Object 



86
87
88
89
90
91
92
93
94
95
 
# File 'lib/fast_exists/bloom/filter.rb', line 86

def dump
  {
    expected_elements: @expected_elements,
    false_positive_rate: @false_positive_rate,
    count: @count,
    bit_size: @bit_size,
    hash_count: @hash_count,
    bytes: @bit_array.to_s
  }
end

#estimated_false_positive_rate ⇒ Object 



63
64
65
66
67
 
# File 'lib/fast_exists/bloom/filter.rb', line 63

def estimated_false_positive_rate
  # p = (1 - e^(-k * n / m))^k
  exponent = -(@hash_count * @count.to_f) / @bit_size
  (1.0 - Math::E**exponent)**@hash_count
end

#memory_usage_bytes ⇒ Object 



69
70
71
 
# File 'lib/fast_exists/bloom/filter.rb', line 69

def memory_usage_bytes
  @bit_array.bytesize
end

#occupancy ⇒ Object 



58
59
60
61
 
# File 'lib/fast_exists/bloom/filter.rb', line 58

def occupancy
  set_bits = @bit_array.count_ones
  set_bits.to_f / @bit_size
end

#stats ⇒ Object 



73
74
75
76
77
78
79
80
81
82
83
84
 
# File 'lib/fast_exists/bloom/filter.rb', line 73

def stats
  {
    expected_elements: @expected_elements,
    false_positive_rate: @false_positive_rate,
    estimated_false_positive_rate: estimated_false_positive_rate,
    inserted_items: @count,
    bit_size: @bit_size,
    hash_count: @hash_count,
    occupancy: occupancy,
    memory_usage_bytes: memory_usage_bytes
  }
end