Struct HyperLogLog

pub struct HyperLogLog<T, H, W> { /* private fields */ }

Estimator logic implementing the HyperLogLog algorithm.

Instances are built using HyperLogLogBuilder, which provides convenient ways to set the internal parameters.

Note that T can be any type satisfying the Hash trait. The parameter H makes it possible to select a hashing algorithm, and W is the unsigned type used to store backends.

An important constraint is that W must be able to represent exactly the backend of an estimator. While usually usize will work (and it is the default type chosen by new), with odd register sizes and small number of registers it might be necessary to select a smaller type, resulting in slower merges. For example, using 16 5-bit registers one needs to use u16, whereas for 16 6-bit registers u32 will be sufficient.

Implementations

impl HyperLogLog<(), (), ()>

pub fn log_2_num_of_registers(rsd: f64) -> usize

Returns the logarithm of the number of registers per estimator that are necessary to attain a given relative standard deviation.

Arguments

• rsd: the relative standard deviation to be attained.

pub fn rel_std(log_2_num_registers: usize) -> f64

Returns the relative standard deviation corresponding to a given number of registers per estimator.

Arguments

• log_2_num_registers: the logarithm of the number of registers per estimator.

pub fn register_size(n: usize) -> usize

Returns the register size in bits, given an upper bound on the number of distinct elements.

Arguments

• n: an upper bound on the number of distinct elements.

Trait Implementations

impl<T, H: Clone, W: Clone> Clone for HyperLogLog<T, H, W>

fn clone(&self) -> Self

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug, H: Debug, W: Debug> Debug for HyperLogLog<T, H, W>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T, H, W> Display for HyperLogLog<T, H, W>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Hash, H: BuildHasher + Clone, W: Word + UpcastableInto<u64> + CastableFrom<u64>> EstimationLogic for HyperLogLog<T, H, W>

type Item = T

The type of items.

type Backend = [W]

The type of the backend.

type Estimator<'a> = DefaultEstimator<HyperLogLog<T, H, W>, &'a HyperLogLog<T, H, W>, Box<[W]>> where T: 'a, W: 'a, H: 'a

The type of an estimator.

fn new_estimator(&self) -> Self::Estimator<'_>

Creates a new empty estimator using this logic.

fn add(&self, backend: &mut Self::Backend, element: impl Borrow<T>)

Adds an element to an estimator with the given backend.

fn estimate(&self, backend: &[W]) -> f64

Returns an estimation of the number of distinct elements that have been added to an estimator with the given backend so far.

fn clear(&self, backend: &mut [W])

Clears a backend, making it empty.

fn set(&self, dst: &mut [W], src: &[W])

Sets the contents of dst to the contents of src.

impl<T: Hash, H: BuildHasher + Clone, W: Word + UpcastableInto<u64> + CastableFrom<u64>> MergeEstimationLogic for HyperLogLog<T, H, W>

type Helper = HyperLogLogHelper<W>

The type of the helper use in merge calculations.

fn new_helper(&self) -> Self::Helper

Creates a new helper to use in merge operations.

fn merge_with_helper(&self, dst: &mut [W], src: &[W], helper: &mut Self::Helper)

Merges src into dst using the provided helper to avoid allocations.

fn merge(&self, dst: &mut Self::Backend, src: &Self::Backend)

Merges src into dst.

impl<T: PartialEq, H: PartialEq, W: PartialEq> PartialEq for HyperLogLog<T, H, W>

fn eq(&self, other: &HyperLogLog<T, H, W>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Hash, H: BuildHasher + Clone, W: Word + UpcastableInto<u64> + CastableFrom<u64>> SliceEstimationLogic<W> for HyperLogLog<T, H, W>

fn backend_len(&self) -> usize

The number of elements of type T in a backend.

impl<T, H, W> StructuralPartialEq for HyperLogLog<T, H, W>