Struct HyperLogLog 

pub struct HyperLogLog<T, H, W = usize> { /* 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 a 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.

Formally, this means that W::BITS must divide (1 << log_2_num_registers) * register_size (using HyperLogLog::register_size(num_elements)). HyperLogLogBuilder::min_log_2_num_reg returns the minimum value for log_2_num_registers that satisfies this property.

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(num_elements: usize) -> usize

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

Arguments

• num_elements: 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 duplicate 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> EstimationLogic for HyperLogLog<T, H, W>

where u32: PrimitiveNumberAs<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> MergeEstimationLogic for HyperLogLog<T, H, W>

where u32: PrimitiveNumberAs<W>,

type Helper = HyperLogLogHelper<W>

The type of the helper used 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> SliceEstimationLogic<W> for HyperLogLog<T, H, W>

where u32: PrimitiveNumberAs<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>