HyperLogLog Estimate Lite

Problem

Estimate cardinality from a HyperLogLog sketch.

Build the registers as in the update problem, then compute the raw estimate alpha * m^2 / sum(2^-register) with alpha = 0.7213 / (1 + 1.079/m). When the raw estimate is small (at most 2.5m) and some registers are zero, use the linear-counting estimate m * ln(m / zeros) instead.

Return the estimate as a float.

Hint

Linear counting takes over for small cardinalities when zero registers remain.

Test cases

case 1

in: [4,["a","b","c"]]

expected: 5.545177444479562

case 2

in: [8,["a","b","c","d","e"]]

expected: 7.8466340240938095

case 3

in: [16,[]]

expected: 0

case 4

in: [4,["x","x","y"]]

expected: 2.772588722239781

Starter codePython

def hll_estimate(num_buckets, items):
    # Your code here
    pass

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