This is an automated email from the ASF dual-hosted git repository. tisonkun pushed a commit to branch inv-table in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
commit 9151e64e385af28155051ad551de13783bced41f Author: tison <[email protected]> AuthorDate: Sat Jul 11 13:57:58 2026 +0800 refactor(hll): reuse the inverse powers lookup table 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]
