HyperLogLog sketches can be combined without replaying their original streams. This makes it possible to maintain one sketch per shard, region, or time window and later obtain a sketch for the union.
Design a HyperLogLogMerger class:
HyperLogLogMerger() creates a stateless merger.int[] merge(int[] a, int[] b) returns a new sketch containing the union of a and b.
The arrays have the same length and therefore the same precision. Register i stores the largest rank observed for hash bucket i. The union's value at that position is max(a[i], b[i]).
Do not mutate either input. Each call is independent.
Example 1:
Input:
Output:
Explanation: Register 2 takes rank 5 from b, register 4 keeps rank 3 from a, and every other position follows the same maximum rule.
Example 2:
Input:
Output:
Explanation: The first sketch supplies positions 0 and 2; the second supplies position 1.
Constraints
0 <= a.length == b.length <= 10^50 <= a[i], b[i] <= 64- Both arrays were produced with the same HyperLogLog precision and hash function.
- At most
100 calls are made to merge.
Merge HyperLogLog Sketchesmedium