HyperLogLog cardinality estimate.
(&self)
| 108 | |
| 109 | /// HyperLogLog cardinality estimate. |
| 110 | fn hll_estimate(&self) -> u64 { |
| 111 | let m = self.hll_registers.len() as f64; |
| 112 | // Alpha constant for m=256. |
| 113 | let alpha = 0.7213 / (1.0 + 1.079 / m); |
| 114 | let raw: f64 = alpha * m * m |
| 115 | / self |
| 116 | .hll_registers |
| 117 | .iter() |
| 118 | .map(|&r| 2.0_f64.powi(-(r as i32))) |
| 119 | .sum::<f64>(); |
| 120 | |
| 121 | if raw <= 2.5 * m { |
| 122 | // Small range correction. |
| 123 | let zeros = self.hll_registers.iter().filter(|&&r| r == 0).count() as f64; |
| 124 | if zeros > 0.0 { |
| 125 | (m * (m / zeros).ln()) as u64 |
| 126 | } else { |
| 127 | raw as u64 |
| 128 | } |
| 129 | } else { |
| 130 | raw as u64 |
| 131 | } |
| 132 | } |
| 133 | |
| 134 | /// Selectivity estimate for equality predicate (1 / distinct_count). |
| 135 | pub fn eq_selectivity(&self) -> f64 { |