Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_data/tests/hll.rs

5.7 KiB, 3 runs

created by r1870400018:11206, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Integration tests for the HyperLogLog primitive.
2
3use oxedyne_fe2o3_core::prelude::*;
4
5use oxedyne_fe2o3_data::hll::{
6 HyperLogLog,
7 P_DEFAULT,
8 P_MAX,
9 P_MIN,
10};
11
12
13/// A deterministic, uniformly distributed 64-bit hash suitable for synthetic
14/// cardinality tests. Uses xoshiro256++ mixing; not cryptographic.
15fn hash_u64(mut x: u64) -> u64 {
16 x = x.wrapping_add(0x9e37_79b9_7f4a_7c15);
17 let mut z = x;
18 z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
19 z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
20 z ^ (z >> 31)
21}
22
23
24#[test]
25fn rejects_out_of_range_precision() -> Outcome<()> {
26 assert!(HyperLogLog::new(P_MIN - 1).is_err());
27 assert!(HyperLogLog::new(P_MAX + 1).is_err());
28 assert!(HyperLogLog::new(0).is_err());
29 assert!(HyperLogLog::new(100).is_err());
30 Ok(())
31}
32
33#[test]
34fn new_allocates_correct_register_count() -> Outcome<()> {
35 for p in P_MIN..=P_MAX {
36 let s = res!(HyperLogLog::new(p));
37 let m = 1usize << p;
38 assert_eq!(s.m(), m, "precision {}: expected {} registers", p, m);
39 assert_eq!(s.precision(), p);
40 assert_eq!(s.as_bytes().len(), m);
41 assert!(s.as_bytes().iter().all(|&b| b == 0));
42 }
43 Ok(())
44}
45
46#[test]
47fn default_precision_is_sixteen_kibibytes() -> Outcome<()> {
48 let s = res!(HyperLogLog::new(P_DEFAULT));
49 assert_eq!(s.as_bytes().len(), 16 * 1024);
50 Ok(())
51}
52
53#[test]
54fn empty_sketch_estimate_is_zero() -> Outcome<()> {
55 let s = res!(HyperLogLog::new(P_DEFAULT));
56 // Linear counting kicks in: m * ln(m/m) = m * 0 = 0.
57 assert_eq!(s.estimate_rounded(), 0);
58 Ok(())
59}
60
61#[test]
62fn single_element_estimate_near_one() -> Outcome<()> {
63 let mut s = res!(HyperLogLog::new(P_DEFAULT));
64 s.add_hash(hash_u64(1));
65 // Linear counting: m * ln(m / (m-1)) for a single filled register.
66 // At m = 16384 this gives ≈ 1.0 (the ln(m/(m-1)) factor ≈ 1/(m-1)).
67 let est = s.estimate();
68 assert!(est > 0.5 && est < 2.0, "estimate = {}", est);
69 Ok(())
70}
71
72#[test]
73fn estimate_accurate_at_medium_cardinality() -> Outcome<()> {
74 let mut s = res!(HyperLogLog::new(P_DEFAULT));
75 // 10 000 distinct elements; at p=14 the theoretical standard error is
76 // ~0.8%. Allow 5% tolerance for safety on a single run.
77 let true_n = 10_000u64;
78 for i in 0..true_n {
79 s.add_hash(hash_u64(i));
80 }
81 let est = s.estimate();
82 let err = (est - true_n as f64).abs() / true_n as f64;
83 assert!(err < 0.05,
84 "estimate {} vs true {} differs by {:.2}%",
85 est, true_n, err * 100.0);
86 Ok(())
87}
88
89#[test]
90fn estimate_accurate_at_large_cardinality() -> Outcome<()> {
91 let mut s = res!(HyperLogLog::new(P_DEFAULT));
92 // 100 000 distinct elements; raw HLL regime.
93 let true_n = 100_000u64;
94 for i in 0..true_n {
95 s.add_hash(hash_u64(i));
96 }
97 let est = s.estimate();
98 let err = (est - true_n as f64).abs() / true_n as f64;
99 assert!(err < 0.05,
100 "estimate {} vs true {} differs by {:.2}%",
101 est, true_n, err * 100.0);
102 Ok(())
103}
104
105#[test]
106fn duplicate_inserts_do_not_change_estimate() -> Outcome<()> {
107 let mut s = res!(HyperLogLog::new(P_DEFAULT));
108 for i in 0..1_000u64 {
109 s.add_hash(hash_u64(i));
110 }
111 let before = s.estimate();
112 // Re-insert every element; register values are already at their max so
113 // the sketch should not move.
114 for _ in 0..5 {
115 for i in 0..1_000u64 {
116 s.add_hash(hash_u64(i));
117 }
118 }
119 let after = s.estimate();
120 assert!((before - after).abs() < 1e-9,
121 "duplicate inserts changed estimate: before {}, after {}",
122 before, after);
123 Ok(())
124}
125
126#[test]
127fn merge_union_approximates_cardinality_of_union() -> Outcome<()> {
128 let mut a = res!(HyperLogLog::new(P_DEFAULT));
129 let mut b = res!(HyperLogLog::new(P_DEFAULT));
130 // a = {0..5000}, b = {2500..7500}, union = 7500 distinct.
131 for i in 0..5_000u64 {
132 a.add_hash(hash_u64(i));
133 }
134 for i in 2_500u64..7_500 {
135 b.add_hash(hash_u64(i));
136 }
137 res!(a.merge(&b));
138 let est = a.estimate();
139 let true_union = 7_500.0f64;
140 let err = (est - true_union).abs() / true_union;
141 assert!(err < 0.05,
142 "merged estimate {} vs true union {} differs by {:.2}%",
143 est, true_union, err * 100.0);
144 Ok(())
145}
146
147#[test]
148fn merge_is_idempotent() -> Outcome<()> {
149 let mut a = res!(HyperLogLog::new(P_DEFAULT));
150 let b = {
151 let mut b = res!(HyperLogLog::new(P_DEFAULT));
152 for i in 0..1_000u64 {
153 b.add_hash(hash_u64(i));
154 }
155 b
156 };
157 res!(a.merge(&b));
158 let once: Vec<u8> = a.as_bytes().to_vec();
159 res!(a.merge(&b));
160 assert_eq!(once, a.as_bytes(),
161 "merging the same sketch twice changed registers");
162 Ok(())
163}
164
165#[test]
166fn merge_rejects_mismatched_precision() -> Outcome<()> {
167 let mut a = res!(HyperLogLog::new(10));
168 let b = res!(HyperLogLog::new(12));
169 assert!(a.merge(&b).is_err());
170 Ok(())
171}
172
173#[test]
174fn from_bytes_roundtrips() -> Outcome<()> {
175 let mut src = res!(HyperLogLog::new(P_DEFAULT));
176 for i in 0..500u64 {
177 src.add_hash(hash_u64(i));
178 }
179 let bytes = src.as_bytes().to_vec();
180 let copy = res!(HyperLogLog::from_bytes(P_DEFAULT, &bytes));
181 assert_eq!(copy.as_bytes(), src.as_bytes());
182 let a = src.estimate();
183 let b = copy.estimate();
184 assert!((a - b).abs() < 1e-9);
185 Ok(())
186}
187
188#[test]
189fn from_bytes_validates_length() -> Outcome<()> {
190 let bytes = vec![0u8; 10];
191 assert!(HyperLogLog::from_bytes(P_DEFAULT, &bytes).is_err());
192 Ok(())
193}
194
195#[test]
196fn clear_zeroes_registers() -> Outcome<()> {
197 let mut s = res!(HyperLogLog::new(P_DEFAULT));
198 for i in 0..100u64 {
199 s.add_hash(hash_u64(i));
200 }
201 assert!(s.estimate() > 50.0);
202 s.clear();
203 assert_eq!(s.estimate_rounded(), 0);
204 assert!(s.as_bytes().iter().all(|&b| b == 0));
205 Ok(())
206}
207
208#[test]
209fn register_values_within_theoretical_bound() -> Outcome<()> {
210 let mut s = res!(HyperLogLog::new(P_DEFAULT));
211 // The per-register cap at p is (64 - p) + 1 = 51 here.
212 for i in 0..1_000_000u64 {
213 s.add_hash(hash_u64(i));
214 }
215 let max_rho = 64u8 - P_DEFAULT + 1;
216 assert!(s.as_bytes().iter().all(|&r| r <= max_rho),
217 "register exceeded theoretical max {}", max_rho);
218 Ok(())
219}