Visitar URL original
Merge pull request #70 from jaideeppyne/feat/hll-composite-estimate · apache/datasketches-python@b821d1a · GitHub
Skip to content

Commit b821d1a

Browse files
authored
Merge pull request #70 from jaideeppyne/feat/hll-composite-estimate
Bind HLL get_composite_estimate
2 parents e34b5b1 + dc0f121 commit b821d1a

2 files changed

Lines changed: 27 additions & 1 deletion

File tree

‎src/hll_wrapper.cpp‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -53,6 +53,10 @@ void init_hll(nb::module_ &m) {
5353
.def_prop_ro("tgt_type", &hll_sketch::get_target_type, "The HLL type (4, 6, or 8) when in estimation mode")
5454
.def("get_estimate", &hll_sketch::get_estimate,
5555
"Estimate of the distinct count of the input stream")
56+
.def("get_composite_estimate", &hll_sketch::get_composite_estimate,
57+
"Composite estimate of the distinct count. Less accurate than get_estimate() when the HIP estimator "
58+
"is available, but order-independent, and the estimator used once a sketch has been unioned. "
59+
"Intended for error characterization rather than normal use.")
5660
.def("get_lower_bound", &hll_sketch::get_lower_bound, nb::arg("num_std_devs"),
5761
"Returns the approximate lower error bound given the specified number of standard deviations in {1, 2, 3}")
5862
.def("get_upper_bound", &hll_sketch::get_upper_bound, nb::arg("num_std_devs"),
@@ -111,6 +115,10 @@ void init_hll(nb::module_ &m) {
111115
.def_prop_ro("lg_config_k", &hll_union::get_lg_config_k, "Configured lg_k value for the union")
112116
.def("get_estimate", &hll_union::get_estimate,
113117
"Estimate of the distinct count of the input stream")
118+
.def("get_composite_estimate", &hll_union::get_composite_estimate,
119+
"Composite estimate of the distinct count. This is less accurate than get_estimate() and is used "
120+
"automatically when a union cannot keep the HIP estimator. Intended for error characterization "
121+
"rather than normal use.")
114122
.def("get_lower_bound", &hll_union::get_lower_bound, nb::arg("num_std_devs"),
115123
"Returns the approximate lower error bound given the specified number of standard deviations in {1, 2, 3}")
116124
.def("get_upper_bound", &hll_union::get_upper_bound, nb::arg("num_std_devs"),

‎tests/hll_test.py‎

Lines changed: 19 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -128,7 +128,25 @@ def test_hll_union(self):
128128
sk = union.get_result()
129129
self.assertTrue(isinstance(sk, hll_sketch))
130130
self.assertEqual(sk.tgt_type, tgt_hll_type.HLL_4)
131-
131+
132+
def test_hll_composite_estimate_is_order_independent(self):
133+
lgk = 12
134+
n = 5000
135+
forward = hll_sketch(lgk)
136+
reverse = hll_sketch(lgk)
137+
for i in range(n):
138+
forward.update(i)
139+
reverse.update(n - 1 - i)
140+
141+
# HIP estimates can depend on insertion order. The composite estimator must not.
142+
self.assertEqual(forward.get_composite_estimate(), reverse.get_composite_estimate())
143+
self.assertGreater(forward.get_composite_estimate(), 0)
144+
145+
union = hll_union(lgk)
146+
union.update(forward)
147+
union.update(reverse)
148+
self.assertEqual(union.get_composite_estimate(), union.get_result().get_composite_estimate())
149+
132150
def generate_sketch(self, n, lgk, sk_type=tgt_hll_type.HLL_4, st_idx=0):
133151
sk = hll_sketch(lgk, sk_type)
134152
for i in range(st_idx, st_idx + n):

0 commit comments

Comments
 (0)