const BITSUSED: u32 = 20;
pub struct HyperLogLog{
m: Vec<u8>,
}
impl HyperLogLog{
pub fn new() -> HyperLogLog {
HyperLogLog{
m: vec![0; 1 << BITSUSED],
}
}
fn tau(mut x: f64) -> f64{
if x == 0.0 || x == 1.0 {
return 0.0;
}
let mut y: f64 = 1.0;
let mut z: f64 = 1.0 - x;
let mut zp: f64 = 2.0;
while zp != z{
x = x.sqrt();
zp = z;
y /= 2.0;
z -= (1.0 - x).powf(2.0) * y;
}
z/3.0
}
fn sigma(mut x: f64) -> f64 {
if x == 1.0 {
return f64::INFINITY;
}
let mut y: f64 = 1.0;
let mut z: f64 = x;
let mut zp: f64 = 2.0;
while zp != z {
x *= x;
zp = z;
z += x * y;
y *= 2.0;
}
return z;
}
pub fn add(&mut self, data: u64) {
let j: usize = (data >> (64-BITSUSED)) as usize;
let w: u64 = data << BITSUSED;
self.m[j] = (self.m[j]).max(w.trailing_zeros() as u8);
}
pub fn count(&self) -> u64 {
let size: u64 = (1 as u64) << BITSUSED;
let mut c: [u32; (64-BITSUSED+2) as usize] = [0; (64-BITSUSED+2) as usize];
for &x in &self.m {
let k:i32 = (x as i32 - BITSUSED as i32 + 1).max(0);
c[k as usize] += 1;
}
let mut z: f64 = size as f64 * HyperLogLog::tau(1.0 - c[(64-BITSUSED+1) as usize] as f64 / size as f64);
for k in (1..64-BITSUSED+1).rev() {
z = 0.5 * (z + c[k as usize] as f64);
}
z += size as f64 * HyperLogLog::sigma(c[0] as f64 / size as f64);
return (1.0/(2.0_f64 * (2.0_f64).ln()) * size as f64 * size as f64 / z) as u64;
}
}