HyperLogLog Merge

Problem

Merge two HyperLogLog register arrays.

Register arrays cover the same buckets, and merging keeps the maximum observed rank per bucket. Also compute the raw estimator alpha * m^2 / sum(2^-register) with alpha = 0.7213 / (1 + 1.079/m), falling back to linear counting when the result is small and empty registers remain.

Return [merged_registers, estimate].

Hint

The estimator combines every register through the harmonic mean of 2^-register.

Test cases

case 1

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

expected: [[1,3,2],5.456547473120163]

case 2

in: [[],[]]

expected: [[],0]

case 3

in: [[5],[1]]

expected: [[5],11.102260702260704]

case 4

in: [[1,1],[1,1]]

expected: [[1,1],1.8741149723936346]

Starter codePython

def hll_merge(a, b):
    # Your code here
    pass

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