This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
The following commit(s) were added to refs/heads/main by this push:
new 1402037 refactor(hll): reuse the inverse powers lookup table (#148)
1402037 is described below
commit 1402037b7f1ade76e600a1a66315788f52e02df1
Author: tison <[email protected]>
AuthorDate: Sun Jul 12 06:03:49 2026 +0800
refactor(hll): reuse the inverse powers lookup table (#148)
Signed-off-by: tison <[email protected]>
---
datasketches/src/common/mod.rs | 2 +-
datasketches/src/hll/estimator.rs | 21 +++++----------------
2 files changed, 6 insertions(+), 17 deletions(-)
diff --git a/datasketches/src/common/mod.rs b/datasketches/src/common/mod.rs
index 503df72..95d2b2d 100644
--- a/datasketches/src/common/mod.rs
+++ b/datasketches/src/common/mod.rs
@@ -24,5 +24,5 @@ pub use self::resize::ResizeFactor;
#[cfg(feature = "theta")]
pub(crate) mod binomial_bounds;
-#[cfg(feature = "cpc")]
+#[cfg(any(feature = "cpc", feature = "hll"))]
pub(crate) mod inv_pow2_table;
diff --git a/datasketches/src/hll/estimator.rs
b/datasketches/src/hll/estimator.rs
index 7c9ca08..e094d98 100644
--- a/datasketches/src/hll/estimator.rs
+++ b/datasketches/src/hll/estimator.rs
@@ -23,6 +23,7 @@
//! moderate cardinalities.
use crate::common::NumStdDev;
+use crate::common::inv_pow2_table::INVERSE_POWERS_OF_2;
use crate::hll::composite_interpolation;
use crate::hll::cubic_interpolation;
use crate::hll::harmonic_numbers;
@@ -90,16 +91,16 @@ impl HipEstimator {
fn update_kxq(&mut self, old_value: u8, new_value: u8) {
// Subtract old value contribution
if old_value < 32 {
- self.kxq0 -= inv_pow2(old_value);
+ self.kxq0 -= INVERSE_POWERS_OF_2[old_value as usize];
} else {
- self.kxq1 -= inv_pow2(old_value);
+ self.kxq1 -= INVERSE_POWERS_OF_2[old_value as usize];
}
// Add new value contribution
if new_value < 32 {
- self.kxq0 += inv_pow2(new_value);
+ self.kxq0 += INVERSE_POWERS_OF_2[new_value as usize];
} else {
- self.kxq1 += inv_pow2(new_value);
+ self.kxq1 += INVERSE_POWERS_OF_2[new_value as usize];
}
}
@@ -313,18 +314,6 @@ impl HipEstimator {
}
}
-/// Compute 1 / 2^value (inverse power of 2)
-#[inline]
-fn inv_pow2(value: u8) -> f64 {
- if value == 0 {
- 1.0
- } else if value <= 63 {
- 1.0 / (1u64 << value) as f64
- } else {
- f64::exp2(-(value as f64))
- }
-}
-
/// Get relative error for HLL estimates
///
/// This matches the implementation in datasketches-cpp HllUtil.hpp and
RelativeErrorTables.hpp
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
