Struct hyperloglogplus::HyperLogLogPlus
source · [−]pub struct HyperLogLogPlus<H, B> where
H: Hash + ?Sized,
B: BuildHasher, { /* private fields */ }
Expand description
Implements the HyperLogLog++ algorithm for cardinality estimation.
This implementation is based on the paper:
HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm.
- Uses 6-bit registers, packed in a 32-bit unsigned integer. Thus, every five registers 2 bits are not used.
- In small cardinalities, a sparse representation is used which allows for higher precision in estimations.
- Performs bias correction using the empirical data provided by Google (can be found here).
- Supports serialization/deserialization through
serde
.
Examples
use std::collections::hash_map::RandomState;
use hyperloglogplus::{HyperLogLog, HyperLogLogPlus};
let mut hllp: HyperLogLogPlus<u32, _> =
HyperLogLogPlus::new(16, RandomState::new()).unwrap();
hllp.insert(&12345);
hllp.insert(&23456);
assert_eq!(hllp.count().trunc() as u32, 2);
References
- “HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm”, Philippe Flajolet, Éric Fusy, Olivier Gandouet and Frédéric Meunier.
- “HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm”, Stefan Heule, Marc Nunkesser and Alexander Hall.
- “Appendix to HyperLogLog in Practice: Algorithmic Engineering of a State of the Art Cardinality Estimation Algorithm”, Stefan Heule, Marc Nunkesser and Alexander Hall.
Implementations
sourceimpl<H, B> HyperLogLogPlus<H, B> where
H: Hash + ?Sized,
B: BuildHasher,
impl<H, B> HyperLogLogPlus<H, B> where
H: Hash + ?Sized,
B: BuildHasher,
sourcepub fn new(precision: u8, builder: B) -> Result<Self, HyperLogLogError>
pub fn new(precision: u8, builder: B) -> Result<Self, HyperLogLogError>
Creates a new HyperLogLogPlus instance.
sourcepub fn merge<S, T>(
&mut self,
other: &HyperLogLogPlus<S, T>
) -> Result<(), HyperLogLogError> where
S: Hash + ?Sized,
T: BuildHasher,
pub fn merge<S, T>(
&mut self,
other: &HyperLogLogPlus<S, T>
) -> Result<(), HyperLogLogError> where
S: Hash + ?Sized,
T: BuildHasher,
Merges the other
HyperLogLogPlus instance into self
.
Both sketches must have the same precision. Merge can trigger the transition from sparse to normal representation.
sourcepub fn insert_any<R>(&mut self, value: &R) where
R: Hash + ?Sized,
pub fn insert_any<R>(&mut self, value: &R) where
R: Hash + ?Sized,
Inserts a new value, of any type, to the multiset.
Trait Implementations
sourceimpl<H: Clone, B: Clone> Clone for HyperLogLogPlus<H, B> where
H: Hash + ?Sized,
B: BuildHasher,
impl<H: Clone, B: Clone> Clone for HyperLogLogPlus<H, B> where
H: Hash + ?Sized,
B: BuildHasher,
sourcefn clone(&self) -> HyperLogLogPlus<H, B>
fn clone(&self) -> HyperLogLogPlus<H, B>
Returns a copy of the value. Read more
1.0.0 · sourcefn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from source
. Read more
sourceimpl<H: Debug, B: Debug> Debug for HyperLogLogPlus<H, B> where
H: Hash + ?Sized,
B: BuildHasher,
impl<H: Debug, B: Debug> Debug for HyperLogLogPlus<H, B> where
H: Hash + ?Sized,
B: BuildHasher,
sourceimpl<'de, H, B> Deserialize<'de> for HyperLogLogPlus<H, B> where
H: Hash + ?Sized,
B: BuildHasher,
B: Deserialize<'de>,
impl<'de, H, B> Deserialize<'de> for HyperLogLogPlus<H, B> where
H: Hash + ?Sized,
B: BuildHasher,
B: Deserialize<'de>,
sourcefn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
__D: Deserializer<'de>,
fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
__D: Deserializer<'de>,
Deserialize this value from the given Serde deserializer. Read more
sourceimpl<H, B> HyperLogLog<H> for HyperLogLogPlus<H, B> where
H: Hash + ?Sized,
B: BuildHasher,
impl<H, B> HyperLogLog<H> for HyperLogLogPlus<H, B> where
H: Hash + ?Sized,
B: BuildHasher,
sourceimpl<H, B> Serialize for HyperLogLogPlus<H, B> where
H: Hash + ?Sized,
B: BuildHasher,
B: Serialize,
impl<H, B> Serialize for HyperLogLogPlus<H, B> where
H: Hash + ?Sized,
B: BuildHasher,
B: Serialize,
Auto Trait Implementations
impl<H: ?Sized, B> RefUnwindSafe for HyperLogLogPlus<H, B> where
B: RefUnwindSafe,
H: RefUnwindSafe,
impl<H: ?Sized, B> Send for HyperLogLogPlus<H, B> where
B: Send,
H: Send,
impl<H: ?Sized, B> Sync for HyperLogLogPlus<H, B> where
B: Sync,
H: Sync,
impl<H: ?Sized, B> Unpin for HyperLogLogPlus<H, B> where
B: Unpin,
H: Unpin,
impl<H: ?Sized, B> UnwindSafe for HyperLogLogPlus<H, B> where
B: UnwindSafe,
H: UnwindSafe,
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more