Struct HyperLogLog 

pub struct HyperLogLog<T, H, W = usize, const BETA: bool = true> { /* private fields */ }

Estimation logic implementing the HyperLogLog algorithm.

This implementation uses 5- or 6-bit registers and broadword programming. It thus uses the minimum possible space, saving 37.5 or 25% space with respect to the HyperLogLog8 logic, which uses 8-bit registers and byte-wise SIMD operations, but it is significantly slower than the latter.

The choice between the two logics should be guided by the specific use case and constraints of your application. Please try the included benchmarks to have an idea of the difference in performance between the two logics in your environment.

Instances are created through HyperLogLogBuilder:

// Default: LogLog-β correction enabled, usize backend
let logic = HyperLogLogBuilder::new(1_000_000)
    .log2_num_regs(8)
    .build::<String>().unwrap();

// Disable LogLog-β, use classic HyperLogLog + linear-counting fallback
let logic = HyperLogLogBuilder::new(1_000_000)
    .log2_num_regs(8)
    .beta::<false>()
    .build::<String>().unwrap();

Type parameters

• T: the type of elements to count (must implement Hash).

• H: the BuildHasher used to hash elements.

• W: the unsigned word type for the register backend (see below).

• BETA: when true (the default), the LogLog-β bias correction is used during estimation. This provides better accuracy across the full cardinality range through a single formula, eliminating the need for a separate linear-counting correction. The cost is roughly 20ns per estimate call when some registers are still zero; when all registers are populated, the correction is skipped and performance is identical to the classic formula. Set to false via HyperLogLogBuilder::beta to use the original HyperLogLog formula instead.

Backend alignment

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 HyperLogLogBuilder::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, W::BITS must divide (1 << log2_num_regs) * register_size (using HyperLogLog::register_size(num_elements)). HyperLogLogBuilder::min_log2_num_regs returns the minimum value for log2_num_regs that satisfies this property.

Implementations

impl<T, H: Clone, W: Word, const BETA: bool> HyperLogLog<T, H, W, BETA>

pub fn log2_num_regs(&self) -> u32

Returns the base-2 logarithm of the number of registers per estimator.

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

pub fn log2_num_of_registers(rsd: f64) -> u32

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(log2_num_regs: u32) -> f64

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

Arguments

• log2_num_regs: 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, const BETA: bool> Clone for HyperLogLog<T, H, W, BETA>

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, const BETA: bool> Debug for HyperLogLog<T, H, W, BETA>

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

Formats the value using the given formatter.

impl<T, H, W, const BETA: bool> Display for HyperLogLog<T, H, W, BETA>

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

Formats the value using the given formatter.

impl<T: Hash, H: BuildHasher + Clone, W: Word, const BETA: bool> EstimationLogic for HyperLogLog<T, H, W, BETA>

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, BETA>, &'a HyperLogLog<T, H, W, BETA>, 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, const BETA: bool> MergeEstimationLogic for HyperLogLog<T, H, W, BETA>

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, const BETA: bool> PartialEq for HyperLogLog<T, H, W, BETA>

fn eq(&self, other: &HyperLogLog<T, H, W, BETA>) -> 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, const BETA: bool> SliceEstimationLogic<W> for HyperLogLog<T, H, W, BETA>

where u32: PrimitiveNumberAs<W>,

fn backend_len(&self) -> usize

The number of elements of type T in a backend.

impl<T, H, W, const BETA: bool> StructuralPartialEq for HyperLogLog<T, H, W, BETA>