Spaces:
Paused
Paused
File size: 2,310 Bytes
a2bbd94 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | """Sketch accuracy: quantile histograms, HyperLogLog, reservoir, Wilson CIs."""
from __future__ import annotations
import numpy as np
import pytest
from sensorflow.megaeval.sketches import HyperLogLog, QuantileHistogram, Reservoir
from sensorflow.megaeval.sampling import wilson_interval
def test_quantile_histogram_percentiles_close_to_exact():
rng = np.random.default_rng(3)
data = np.clip(rng.beta(5, 2, size=50_000), 0, 1)
h = QuantileHistogram(0, 1, 64)
h.add(data)
bin_width = 1 / 64
for q in (10, 25, 50, 75, 90, 99):
approx = h.percentile(q)
exact = float(np.percentile(data, q))
assert abs(approx - exact) <= bin_width + 1e-9, f"p{q}: {approx} vs {exact}"
def test_quantile_histogram_merge_equals_combined():
rng = np.random.default_rng(4)
a, b = rng.random(10_000), rng.random(10_000)
ha, hb, hc = QuantileHistogram(), QuantileHistogram(), QuantileHistogram()
ha.add(a)
hb.add(b)
hc.add(np.concatenate([a, b]))
merged = ha.merge(hb)
assert np.array_equal(merged.counts, hc.counts)
def test_hll_estimate_within_five_percent():
hll = HyperLogLog(12)
n = 20_000
hll.add_ids(np.arange(n, dtype=np.int64))
est = hll.estimate()
assert abs(est - n) / n < 0.05, est
def test_hll_merge_is_union():
h1, h2 = HyperLogLog(12), HyperLogLog(12)
h1.add_ids(np.arange(0, 8_000, dtype=np.int64))
h2.add_ids(np.arange(4_000, 12_000, dtype=np.int64))
merged = h1.merge(h2)
est = merged.estimate()
assert abs(est - 12_000) / 12_000 < 0.06, est
def test_reservoir_bounded_and_uniformish():
r = Reservoir(k=100, seed=1)
r.add_ids(np.arange(10_000))
assert len(r.items) == 100
assert r.seen == 10_000
# sampled ids should span the range, not just the head
assert max(r.items) > 5_000 and min(r.items) < 5_000
def test_wilson_interval_known_value():
lo, hi = wilson_interval(8, 10)
assert lo == pytest.approx(0.490, abs=0.01)
assert hi == pytest.approx(0.943, abs=0.01)
lo0, hi0 = wilson_interval(0, 0)
assert (lo0, hi0) == (0.0, 1.0)
# Wilson upper bound at p=1 is mathematically < 1 (that's the point of Wilson)
lo1, hi1 = wilson_interval(50, 50)
assert 0.9 < lo1 < hi1 <= 1.0
assert hi1 == pytest.approx(0.9928, abs=0.01)
|