bloomcalc/
lib.rs

1#![doc = include_str!("../README.md")]
2
3/// A Parameter is a typed wrapper around a f64.
4pub trait Parameter {
5    /// Return a new parameter from the provided f64.
6    fn new(x: f64) -> Self;
7}
8
9const LN2_2: f64 = 0.4804530139182014; // ln^2 2
10
11/// N is the number of items expected to be inserted into the bloom filter.
12#[derive(Clone, Copy)]
13pub struct N(pub f64);
14
15impl Parameter for N {
16    fn new(x: f64) -> N {
17        N(x)
18    }
19}
20
21/// P is the probability of false positives.
22#[derive(Clone, Copy)]
23pub struct P(pub f64);
24
25impl Parameter for P {
26    fn new(x: f64) -> P {
27        P(x)
28    }
29}
30
31/// M is the number of bits to use in the bloom filter.
32#[derive(Clone, Copy)]
33pub struct M(pub f64);
34
35impl Parameter for M {
36    fn new(x: f64) -> M {
37        M(x)
38    }
39}
40
41/// K is the number of keys to insert/hash.
42#[derive(Clone, Copy)]
43pub struct K(pub f64);
44
45impl Parameter for K {
46    fn new(x: f64) -> K {
47        K(x)
48    }
49}
50
51/////////////////////////////////////////// Calculations ///////////////////////////////////////////
52
53/// Given the probability of false positive, compute the necessary number of keys.
54pub fn calc_keys_given_probability(p: P) -> K {
55    K(0.0f64 - p.0.log2())
56}
57
58/// Given the probability of false positive and number of elements, compute the number of bits.
59pub fn calc_m_given_p_n(p: P, n: N) -> M {
60    M(0.0 - n.0 * p.0.ln() / LN2_2)
61}
62
63/// Given the number of elements and number of bits, compute the probability of false positive.
64pub fn calc_p_given_n_m(n: N, m: M) -> P {
65    let e = std::f64::consts::E;
66    P(e.powf(0.0 - LN2_2 * m.0 / n.0))
67}
68
69/////////////////////////////////////////////// tests //////////////////////////////////////////////
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    struct TestParams {
76        n: N,
77        p: P,
78        m: M,
79        k: K,
80    }
81
82    const TEST_PARAMS: &[TestParams] = &[
83        TestParams {
84            n: N(100.0),
85            p: P(0.01),
86            m: M(958.505837736744),
87            k: K(6.643856189774724),
88        },
89        TestParams {
90            n: N(1000.0),
91            p: P(0.001),
92            m: M(14377.58756605116),
93            k: K(9.965784284662087),
94        },
95        TestParams {
96            n: N(2718281.0),
97            p: P(0.0314159),
98            m: M(19578296.19763294),
99            k: K(4.99236127889529),
100        },
101    ];
102
103    fn approximately_correct(expected: f64, returned: f64) -> bool {
104        returned * 0.99 < expected && returned * 1.01 > expected
105    }
106
107    #[test]
108    fn ln2_2() {
109        let expect = 2.0f64.ln().powf(2.0);
110        assert!(approximately_correct(expect, LN2_2));
111    }
112
113    #[test]
114    fn test_keys_given_probability() {
115        for param in TEST_PARAMS.iter() {
116            let k = calc_keys_given_probability(param.p);
117            assert!(approximately_correct(param.k.0, k.0));
118        }
119    }
120
121    #[test]
122    fn test_m_given_p_n() {
123        for param in TEST_PARAMS.iter() {
124            let m = calc_m_given_p_n(param.p, param.n);
125            assert!(approximately_correct(param.m.0, m.0));
126        }
127    }
128
129    #[test]
130    fn test_p_given_n_m() {
131        for param in TEST_PARAMS.iter() {
132            let p = calc_p_given_n_m(param.n, param.m);
133            assert!(approximately_correct(param.p.0, p.0));
134        }
135    }
136}
bloomcalc/lib.rs

bloomcalc/
lib.rs
