Struct hyperloglog_rs::hyperloglog::HyperLogLog
source · pub struct HyperLogLog<P: Precision + WordType<BITS>, const BITS: usize> { /* private fields */ }
Expand description
A probabilistic algorithm for estimating the number of distinct elements in a set.
HyperLogLog is a probabilistic algorithm designed to estimate the number of distinct elements in a set. It does so by taking advantage of the fact that the representation of an element can be transformed into a uniform distribution in a space with a fixed range.
HyperLogLog works by maintaining a fixed-sized register array, where each register holds a counter. The algorithm splits the input set into subsets, applies a hash function to each element in the subset, and then updates the corresponding counter in the register array.
HyperLogLog uses a trick called “probabilistic counting” to estimate the number of distinct elements in the set. Each register counter is converted to a binary string, and the algorithm counts the number of leading zeros in each binary string. The maximum number of leading zeros over all counters is used to estimate the number of distinct elements in the set.
HyperLogLog has a tunable parameter called precision that determines the accuracy of the algorithm. Higher precision leads to better accuracy, but requires more memory. The error rate of the algorithm is guaranteed to be within a certain bound, depending on the chosen precision.
Examples
use hyperloglog_rs::prelude::*;
let mut hll = HyperLogLog::<Precision12, 6>::default();
hll.insert(&"apple");
hll.insert(&"banana");
hll.insert(&"cherry");
let estimated_cardinality = hll.estimate_cardinality();
assert!(estimated_cardinality >= 3.0_f32 * 0.9 &&
estimated_cardinality <= 3.0_f32 * 1.1);
Citations
This implementation is based on the following papers:
- Flajolet, Philippe, et al. “HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm.” DMTCS Proceedings 1 (2007): 127-146.
- Heule, Stefan, Marc Nunkesser, and Alexander Hall. “HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm.” Proceedings of the 16th International Conference on Extending Database Technology. 2013.
Implementations§
source§impl<P: Precision + WordType<BITS>, const BITS: usize> HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize> HyperLogLog<P, BITS>
sourcepub fn from_words(words: &P::Words) -> Self
pub fn from_words(words: &P::Words) -> Self
Create a new HyperLogLog counter from an array of words.
Arguments
words
- An array of u64 words to use for the HyperLogLog counter.
Returns
A new HyperLogLog counter initialized with the given words.
Examples
use hyperloglog_rs::prelude::*;
let words = [0_u32; 4];
let hll = HyperLogLog::<Precision4, 6>::from_words(&words);
assert_eq!(hll.len(), 16);
sourcepub fn from_registers(registers: &[u32]) -> Self
pub fn from_registers(registers: &[u32]) -> Self
Create a new HyperLogLog counter from an array of registers.
Arguments
registers
- An array of u32 registers to use for the HyperLogLog counter.
Returns
A new HyperLogLog counter initialized with the given registers.
Examples
use hyperloglog_rs::prelude::*;
let registers = [0_u32; 1 << 4];
let hll = HyperLogLog::<Precision4, 6>::from_registers(®isters);
assert_eq!(hll.len(), 1 << 4);
sourcepub fn insert<T: Hash>(&mut self, rhs: T) -> bool
pub fn insert<T: Hash>(&mut self, rhs: T) -> bool
Adds an element to the HyperLogLog counter, and returns whether the counter has changed.
Arguments
rhs
- The element to add.
Examples
use hyperloglog_rs::prelude::*;
let mut hll = HyperLogLog::<Precision10, 6>::default();
hll.insert("Hello");
hll.insert("World");
assert!(hll.estimate_cardinality() >= 2.0);
Performance
The performance of this function depends on the size of the HyperLogLog counter (N
), the number
of distinct elements in the input, and the hash function used to hash elements. For a given value of N
,
the function has an average time complexity of O(1) and a worst-case time complexity of O(log N).
However, the actual time complexity may vary depending on the distribution of the hashed elements.
Errors
This function does not return any errors.
Trait Implementations§
source§impl<P: Precision + WordType<BITS>, const BITS: usize> BitAnd<&HyperLogLog<P, BITS>> for HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize> BitAnd<&HyperLogLog<P, BITS>> for HyperLogLog<P, BITS>
source§fn bitand(self, rhs: &Self) -> Self
fn bitand(self, rhs: &Self) -> Self
Computes the intersection between two HyperLogLog counters of the same precision and number of bits per register.
Caveats
Please be advised that HLL are not designed to compute intersections such as the one estimated by this operation. The resulting set will most likely be an overestimation of the real intersection. Operate with caution.
Implementation details
This operation is implemented by computing the minimum register-wise of the two HLL counters. This results in an estimation of the intersection because we obtain a new HLL counter that at most contain the elements present in both HLL counters.
Example
let mut hll1 = HyperLogLog::<Precision14, 5>::default();
hll1.insert(&1);
hll1.insert(&2);
let mut hll2 = HyperLogLog::<Precision14, 5>::default();
hll2.insert(&2);
hll2.insert(&3);
let hll_intersection = hll1 | hll2;
assert!(hll_intersection.estimate_cardinality() >= 3.0_f32 * 0.9 &&
hll_intersection.estimate_cardinality() <= 3.0_f32 * 1.1);
Merging a set with an empty set should not change the cardinality.
let mut hll1 = HyperLogLog::<Precision14, 5>::default();
hll1.insert(&1);
hll1.insert(&2);
let hll_intersection = hll1.clone() | HyperLogLog::<Precision14, 5>::default();
assert_eq!(
hll_intersection,
hll1,
concat!(
"The cardinality of the intersection should ",
"be the same as the cardinality of the first set."
)
);
We can create the HLL counters from array from registers, so to be able to check that everything works as expected.
let first_registers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
let second_registers = [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 19];
let expected = [9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 11, 12, 13, 14, 15, 19];
let mut hll1 = HyperLogLog::<Precision4, 5>::from_registers(&first_registers);
let mut hll2 = HyperLogLog::<Precision4, 5>::from_registers(&second_registers);
let intersection = hll1 | &hll2;
assert_eq!(intersection.get_registers(), expected, "The registers are not the expected ones, got {:?} instead of {:?}.", intersection.get_registers(), expected);
§type Output = HyperLogLog<P, BITS>
type Output = HyperLogLog<P, BITS>
&
operator.source§impl<P: Precision + WordType<BITS>, const BITS: usize> BitAnd for HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize> BitAnd for HyperLogLog<P, BITS>
source§fn bitand(self, rhs: Self) -> Self
fn bitand(self, rhs: Self) -> Self
Computes the intersection between two HyperLogLog counters of the same precision and number of bits per register.
Caveats
Please be advised that HLL are not designed to compute intersections such as the one estimated by this operation. The resulting set will most likely be an overestimation of the real intersection. Operate with caution.
Implementation details
This operation is implemented by computing the minimum register-wise of the two HLL counters. This results in an estimation of the intersection because we obtain a new HLL counter that at most contain the elements present in both HLL counters.
Example
let mut hll1 = HyperLogLog::<Precision14, 5>::default();
hll1.insert(&1);
hll1.insert(&2);
let mut hll2 = HyperLogLog::<Precision14, 5>::default();
hll2.insert(&2);
hll2.insert(&3);
let hll_intersection = hll1 & hll2;
assert!(hll_intersection.estimate_cardinality() >= 1.0_f32 * 0.9 &&
hll_intersection.estimate_cardinality() <= 1.0_f32 * 1.1);
Executing the intersection between a set and an empty set should result in an empty set.
let mut hll1 = HyperLogLog::<Precision14, 5>::default();
hll1.insert(&1);
hll1.insert(&2);
let hll_intersection = hll1.clone() & HyperLogLog::<Precision14, 5>::default();
assert_eq!(
HyperLogLog::<Precision14, 5>::default(),
hll_intersection,
concat!(
"The cardinality of the intersection should ",
"be the same as the empty test."
)
);
We can create the HLL counters from array from registers, so to be able to check that everything works as expected.
let first_registers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
let second_registers = [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 19];
let expected = [9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 11, 12, 13, 14, 15, 19];
let mut hll1 = HyperLogLog::<Precision4, 5>::from_registers(&first_registers);
let mut hll2 = HyperLogLog::<Precision4, 5>::from_registers(&second_registers);
let intersection = hll1 | hll2;
assert_eq!(intersection.get_registers(), expected, "The registers are not the expected ones, got {:?} instead of {:?}.", intersection.get_registers(), expected);
§type Output = HyperLogLog<P, BITS>
type Output = HyperLogLog<P, BITS>
&
operator.source§impl<P: Precision + WordType<BITS>, const BITS: usize> BitAndAssign<&HyperLogLog<P, BITS>> for HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize> BitAndAssign<&HyperLogLog<P, BITS>> for HyperLogLog<P, BITS>
source§fn bitand_assign(&mut self, rhs: &Self)
fn bitand_assign(&mut self, rhs: &Self)
Computes intersection between HLL counters.
Caveats
Please be advised that HLL are not designed to compute intersections such as the one estimated by this operation. The resulting set will most likely be an overestimation of the real intersection. Operate with caution.
Implementation details
This operation is implemented by computing the minimum register-wise of the two HLL counters. This results in an estimation of the intersection because we obtain a new HLL counter that at most contain the elements present in both HLL counters.
Example
let mut hll = HyperLogLog::<Precision8, 6>::default();
hll.insert(1u8);
let mut hll2 = HyperLogLog::<Precision8, 6>::default();
hll2.insert(2u8);
hll.bitand_assign(&hll2);
assert!(hll.estimate_cardinality() < 0.1, "The cardinality is {}, we were expecting 0.", hll.estimate_cardinality());
let mut hll = HyperLogLog::<Precision8, 6>::default();
hll.insert(1u8);
let mut hll2 = HyperLogLog::<Precision8, 6>::default();
hll2.insert(1u8);
hll.bitand_assign(&hll2);
assert!(hll.estimate_cardinality() > 1.0 - 0.1, "The cardinality is {}, we were expecting 1.", hll.estimate_cardinality());
assert!(hll.estimate_cardinality() < 1.0 + 0.1, "The cardinality is {}, we were expecting 1.", hll.estimate_cardinality());
let mut hll3 = HyperLogLog::<Precision16, 6>::default();
hll3.insert(3u8);
hll3.insert(5u8);
hll3.insert(6u8);
let mut hll4 = HyperLogLog::<Precision16, 6>::default();
hll4.insert(5u8);
hll4.insert(6u8);
hll3.bitand_assign(&hll4);
assert!(hll3.estimate_cardinality() > 2.0 - 0.1, "Expected a value equal to around 2, got {}", hll3.estimate_cardinality());
assert!(hll3.estimate_cardinality() < 2.0 + 0.1, "Expected a value equal to around 2, got {}", hll3.estimate_cardinality());
Another example is that, if we allocate two example vectors which we will use to populate both two sets and the two HyperLogLog counter. All elements in the intersection of the two sets must also appear in the intersection of the two HyperLogLog counters. Usually, the problem is that it may over-estimate the cardinality of the intersection.
let first_vec: Vec<u64> = vec![1, 2, 3, 4, 4, 5, 6, 6, 7, 8];
let second_vec: Vec<u64> = vec![5, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12];
let first_set = first_vec.iter().collect::<std::collections::HashSet<_>>();
let second_set = second_vec.iter().collect::<std::collections::HashSet<_>>();
let mut hll1 = HyperLogLog::<Precision8, 6>::default();
let mut hll2 = HyperLogLog::<Precision8, 6>::default();
for element in first_vec.iter() {
hll1.insert(element);
}
for element in second_vec.iter() {
hll2.insert(element);
}
let mut hll_intersection = hll1.clone();
hll_intersection &= &hll2;
let intersection = first_set.intersection(&second_set).collect::<std::collections::HashSet<_>>();
assert!(hll_intersection.estimate_cardinality() >= intersection.len() as f32 * 0.9 &&
hll_intersection.estimate_cardinality() <= intersection.len() as f32 * 1.1);
for element in intersection.iter() {
assert!(hll_intersection.may_contain(element));
}
source§impl<P: Precision + WordType<BITS>, const BITS: usize> BitAndAssign for HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize> BitAndAssign for HyperLogLog<P, BITS>
source§fn bitand_assign(&mut self, rhs: Self)
fn bitand_assign(&mut self, rhs: Self)
Computes intersection between HLL counters.
Caveats
Please be advised that HLL are not designed to compute intersections such as the one estimated by this operation. The resulting set will most likely be an overestimation of the real intersection. Operate with caution.
Implementation details
This operation is implemented by computing the minimum register-wise of the two HLL counters. This results in an estimation of the intersection because we obtain a new HLL counter that at most contain the elements present in both HLL counters.
Example
let mut hll = HyperLogLog::<Precision8, 6>::default();
hll.insert(1u8);
let mut hll2 = HyperLogLog::<Precision8, 6>::default();
hll2.insert(2u8);
hll.bitand_assign(hll2);
assert!(hll.estimate_cardinality() < 0.1, "The cardinality is {}, we were expecting 0.", hll.estimate_cardinality());
let mut hll = HyperLogLog::<Precision8, 6>::default();
hll.insert(1u8);
let mut hll2 = HyperLogLog::<Precision8, 6>::default();
hll2.insert(1u8);
hll.bitand_assign(hll2);
assert!(hll.estimate_cardinality() > 1.0 - 0.1, "The cardinality is {}, we were expecting 1.", hll.estimate_cardinality());
assert!(hll.estimate_cardinality() < 1.0 + 0.1, "The cardinality is {}, we were expecting 1.", hll.estimate_cardinality());
let mut hll3 = HyperLogLog::<Precision16, 6>::default();
hll3.insert(3u8);
hll3.insert(5u8);
let mut hll4 = HyperLogLog::<Precision16, 6>::default();
hll4.insert(5u8);
hll4.insert(6u8);
hll3.bitand_assign(hll4);
assert!(hll3.estimate_cardinality() > 1.0 - 0.1, "Expected a value equal to around 1, got {}", hll3.estimate_cardinality());
assert!(hll3.estimate_cardinality() < 1.0 + 0.1, "Expected a value equal to around 1, got {}", hll3.estimate_cardinality());
source§impl<P: Precision + WordType<BITS>, const BITS: usize> BitOr<&HyperLogLog<P, BITS>> for HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize> BitOr<&HyperLogLog<P, BITS>> for HyperLogLog<P, BITS>
source§fn bitor(self, rhs: &Self) -> Self
fn bitor(self, rhs: &Self) -> Self
Computes the union between two HyperLogLog counters of the same precision and number of bits per register.
Example
let mut hll1 = HyperLogLog::<Precision14, 5>::default();
hll1.insert(&1);
hll1.insert(&2);
let mut hll2 = HyperLogLog::<Precision14, 5>::default();
hll2.insert(&2);
hll2.insert(&3);
let hll_union = hll1 | hll2;
assert!(hll_union.estimate_cardinality() >= 3.0_f32 * 0.9 &&
hll_union.estimate_cardinality() <= 3.0_f32 * 1.1);
Merging a set with an empty set should not change the cardinality.
let mut hll1 = HyperLogLog::<Precision14, 5>::default();
hll1.insert(&1);
hll1.insert(&2);
let hll_union = hll1.clone() | HyperLogLog::<Precision14, 5>::default();
assert_eq!(
hll_union,
hll1,
concat!(
"The cardinality of the union should ",
"be the same as the cardinality of the first set."
)
);
We can create the HLL counters from array from registers, so to be able to check that everything works as expected.
let first_registers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
let second_registers = [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 19];
let expected = [9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 11, 12, 13, 14, 15, 19];
let mut hll1 = HyperLogLog::<Precision4, 5>::from_registers(&first_registers);
let mut hll2 = HyperLogLog::<Precision4, 5>::from_registers(&second_registers);
let union = hll1 | &hll2;
assert_eq!(union.get_registers(), expected, "The registers are not the expected ones, got {:?} instead of {:?}.", union.get_registers(), expected);
§type Output = HyperLogLog<P, BITS>
type Output = HyperLogLog<P, BITS>
|
operator.source§impl<Item: Hash, I: Iterator<Item = Item>, P: Precision + WordType<BITS>, const BITS: usize> BitOr<I> for HyperLogLog<P, BITS>
impl<Item: Hash, I: Iterator<Item = Item>, P: Precision + WordType<BITS>, const BITS: usize> BitOr<I> for HyperLogLog<P, BITS>
source§impl<P: Precision + WordType<BITS>, const BITS: usize> BitOr for HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize> BitOr for HyperLogLog<P, BITS>
source§fn bitor(self, rhs: Self) -> Self
fn bitor(self, rhs: Self) -> Self
Computes the union between two HyperLogLog counters of the same precision and number of bits per register.
Example
let mut hll1 = HyperLogLog::<Precision14, 5>::default();
hll1.insert(&1);
hll1.insert(&2);
let mut hll2 = HyperLogLog::<Precision14, 5>::default();
hll2.insert(&2);
hll2.insert(&3);
let hll_union = hll1 | hll2;
assert!(hll_union.estimate_cardinality() >= 3.0_f32 * 0.9 &&
hll_union.estimate_cardinality() <= 3.0_f32 * 1.1);
Merging a set with an empty set should not change the cardinality.
let mut hll1 = HyperLogLog::<Precision14, 5>::default();
hll1.insert(&1);
hll1.insert(&2);
let hll_union = hll1.clone() | HyperLogLog::<Precision14, 5>::default();
assert_eq!(
hll_union,
hll1,
concat!(
"The cardinality of the union should ",
"be the same as the cardinality of the first set."
)
);
We can create the HLL counters from array from registers, so to be able to check that everything works as expected.
let first_registers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
let second_registers = [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 19];
let expected = [9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 11, 12, 13, 14, 15, 19];
let mut hll1 = HyperLogLog::<Precision4, 5>::from_registers(&first_registers);
let mut hll2 = HyperLogLog::<Precision4, 5>::from_registers(&second_registers);
let union = hll1 | hll2;
assert_eq!(union.get_registers(), expected, "The registers are not the expected ones, got {:?} instead of {:?}.", union.get_registers(), expected);
§type Output = HyperLogLog<P, BITS>
type Output = HyperLogLog<P, BITS>
|
operator.source§impl<P: Precision + WordType<BITS>, const BITS: usize> BitOrAssign<&HyperLogLog<P, BITS>> for HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize> BitOrAssign<&HyperLogLog<P, BITS>> for HyperLogLog<P, BITS>
source§fn bitor_assign(&mut self, rhs: &Self)
fn bitor_assign(&mut self, rhs: &Self)
Computes union between HLL counters.
let mut hll = HyperLogLog::<Precision8, 6>::default();
hll.insert(1u8);
let mut hll2 = HyperLogLog::<Precision8, 6>::default();
hll2.insert(2u8);
hll.bitor_assign(&hll2);
assert!(hll.estimate_cardinality() > 2.0 - 0.1, "The cardinality is {}, we were expecting 2.", hll.estimate_cardinality());
assert!(hll.estimate_cardinality() < 2.0 + 0.1, "The cardinality is {}, we were expecting 2.", hll.estimate_cardinality());
let mut hll = HyperLogLog::<Precision8, 6>::default();
hll.insert(1u8);
let mut hll2 = HyperLogLog::<Precision8, 6>::default();
hll2.insert(1u8);
hll.bitor_assign(&hll2);
assert!(hll.estimate_cardinality() > 1.0 - 0.1, "The cardinality is {}, we were expecting 1.", hll.estimate_cardinality());
assert!(hll.estimate_cardinality() < 1.0 + 0.1, "The cardinality is {}, we were expecting 1.", hll.estimate_cardinality());
let mut hll3 = HyperLogLog::<Precision16, 6>::default();
hll3.insert(3u8);
hll3.insert(4u8);
let mut hll4 = HyperLogLog::<Precision16, 6>::default();
hll4.insert(5u8);
hll4.insert(6u8);
hll3.bitor_assign(&hll4);
assert!(hll3.estimate_cardinality() > 4.0 - 0.1, "Expected a value equal to around 4, got {}", hll3.estimate_cardinality());
assert!(hll3.estimate_cardinality() < 4.0 + 0.1, "Expected a value equal to around 4, got {}", hll3.estimate_cardinality());
source§impl<Item: Hash, I: IntoIterator<Item = Item>, P: Precision + WordType<BITS>, const BITS: usize> BitOrAssign<I> for &mut HyperLogLog<P, BITS>
impl<Item: Hash, I: IntoIterator<Item = Item>, P: Precision + WordType<BITS>, const BITS: usize> BitOrAssign<I> for &mut HyperLogLog<P, BITS>
source§fn bitor_assign(&mut self, rhs: I)
fn bitor_assign(&mut self, rhs: I)
|=
operation. Read moresource§impl<Item: Hash, I: IntoIterator<Item = Item>, P: Precision + WordType<BITS>, const BITS: usize> BitOrAssign<I> for HyperLogLog<P, BITS>
impl<Item: Hash, I: IntoIterator<Item = Item>, P: Precision + WordType<BITS>, const BITS: usize> BitOrAssign<I> for HyperLogLog<P, BITS>
source§fn bitor_assign(&mut self, rhs: I)
fn bitor_assign(&mut self, rhs: I)
Computes inplace union between an HLL counter and an iterator.
let mut hll = HyperLogLog::<Precision8, 6>::default();
hll |= [1u8, 2u8];
assert!(hll.estimate_cardinality() > 2.0 - 0.1, "The cardinality is {}, we were expecting 2.", hll.estimate_cardinality());
assert!(hll.estimate_cardinality() < 2.0 + 0.1, "The cardinality is {}, we were expecting 2.", hll.estimate_cardinality());
hll |= [2u8, 3u8];
assert!(hll.estimate_cardinality() > 3.0 - 0.1, "Expected a value equal to around 3, got {}", hll.estimate_cardinality());
assert!(hll.estimate_cardinality() < 3.0 + 0.1, "Expected a value equal to around 3, got {}", hll.estimate_cardinality());
source§impl<P: Precision + WordType<BITS>, const BITS: usize> BitOrAssign for HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize> BitOrAssign for HyperLogLog<P, BITS>
source§fn bitor_assign(&mut self, rhs: Self)
fn bitor_assign(&mut self, rhs: Self)
Computes union between HLL counters.
let mut hll = HyperLogLog::<Precision8, 6>::default();
hll.insert(1u8);
let mut hll2 = HyperLogLog::<Precision8, 6>::default();
hll2.insert(2u8);
hll.bitor_assign(hll2);
assert!(hll.estimate_cardinality() > 2.0 - 0.1, "The cardinality is {}, we were expecting 2.", hll.estimate_cardinality());
assert!(hll.estimate_cardinality() < 2.0 + 0.1, "The cardinality is {}, we were expecting 2.", hll.estimate_cardinality());
let mut hll = HyperLogLog::<Precision8, 6>::default();
hll.insert(1u8);
let mut hll2 = HyperLogLog::<Precision8, 6>::default();
hll2.insert(1u8);
hll.bitor_assign(hll2);
assert!(hll.estimate_cardinality() > 1.0 - 0.1, "The cardinality is {}, we were expecting 1.", hll.estimate_cardinality());
assert!(hll.estimate_cardinality() < 1.0 + 0.1, "The cardinality is {}, we were expecting 1.", hll.estimate_cardinality());
let mut hll3 = HyperLogLog::<Precision16, 6>::default();
hll3.insert(3u8);
hll3.insert(4u8);
let mut hll4 = HyperLogLog::<Precision16, 6>::default();
hll4.insert(5u8);
hll4.insert(6u8);
hll3.bitor_assign(hll4);
assert!(hll3.estimate_cardinality() > 4.0 - 0.1, "Expected a value equal to around 4, got {}", hll3.estimate_cardinality());
assert!(hll3.estimate_cardinality() < 4.0 + 0.1, "Expected a value equal to around 4, got {}", hll3.estimate_cardinality());
source§impl<P: Clone + Precision + WordType<BITS>, const BITS: usize> Clone for HyperLogLog<P, BITS>
impl<P: Clone + Precision + WordType<BITS>, const BITS: usize> Clone for HyperLogLog<P, BITS>
source§fn clone(&self) -> HyperLogLog<P, BITS>
fn clone(&self) -> HyperLogLog<P, BITS>
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moresource§impl<P: Debug + Precision + WordType<BITS>, const BITS: usize> Debug for HyperLogLog<P, BITS>
impl<P: Debug + Precision + WordType<BITS>, const BITS: usize> Debug for HyperLogLog<P, BITS>
source§impl<P: Precision + WordType<BITS>, const BITS: usize> Default for HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize> Default for HyperLogLog<P, BITS>
Implements the Default trait for HyperLogLog.
HyperLogLog is a probabilistic cardinality estimator that uses a fixed amount of memory to estimate the number of distinct elements in a set.
Examples
let hll: HyperLogLog<Precision10, 6> = Default::default();
assert_eq!(hll.len(), 1024);
source§impl<'de, P: Precision + WordType<BITS>, const BITS: usize> Deserialize<'de> for HyperLogLog<P, BITS>
impl<'de, P: Precision + WordType<BITS>, const BITS: usize> Deserialize<'de> for HyperLogLog<P, BITS>
source§fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error>
fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error>
Deserializes the HyperLogLog counter using the given deserializer.
This method is part of the Deserialize
trait implementation for the HyperLogLog struct,
allowing the counter to be deserialized from a format supported by the deserializer.
Arguments
deserializer
: The deserializer used to deserialize the HyperLogLog counter.
Returns
The deserialization result, indicating success or failure.
Example
use serde::de::Deserialize;
use serde_json::Deserializer;
use hyperloglog_rs::prelude::*;
let words = [0, 0, 0, 0, 5, 0, 4, 0, 0, 3, 0, 0, 0];
let words_str = "[0, 0, 0, 0, 5, 0, 4, 0, 0, 3, 0, 0, 0]";
let mut deserializer = Deserializer::from_str(words_str);
let result = HyperLogLog::<Precision6, 6>::deserialize(&mut deserializer);
assert!(result.is_ok(), "Deserialization failed, error: {:?}", result.err());
let hll = result.unwrap();
hll.get_words().iter().zip(words.iter()).for_each(|(a, b)| assert_eq!(a, b, "Deserialized words do not match, expected: {}, actual: {}", b, a));
source§impl<P: Precision + WordType<BITS>, const BITS: usize> From<HyperLogLog<P, BITS>> for HyperLogLogWithMultiplicities<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize> From<HyperLogLog<P, BITS>> for HyperLogLogWithMultiplicities<P, BITS>
source§fn from(hll: HyperLogLog<P, BITS>) -> Self
fn from(hll: HyperLogLog<P, BITS>) -> Self
source§impl<P: Precision + WordType<BITS>, const BITS: usize> From<HyperLogLogWithMultiplicities<P, BITS>> for HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize> From<HyperLogLogWithMultiplicities<P, BITS>> for HyperLogLog<P, BITS>
source§fn from(hll: HyperLogLogWithMultiplicities<P, BITS>) -> Self
fn from(hll: HyperLogLogWithMultiplicities<P, BITS>) -> Self
source§impl<P: Precision + WordType<BITS>, const BITS: usize, T: Hash> From<T> for HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize, T: Hash> From<T> for HyperLogLog<P, BITS>
source§fn from(value: T) -> Self
fn from(value: T) -> Self
Create a new HyperLogLog counter from a value.
This method creates a new empty HyperLogLog counter and inserts the hash
of the given value into it. The value can be any type that implements
the Hash
trait.
Examples
let hll = HyperLogLog::<Precision14, 5>::from("test");
assert!(hll.estimate_cardinality() >= 1.0_f32);
assert!(!hll.is_empty());
assert!(hll.may_contain(&"test"));
source§impl<P: Precision + WordType<BITS>, const BITS: usize, A: Hash> FromIterator<A> for HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize, A: Hash> FromIterator<A> for HyperLogLog<P, BITS>
source§fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self
fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self
Creates a new HyperLogLog counter and adds all elements from an iterator to it.
Examples
use hyperloglog_rs::prelude::*;
let data = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
let hll: HyperLogLog<Precision12, 5> = data.iter().collect();
assert!(
hll.estimate_cardinality() > 0.9 * data.len() as f32,
concat!(
"The estimate is too low, expected ",
"at least {}, got {}",
),
0.9 * data.len() as f32,
hll.estimate_cardinality()
);
assert!(
hll.estimate_cardinality() < 1.1 * data.len() as f32,
concat!(
"The estimate is too high, expected ",
"at most {}, got {}",
),
1.1 * data.len() as f32,
hll.estimate_cardinality()
);
source§impl<P: Precision + WordType<BITS>, const BITS: usize> HyperLogLogTrait<P, BITS> for HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize> HyperLogLogTrait<P, BITS> for HyperLogLog<P, BITS>
source§fn get_number_of_zero_registers(&self) -> usize
fn get_number_of_zero_registers(&self) -> usize
Returns the number of registers with zero values. This value is used for computing a small correction when estimating the cardinality of a small set.
Examples
// Create a new HyperLogLog counter with precision 14 and 5 bits per register.
let mut hll = HyperLogLog::<Precision14, 5>::default();
// Add some elements to the counter.
hll.insert(&1);
hll.insert(&2);
hll.insert(&3);
// Get the number of zero registers.
let number_of_zero_registers = hll.get_number_of_zero_registers();
assert_eq!(number_of_zero_registers, 16381);
source§const INTERMEDIATE_RANGE_CORRECTION_THRESHOLD: f32 = _
const INTERMEDIATE_RANGE_CORRECTION_THRESHOLD: f32 = _
const LINEAR_COUNT_THRESHOLD: f32 = _
source§const LOWER_REGISTER_MASK: u32 = _
const LOWER_REGISTER_MASK: u32 = _
source§const LOWER_PRECISION_MASK: usize = _
const LOWER_PRECISION_MASK: usize = _
const NOT_LOWER_PRECISION_MASK: u64 = _
const NUMBER_OF_PADDING_BITS: usize = _
source§const PADDING_BITS_MASK: u32 = _
const PADDING_BITS_MASK: u32 = _
const NUMBER_OF_PADDING_REGISTERS: usize = _
source§const LAST_WORD_PADDING_BITS_MASK: u32 = _
const LAST_WORD_PADDING_BITS_MASK: u32 = _
source§const UPPER_PRECISION_MASK: usize = _
const UPPER_PRECISION_MASK: usize = _
source§const NUMBER_OF_REGISTERS_IN_WORD: usize = _
const NUMBER_OF_REGISTERS_IN_WORD: usize = _
fn adjust_estimate(raw_estimate: f32) -> f32
fn adjust_estimate_with_zeros(raw_estimate: f32, number_of_zeros: usize) -> f32
source§fn use_small_range_correction(&self) -> bool
fn use_small_range_correction(&self) -> bool
source§fn estimate_cardinality(&self) -> f32
fn estimate_cardinality(&self) -> f32
source§fn estimate_union_cardinality(&self, other: &Self) -> f32
fn estimate_union_cardinality(&self, other: &Self) -> f32
source§fn estimate_union_and_sets_cardinality<F: Primitive<f32> + MaxMin>(
&self,
other: &Self
) -> EstimatedUnionCardinalities<F>
fn estimate_union_and_sets_cardinality<F: Primitive<f32> + MaxMin>( &self, other: &Self ) -> EstimatedUnionCardinalities<F>
source§fn estimate_intersection_cardinality<F: Primitive<f32>>(
&self,
other: &Self
) -> F
fn estimate_intersection_cardinality<F: Primitive<f32>>( &self, other: &Self ) -> F
source§fn estimate_jaccard_index(&self, other: &Self) -> f32
fn estimate_jaccard_index(&self, other: &Self) -> f32
source§fn estimate_difference_cardinality<F: Primitive<f32> + One>(
&self,
other: &Self
) -> F
fn estimate_difference_cardinality<F: Primitive<f32> + One>( &self, other: &Self ) -> F
source§fn is_empty(&self) -> bool
fn is_empty(&self) -> bool
source§fn get_number_of_padding_registers() -> usize
fn get_number_of_padding_registers() -> usize
fn get_number_of_non_zero_registers(&self) -> usize
source§fn get_registers(&self) -> P::Registers
fn get_registers(&self) -> P::Registers
source§fn may_contain<T: Hash>(&self, rhs: &T) -> bool
fn may_contain<T: Hash>(&self, rhs: &T) -> bool
true
if the HyperLogLog counter may contain the given element. Read moresource§fn may_contain_all(&self, rhs: &Self) -> bool
fn may_contain_all(&self, rhs: &Self) -> bool
source§fn get_hash_and_index<T: Hash>(&self, value: &T) -> (u64, usize)
fn get_hash_and_index<T: Hash>(&self, value: &T) -> (u64, usize)
source§fn estimate_cardinality_from_multiplicities(
multiplicities: &P::RegisterMultiplicities
) -> f32
fn estimate_cardinality_from_multiplicities( multiplicities: &P::RegisterMultiplicities ) -> f32
source§impl<P: Precision + WordType<BITS>, const BITS: usize, I: Primitive<f32>> HyperSpheresSketch<I> for HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize, I: Primitive<f32>> HyperSpheresSketch<I> for HyperLogLog<P, BITS>
source§impl<P: Precision + WordType<BITS>, const BITS: usize> PartialEq for HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize> PartialEq for HyperLogLog<P, BITS>
Implements PartialEq for HyperLogLog.
Implementative details
Two HyperLogLog counters are considered equal if they have the same words.
Examples
let mut hll1 = HyperLogLog::<Precision14, 5>::default();
hll1.insert(&2);
let mut hll2 = HyperLogLog::<Precision14, 5>::default();
hll2.insert(&2);
hll2.insert(&3);
assert_ne!(hll1, hll2);
hll1 |= hll2;
assert_eq!(hll1, hll2);
source§impl<P: Precision + WordType<BITS>, const BITS: usize> Serialize for HyperLogLog<P, BITS>
impl<P: Precision + WordType<BITS>, const BITS: usize> Serialize for HyperLogLog<P, BITS>
source§fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error>
fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error>
Serializes the HyperLogLog counter using the given serializer.
This method is part of the Serialize
trait implementation for the HyperLogLog struct,
allowing the counter to be serialized into a format supported by the serializer.
Arguments
serializer
: The serializer used to serialize the HyperLogLog counter.
Returns
The serialization result, indicating success or failure.
Example
use serde::Serialize;
use serde_json::Serializer;
use hyperloglog_rs::prelude::*;
let hll = HyperLogLog::<Precision12, 6>::default();
let mut serializer = Serializer::new(Vec::new());
let result = hll.serialize(&mut serializer);
assert!(result.is_ok(), "Serialization failed, error: {:?}", result.err());