Code lab · World 08 · Designing an Analytics Pipeline

HyperLogLog unique viewers.

Count distinct viewers in a few kilobytes with HyperLogLog registers, correct small counts with linear counting, and merge daily sketches into an exact-union weekly count.

Medium~35 min3 example + 8 hidden tests+90 XPJump to the code ↓

Saving also stores the Python runtime (~13.5 MB, once for every lab) so this lab runs with no internet.

PractisesW08 · D63.1 HyperLogLog: the intuition W08 · D63.4 Merging sketches W08 · D52.2 Approximate algorithms W08 · BossCapstone · viewers_hll, mergeable across days

The Week 8 capstone counts unique viewers per title, per day, and then per month. An exact set of viewer ids per title per day is gigabytes, and you can't add daily uniques: a viewer who watched on 5 days would count 5 times. The capstone's rollup stores a viewers_hll sketch instead, "mergeable across days" (Day 5, section 2.2: approximate algorithms).

HyperLogLog (Flajolet et al., 2007) keeps m = 2^p small registers:

Hash the item to 64 bits (hash64 is given).
The first p bits pick a register: idx = h >> (64 - p).
In the remaining 64 - p bits w, find the position of the leftmost 1-bit, counting from 1: rho = (64 - p) - w.bit_length() + 1. (If w is 0, rho = 64 - p + 1.)
The register keeps the largest rho it has seen.

A run of r leading zeros happens about once in 2^r distinct items, so the registers estimate the count:

text3 lines

E = alpha(m) * m * m / sum(2 ** -reg for reg in registers)
if E <= 2.5 * m and some registers are 0:      # small counts: linear counting is better
    E = m * ln(m / zero_registers)

alpha(m) is given. With p = 12 (4,096 registers, a few KB) the standard error is about 1.04 / sqrt(m) = 1.6%.

Implement HyperLogLog(p):

Method	Does
`HyperLogLog(p)`	`p` from 4 to 16, else `ValueError`. `self.registers` is a list of `2 ** p` zeros
`add(item)`	updates one register
`count()`	the estimate, rounded to an int. `0` when empty
`merge(other)`	a new sketch, the register-wise max of both. Different `p`: `ValueError`. Neither input changes

Rules the tests check:

Adding the same item again changes nothing.
A merged sketch is identical to one sketch fed both streams: that's what makes it safe to store per day and merge per month.
Results are deterministic: hash64 is a fixed hash, not Python's per-process hash().

Python 3.14 loads on first run (~6.5 MB once)14

Loading the editor…

⌘/Ctrl + Enternot run yet · 8 s limit

press Run tests

Write your code, then run 3 example tests and 8 hidden tests. Each run is limited to 8 seconds: an infinite loop gets stopped and Python restarts, your code stays.