Class: FastExists::Probabilistic::HyperLogLog

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(p: 14) ⇒ HyperLogLog

Returns a new instance of HyperLogLog.

Raises:



11
12
13
14
15
16
17
18
19
 
# File 'lib/fast_exists/probabilistic/hyper_log_log.rb', line 11

def initialize(p: 14)
  raise InvalidArgumentError, "p must be between 4 and 16" if p < 4 || p > 16

  @p = p
  @m = 1 << p
  @registers = Array.new(@m, 0)
  @alpha = calculate_alpha(@m)
  @mutex = Mutex.new
end

Instance Attribute Details

#m ⇒ Object (readonly)

Returns the value of attribute m.



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

def m
  @m
end

#p ⇒ Object (readonly)

Returns the value of attribute p.



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

def p
  @p
end

Instance Method Details

#add(element) ⇒ Object 



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

def add(element)
  hash = Digest::SHA256.hexdigest(element.to_s)[0..15].hex
  idx = hash >> (64 - @p)
  w = hash & ((1 << (64 - @p)) - 1)
  rho = leading_zeros(w, 64 - @p) + 1

  @mutex.synchronize do
    @registers[idx] = [@registers[idx], rho].max
  end
  true
end

#clear ⇒ Object 



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

def clear
  @mutex.synchronize do
    @registers.fill(0)
  end
  true
end

#count ⇒ Object 



33
34
35
36
37
38
39
40
41
42
43
44
 
# File 'lib/fast_exists/probabilistic/hyper_log_log.rb', line 33

def count
  @mutex.synchronize do
    raw_estimate = @alpha * (@m**2) * (1.0 / @registers.sum { |r| 2.0**(-r) })

    if raw_estimate <= 2.5 * @m
      zeros = @registers.count(0)
      zeros > 0 ? @m * Math.log(@m.to_f / zeros) : raw_estimate
    else
      raw_estimate
    end.round
  end
end

#stats ⇒ Object 



53
54
55
56
57
58
59
60
 
# File 'lib/fast_exists/probabilistic/hyper_log_log.rb', line 53

def stats
  {
    type: :hyper_log_log,
    registers: @m,
    precision_p: @p,
    estimated_cardinality: count
  }
end