ZENOTME commented on code in PR #152: URL: https://github.com/apache/datasketches-rust/pull/152#discussion_r3610493566
########## datasketches/src/tuple/hash_table.rs: ########## @@ -0,0 +1,480 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use std::hash::Hash; +use std::num::NonZeroU64; + +use crate::thetacommon::RawHashTableEntry; +use crate::thetacommon::hash_table::RawHashTable; + +/// A retained entry in a Tuple sketch: a hash key together with its associated summary. +/// +/// The hash is stored as [`NonZeroU64`] (hash 0 is screened out before insertion), so +/// `Option<TupleEntry<S>>` keeps the niche and takes no more space than `TupleEntry<S>` itself — +/// the same layout the Theta table gets from its `NonZeroU64` entry. +#[derive(Debug, Clone)] +pub struct TupleEntry<S> { + hash: NonZeroU64, + summary: S, +} + +impl<S> TupleEntry<S> { + /// Creates an entry from a hash known to be non-zero. + /// + /// # Panics + /// + /// Panics if `hash` is zero. + pub(crate) fn new(hash: u64, summary: S) -> Self { + let hash = NonZeroU64::new(hash).expect("hash must be non-zero"); + Self { hash, summary } + } + + /// Return the hash used as this entry's key. + pub fn hash(&self) -> u64 { + self.hash.get() + } + + /// Returns the summary stored in this entry. + pub fn summary(&self) -> &S { + &self.summary + } + + /// Splits this entry into its `(hash, summary)` parts. + pub(super) fn into_parts(self) -> (u64, S) { Review Comment: Maybe we don't need it if CompactTuple store TupleEntry. ########## datasketches/src/tuple/sketch.rs: ########## @@ -0,0 +1,1020 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Tuple sketch types. +//! +//! This module provides [`UpdatableTupleSketch`] (mutable) and [`CompactTupleSketch`] (immutable), +//! the Tuple sketch analogues of the Theta sketch. Each retained key carries a user-defined summary +//! whose behavior is supplied by a [`SummaryUpdatePolicy`]. + +use std::hash::Hash; +use std::marker::PhantomData; + +use crate::codec::SketchBytes; +use crate::codec::SketchSlice; +use crate::codec::assert::ensure_preamble_longs_in_range; +use crate::codec::assert::insufficient_data; +use crate::codec::family::Family; +use crate::common::NumStdDev; +use crate::common::ResizeFactor; +use crate::error::Error; +use crate::hash::DEFAULT_UPDATE_SEED; +use crate::hash::compute_seed_hash; +use crate::thetacommon::RawThetaSketchView; +use crate::thetacommon::binomial_bounds; +use crate::thetacommon::constants::DEFAULT_LG_K; +use crate::thetacommon::constants::FLAGS_IS_COMPACT; +use crate::thetacommon::constants::FLAGS_IS_EMPTY; +use crate::thetacommon::constants::FLAGS_IS_ORDERED; +use crate::thetacommon::constants::FLAGS_IS_READ_ONLY; +use crate::thetacommon::constants::MAX_LG_K; +use crate::thetacommon::constants::MAX_THETA; +use crate::thetacommon::constants::MIN_LG_K; +use crate::tuple::hash_table::TupleEntry; +use crate::tuple::hash_table::TupleHashTable; +use crate::tuple::policy::DefaultUpdatePolicy; +use crate::tuple::policy::SummaryUpdatePolicy; +use crate::tuple::serde::SummarySerde; +use crate::tuple::serialization; + +/// Read-only view for Tuple sketches. +/// +/// This trait is the input abstraction for APIs (such as union and intersection) that accept +/// either a mutable [`UpdatableTupleSketch`] or an immutable [`CompactTupleSketch`]. `S` is the +/// summary type retained by the sketch. +/// +/// It is blanket-implemented for every [`RawThetaSketchView`] over [`TupleEntry`], so custom +/// sketch-like inputs can be supplied by implementing that trait. +pub trait TupleSketchView<S>: RawThetaSketchView<TupleEntry<S>> {} + +impl<S, T> TupleSketchView<S> for T where T: RawThetaSketchView<TupleEntry<S>> {} + +/// Mutable Tuple sketch for building from input data. +/// +/// `S` is the summary type retained alongside each key, and `P` is the [`SummaryUpdatePolicy`] that +/// defines how summaries are created and updated. For additive summaries the default +/// [`DefaultUpdatePolicy`] is used. +/// +/// # Examples +/// +/// ``` +/// # use datasketches::tuple::UpdatableTupleSketch; +/// let mut sketch = UpdatableTupleSketch::<u64>::builder().build(); +/// sketch.update("apple", 1); +/// sketch.update("apple", 1); +/// assert!(sketch.estimate() >= 1.0); +/// assert_eq!(sketch.num_retained(), 1); +/// ``` +#[derive(Debug)] +pub struct UpdatableTupleSketch<S, P = DefaultUpdatePolicy> { Review Comment: UpdatableTupleSketch -> TupleSketch ########## datasketches/src/tuple/policy.rs: ########## @@ -0,0 +1,108 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Policies describing how summaries are created, updated, and combined. +//! +//! A Tuple sketch keeps a user-defined summary `S` next to every retained key. The behavior of a +//! summary is supplied externally through policy objects rather than baked into the summary type +//! itself, so the same summary type (for example a plain `u64` or a `Vec<f64>`) can be driven by +//! different behaviors and can carry per-instance configuration (such as the number of values in an +//! array-of-doubles summary). +//! Review Comment: > //! //! This mirrors the policy approach used by the C++ implementation //! (`default_tuple_update_policy`, `default_tuple_union_policy`) and the Java //! `SummaryFactory` / `SummarySetOperations` interfaces. Not sure whether it's need. ########## datasketches/src/tuple/hash_table.rs: ########## @@ -0,0 +1,480 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use std::hash::Hash; +use std::num::NonZeroU64; + +use crate::thetacommon::RawHashTableEntry; +use crate::thetacommon::hash_table::RawHashTable; + +/// A retained entry in a Tuple sketch: a hash key together with its associated summary. +/// +/// The hash is stored as [`NonZeroU64`] (hash 0 is screened out before insertion), so +/// `Option<TupleEntry<S>>` keeps the niche and takes no more space than `TupleEntry<S>` itself — +/// the same layout the Theta table gets from its `NonZeroU64` entry. +#[derive(Debug, Clone)] +pub struct TupleEntry<S> { + hash: NonZeroU64, + summary: S, +} + +impl<S> TupleEntry<S> { + /// Creates an entry from a hash known to be non-zero. + /// + /// # Panics + /// + /// Panics if `hash` is zero. + pub(crate) fn new(hash: u64, summary: S) -> Self { + let hash = NonZeroU64::new(hash).expect("hash must be non-zero"); + Self { hash, summary } + } + + /// Return the hash used as this entry's key. + pub fn hash(&self) -> u64 { + self.hash.get() + } + + /// Returns the summary stored in this entry. + pub fn summary(&self) -> &S { + &self.summary + } + + /// Splits this entry into its `(hash, summary)` parts. + pub(super) fn into_parts(self) -> (u64, S) { + (self.hash.get(), self.summary) + } +} + +/// Specific hash table for tuple sketch. +/// +/// This is the Theta sketch hash table extended so that each retained key carries a user-defined +/// summary. It maintains an array with capacity up to 2^lg_max_size: +/// * Before it reaches the max capacity, it will extend the array based on resize_factor. +/// * After it reaches the capacity bigger than 2^lg_nom_size, every time the number of entries +/// exceeds the threshold, it will rebuild the table: only keep the min 2^lg_nom_size entries and +/// update the theta to the k-th smallest entry. +/// +/// Unlike the Theta hash table, when a key is inserted that already exists, the incoming update is +/// merged into the existing summary rather than discarded. +pub(super) type TupleHashTable<S> = RawHashTable<TupleEntry<S>>; + +impl<S> RawHashTableEntry for TupleEntry<S> { + fn hash(&self) -> u64 { + self.hash.get() + } +} + +impl<S> TupleHashTable<S> { + /// Hashes a key and inserts or updates its summary via a single callback. + /// + /// See [`upsert`](Self::upsert) for the callback contract. Returns true if a new entry was + /// created, false if the key already existed or the hash was screened out by theta. + pub fn update<T, F>(&mut self, key: T, f: F) -> bool Review Comment: How about named it in consistent way as theta: 1. try_insert 2. try_insert_hash ########## datasketches/src/tuple/hash_table.rs: ########## @@ -0,0 +1,480 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use std::hash::Hash; +use std::num::NonZeroU64; + +use crate::thetacommon::RawHashTableEntry; +use crate::thetacommon::hash_table::RawHashTable; + +/// A retained entry in a Tuple sketch: a hash key together with its associated summary. +/// +/// The hash is stored as [`NonZeroU64`] (hash 0 is screened out before insertion), so +/// `Option<TupleEntry<S>>` keeps the niche and takes no more space than `TupleEntry<S>` itself — +/// the same layout the Theta table gets from its `NonZeroU64` entry. +#[derive(Debug, Clone)] +pub struct TupleEntry<S> { + hash: NonZeroU64, + summary: S, +} + +impl<S> TupleEntry<S> { + /// Creates an entry from a hash known to be non-zero. + /// + /// # Panics + /// + /// Panics if `hash` is zero. + pub(crate) fn new(hash: u64, summary: S) -> Self { + let hash = NonZeroU64::new(hash).expect("hash must be non-zero"); + Self { hash, summary } + } + + /// Return the hash used as this entry's key. + pub fn hash(&self) -> u64 { + self.hash.get() + } + + /// Returns the summary stored in this entry. + pub fn summary(&self) -> &S { + &self.summary + } + + /// Splits this entry into its `(hash, summary)` parts. + pub(super) fn into_parts(self) -> (u64, S) { + (self.hash.get(), self.summary) + } +} + +/// Specific hash table for tuple sketch. +/// +/// This is the Theta sketch hash table extended so that each retained key carries a user-defined +/// summary. It maintains an array with capacity up to 2^lg_max_size: +/// * Before it reaches the max capacity, it will extend the array based on resize_factor. +/// * After it reaches the capacity bigger than 2^lg_nom_size, every time the number of entries +/// exceeds the threshold, it will rebuild the table: only keep the min 2^lg_nom_size entries and +/// update the theta to the k-th smallest entry. +/// +/// Unlike the Theta hash table, when a key is inserted that already exists, the incoming update is +/// merged into the existing summary rather than discarded. +pub(super) type TupleHashTable<S> = RawHashTable<TupleEntry<S>>; + +impl<S> RawHashTableEntry for TupleEntry<S> { + fn hash(&self) -> u64 { + self.hash.get() + } +} + +impl<S> TupleHashTable<S> { + /// Hashes a key and inserts or updates its summary via a single callback. + /// + /// See [`upsert`](Self::upsert) for the callback contract. Returns true if a new entry was + /// created, false if the key already existed or the hash was screened out by theta. + pub fn update<T, F>(&mut self, key: T, f: F) -> bool + where + T: Hash, + F: FnOnce(Option<&mut S>) -> Option<S>, + { + let hash = self.hash(key); + self.upsert(hash, f) + } + + /// Inserts or updates the summary slot for a pre-hashed key. + /// + /// The callback `f` is invoked with the current summary for `hash`: Review Comment: This contract comment here looks more appropriate in `RawHashTbale::upsert_entry` ########## datasketches/src/tuple/hash_table.rs: ########## @@ -0,0 +1,480 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use std::hash::Hash; +use std::num::NonZeroU64; + +use crate::thetacommon::RawHashTableEntry; +use crate::thetacommon::hash_table::RawHashTable; + +/// A retained entry in a Tuple sketch: a hash key together with its associated summary. +/// +/// The hash is stored as [`NonZeroU64`] (hash 0 is screened out before insertion), so +/// `Option<TupleEntry<S>>` keeps the niche and takes no more space than `TupleEntry<S>` itself — +/// the same layout the Theta table gets from its `NonZeroU64` entry. +#[derive(Debug, Clone)] +pub struct TupleEntry<S> { + hash: NonZeroU64, + summary: S, +} + +impl<S> TupleEntry<S> { + /// Creates an entry from a hash known to be non-zero. + /// + /// # Panics + /// + /// Panics if `hash` is zero. + pub(crate) fn new(hash: u64, summary: S) -> Self { + let hash = NonZeroU64::new(hash).expect("hash must be non-zero"); + Self { hash, summary } + } + + /// Return the hash used as this entry's key. + pub fn hash(&self) -> u64 { + self.hash.get() + } + + /// Returns the summary stored in this entry. + pub fn summary(&self) -> &S { + &self.summary + } + + /// Splits this entry into its `(hash, summary)` parts. + pub(super) fn into_parts(self) -> (u64, S) { + (self.hash.get(), self.summary) + } +} + +/// Specific hash table for tuple sketch. +/// +/// This is the Theta sketch hash table extended so that each retained key carries a user-defined +/// summary. It maintains an array with capacity up to 2^lg_max_size: +/// * Before it reaches the max capacity, it will extend the array based on resize_factor. +/// * After it reaches the capacity bigger than 2^lg_nom_size, every time the number of entries +/// exceeds the threshold, it will rebuild the table: only keep the min 2^lg_nom_size entries and +/// update the theta to the k-th smallest entry. +/// +/// Unlike the Theta hash table, when a key is inserted that already exists, the incoming update is +/// merged into the existing summary rather than discarded. +pub(super) type TupleHashTable<S> = RawHashTable<TupleEntry<S>>; Review Comment: > It maintains an array with capacity up to 2^lg_max_size: /// * Before it reaches the max capacity, it will extend the array based on resize_factor. /// * After it reaches the capacity bigger than 2^lg_nom_size, every time the number of entries /// exceeds the threshold, it will rebuild the table: only keep the min 2^lg_nom_size entries and /// update the theta to the k-th smallest entry. I think this comment may better in RawHashTable rather a specific comment in RawHashTable. We can dicard it for now in this place. ########## datasketches/src/tuple/sketch.rs: ########## @@ -0,0 +1,1020 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Tuple sketch types. +//! +//! This module provides [`UpdatableTupleSketch`] (mutable) and [`CompactTupleSketch`] (immutable), +//! the Tuple sketch analogues of the Theta sketch. Each retained key carries a user-defined summary +//! whose behavior is supplied by a [`SummaryUpdatePolicy`]. + +use std::hash::Hash; +use std::marker::PhantomData; + +use crate::codec::SketchBytes; +use crate::codec::SketchSlice; +use crate::codec::assert::ensure_preamble_longs_in_range; +use crate::codec::assert::insufficient_data; +use crate::codec::family::Family; +use crate::common::NumStdDev; +use crate::common::ResizeFactor; +use crate::error::Error; +use crate::hash::DEFAULT_UPDATE_SEED; +use crate::hash::compute_seed_hash; +use crate::thetacommon::RawThetaSketchView; +use crate::thetacommon::binomial_bounds; +use crate::thetacommon::constants::DEFAULT_LG_K; +use crate::thetacommon::constants::FLAGS_IS_COMPACT; +use crate::thetacommon::constants::FLAGS_IS_EMPTY; +use crate::thetacommon::constants::FLAGS_IS_ORDERED; +use crate::thetacommon::constants::FLAGS_IS_READ_ONLY; +use crate::thetacommon::constants::MAX_LG_K; +use crate::thetacommon::constants::MAX_THETA; +use crate::thetacommon::constants::MIN_LG_K; +use crate::tuple::hash_table::TupleEntry; +use crate::tuple::hash_table::TupleHashTable; +use crate::tuple::policy::DefaultUpdatePolicy; +use crate::tuple::policy::SummaryUpdatePolicy; +use crate::tuple::serde::SummarySerde; +use crate::tuple::serialization; + +/// Read-only view for Tuple sketches. +/// +/// This trait is the input abstraction for APIs (such as union and intersection) that accept +/// either a mutable [`UpdatableTupleSketch`] or an immutable [`CompactTupleSketch`]. `S` is the +/// summary type retained by the sketch. +/// +/// It is blanket-implemented for every [`RawThetaSketchView`] over [`TupleEntry`], so custom +/// sketch-like inputs can be supplied by implementing that trait. +pub trait TupleSketchView<S>: RawThetaSketchView<TupleEntry<S>> {} + +impl<S, T> TupleSketchView<S> for T where T: RawThetaSketchView<TupleEntry<S>> {} + +/// Mutable Tuple sketch for building from input data. +/// +/// `S` is the summary type retained alongside each key, and `P` is the [`SummaryUpdatePolicy`] that +/// defines how summaries are created and updated. For additive summaries the default +/// [`DefaultUpdatePolicy`] is used. +/// +/// # Examples +/// +/// ``` +/// # use datasketches::tuple::UpdatableTupleSketch; +/// let mut sketch = UpdatableTupleSketch::<u64>::builder().build(); +/// sketch.update("apple", 1); +/// sketch.update("apple", 1); +/// assert!(sketch.estimate() >= 1.0); +/// assert_eq!(sketch.num_retained(), 1); +/// ``` +#[derive(Debug)] +pub struct UpdatableTupleSketch<S, P = DefaultUpdatePolicy> { + table: TupleHashTable<S>, + policy: P, +} + +impl<S> UpdatableTupleSketch<S, DefaultUpdatePolicy> { + /// Creates a new builder using the default update policy. + /// + /// # Examples + /// + /// ``` + /// # use datasketches::tuple::UpdatableTupleSketch; + /// let sketch = UpdatableTupleSketch::<u64>::builder().lg_k(12).build(); + /// assert_eq!(sketch.lg_k(), 12); + /// ``` + pub fn builder() -> UpdatableTupleSketchBuilder<S, DefaultUpdatePolicy> { + UpdatableTupleSketchBuilder::default() + } +} + +impl<S, P> UpdatableTupleSketch<S, P> { + /// Updates the sketch with a key and an update value. + /// + /// If the key is new, the policy creates a summary and folds in `value`; if the key already + /// exists, `value` is folded into the retained summary. Updates screened out by theta do not + /// change any summary. + /// + /// # Examples + /// + /// ``` + /// # use datasketches::tuple::UpdatableTupleSketch; + /// let mut sketch = UpdatableTupleSketch::<u64>::builder().build(); + /// sketch.update(42, 5); + /// ``` + pub fn update<U>(&mut self, key: impl Hash, value: U) + where + P: SummaryUpdatePolicy<S, U>, + { + let policy = &self.policy; + self.table.update(key, |existing| match existing { + Some(summary) => { + policy.update(summary, value); + None + } + None => { + let mut summary = policy.create(); + policy.update(&mut summary, value); + Some(summary) + } + }); + } + + /// Returns the cardinality (distinct key count) estimate. + pub fn estimate(&self) -> f64 { + if self.is_empty() { + return 0.0; + } + let num_retained = self.table.num_retained() as f64; + let theta = self.table.theta() as f64 / MAX_THETA as f64; + num_retained / theta + } + + /// Returns theta as a fraction (0.0 to 1.0). + pub fn theta(&self) -> f64 { + self.table.theta() as f64 / MAX_THETA as f64 + } + + /// Returns theta as `u64`. + pub fn theta64(&self) -> u64 { + self.table.theta() + } + + /// Returns the 16-bit seed hash. + pub fn seed_hash(&self) -> u16 { + self.table.seed_hash() + } + + /// Returns true if the sketch is empty. + pub fn is_empty(&self) -> bool { + self.table.is_empty() + } + + /// Returns true if the sketch is in estimation mode. + pub fn is_estimation_mode(&self) -> bool { + self.table.theta() < MAX_THETA + } + + /// Returns the number of retained entries. + pub fn num_retained(&self) -> usize { + self.table.num_retained() + } + + /// Returns lg_k (log2 of the nominal size k). + pub fn lg_k(&self) -> u8 { + self.table.lg_nom_size() + } + + /// Trims the sketch to the nominal size k. + pub fn trim(&mut self) { + self.table.trim(); + } + + /// Resets the sketch to the empty state. + pub fn reset(&mut self) { + self.table.reset(); + } + + /// Returns an iterator over retained entries as `(hash, &summary)` pairs. + pub fn iter(&self) -> impl Iterator<Item = (u64, &S)> + '_ { + self.table.iter() + } + + /// Returns the approximate lower error bound given the number of standard deviations. + pub fn lower_bound(&self, num_std_dev: NumStdDev) -> f64 { + if !self.is_estimation_mode() { + return self.num_retained() as f64; + } + binomial_bounds::lower_bound(self.num_retained() as u64, self.theta(), num_std_dev) + .expect("theta should always be valid") + } + + /// Returns the approximate upper error bound given the number of standard deviations. + pub fn upper_bound(&self, num_std_dev: NumStdDev) -> f64 { + if !self.is_estimation_mode() { + return self.num_retained() as f64; + } + binomial_bounds::upper_bound( + self.num_retained() as u64, + self.theta(), + num_std_dev, + self.is_empty(), + ) + .expect("theta should always be valid") + } + + /// Returns the estimated size of the sketch in bytes. + pub fn estimated_size(&self) -> usize { + std::mem::size_of::<Self>() + self.table.estimated_size() + } +} + +impl<S: Clone, P> UpdatableTupleSketch<S, P> { + /// Returns this sketch in compact (immutable) form. + /// + /// If `ordered` is true, retained entries are sorted by hash in ascending order. + /// + /// # Examples + /// + /// ``` + /// # use datasketches::tuple::UpdatableTupleSketch; + /// let mut sketch = UpdatableTupleSketch::<u64>::builder().build(); + /// sketch.update("apple", 1); + /// let compact = sketch.compact(true); + /// assert_eq!(compact.num_retained(), 1); + /// ``` + pub fn compact(&self, ordered: bool) -> CompactTupleSketch<S> { + let parts = self.table.to_compact_parts(ordered); + CompactTupleSketch::from_parts( + parts + .entries + .into_iter() + .map(TupleEntry::into_parts) + .collect(), + parts.theta, + parts.seed_hash, + parts.ordered, + parts.empty, + ) + } +} + +impl<S: Clone, P> RawThetaSketchView<TupleEntry<S>> for UpdatableTupleSketch<S, P> { + fn seed_hash(&self) -> u16 { + self.table.seed_hash() + } + + fn theta(&self) -> u64 { + self.table.theta() + } + + fn is_empty(&self) -> bool { + self.table.is_empty() + } + + fn is_ordered(&self) -> bool { + false + } + + fn iter(&self) -> impl Iterator<Item = TupleEntry<S>> + '_ { + self.table + .iter() + .map(|(hash, summary)| TupleEntry::new(hash, summary.clone())) + } + + fn num_retained(&self) -> usize { + self.table.num_retained() + } +} + +/// Compact (immutable) Tuple sketch. +/// +/// This is the serialization-friendly form: a compact array of `(hash, summary)` entries plus theta +/// and a 16-bit seed hash. It can be ordered (sorted ascending by hash) or unordered. +#[derive(Clone, Debug)] +pub struct CompactTupleSketch<S> { + entries: Vec<(u64, S)>, Review Comment: Why not use `Vec<TupleEntry<S>>` direcly. ########## datasketches/src/tuple/policy.rs: ########## @@ -0,0 +1,108 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Policies describing how summaries are created, updated, and combined. +//! +//! A Tuple sketch keeps a user-defined summary `S` next to every retained key. The behavior of a +//! summary is supplied externally through policy objects rather than baked into the summary type +//! itself, so the same summary type (for example a plain `u64` or a `Vec<f64>`) can be driven by +//! different behaviors and can carry per-instance configuration (such as the number of values in an +//! array-of-doubles summary). +//! +//! This mirrors the policy approach used by the C++ implementation +//! (`default_tuple_update_policy`, `default_tuple_union_policy`) and the Java +//! `SummaryFactory` / `SummarySetOperations` interfaces. + +use std::ops::AddAssign; + +/// Defines how a summary is created and how update values are folded into it. +/// +/// This is used by the update tuple sketch. `S` is the stored summary type and `U` is the type of +/// the update value, which may be a borrowed type such as `&[f64]`. +/// +/// Corresponds to C++ `default_tuple_update_policy<Summary, Update>` and Java +/// `UpdatableSummary<U>` together with `SummaryFactory`. Review Comment: > /// Corresponds to C++ `default_tuple_update_policy<Summary, Update>` and Java /// `UpdatableSummary<U>` together with `SummaryFactory`. Not sure whether it's need. It's easy to be inconsistent across different language. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
