hypertwobits 0.2.3

HyperTwoBits cardinality estimation algorithm
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

use std::hash::Hasher;

/// `HyperBitBit` cardinality counter with 64 substreams
#[derive(Debug, Eq, PartialEq, Hash, Clone)]
#[cfg_attr(feature = "mem_dbg", derive(mem_dbg::MemDbg, mem_dbg::MemSize))]
pub struct HyperBitBit64<HASH: Hasher + Default = ahash::AHasher> {
    _hash: std::marker::PhantomData<HASH>,
    sketch1: u64,
    sketch2: u64,
    count1: u64,
    count2: u64,
    u: u64, // Power-of-two estimate of substream cardinality
}
impl<HASH: Hasher + Default> HyperBitBit64<HASH> {
    #[must_use]
    /// Creates a new `HyperBitBit64` counter
    pub fn new() -> Self {
        Self {
            _hash: std::marker::PhantomData,
            sketch1: 0,
            sketch2: 0,
            count1: 0,
            count2: 0,
            u: 1,
        }
    }
}

impl Default for HyperBitBit64 {
    fn default() -> Self {
        Self {
            _hash: std::marker::PhantomData,
            sketch1: 0,
            sketch2: 0,
            count1: 0,
            count2: 0,
            u: 1,
        }
    }
}

impl<HASH: Hasher + Default> HyperBitBit64<HASH> {
    /// The number of substreams
    const M: u64 = 64;
    #[inline]
    /// Inserts a value into the counter
    pub fn insert<V: std::hash::Hash>(&mut self, v: V) {
        let mut x = HASH::default();
        v.hash(&mut x);
        let x = x.finish();
        let k: u32 = (x >> 58) as u32 % 64;
        let x: u64 = x & 0x03FF_FFFF_FFFF_FFFF;

        if x & (self.u - 1) == self.u - 1 {
            if (self.sketch1 & (1_u64 << k)) == 0 {
                self.count1 += 1;
            }
            self.sketch1 |= 1 << k;
        }

        if x & (4 * self.u - 1) == 4 * self.u - 1 {
            if (self.sketch2 & (1_u64 << k)) == 0 {
                self.count2 += 1;
            }
            self.sketch2 |= 1 << k;
        }

        if self.count1 >= 62 {
            self.u *= 4;
            self.sketch1 = self.sketch2;
            self.count1 = self.count2;
            self.sketch2 = 0;
            self.count2 = 0;
        }
    }
    #[inline]
    #[must_use]
    #[allow(
        clippy::cast_precision_loss,
        clippy::cast_possible_truncation,
        clippy::cast_sign_loss
    )]
    /// Returns the cardinality estimate
    pub fn count(&self) -> u64 {
        let beta = 1.0 - (self.count1 as f64 / Self::M as f64);
        let bias: f64 = 1.1 * (1.0 / beta).ln();
        ((self.u as f64) * (Self::M as f64) * bias) as u64
    }
}