HyperLogLog Raw Cardinality Estimate

Problem

Estimate cardinality from HyperLogLog register values with the raw harmonic-mean formula.

For m registers return alpha * m * m / sum(2 ** -r) over all registers, where alpha = 0.7213 / (1 + 1.079 / m). The registers hold the maximum observed rank per bucket, and an empty register list returns 0.0.

Hint

Large register values shrink the denominator, so the estimate grows with the observed ranks.

Test cases

case 1

in: [[0,0,0,0]]

expected: 2.272258318566647

case 2

in: [[3,2,1,0]]

expected: 4.847484412942181

case 3

in: [[5]]

expected: 11.102260702260704

case 4

in: [[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]

expected: 10.811686866912583

case 5

in: [[]]

expected: 0

Starter codePython

def hll_raw_estimate(registers):
    # Your code here
    pass

5 test cases · run your code against them in the editor