Size the filter
A service needs many Bloom filters: each customer has their own number of items n and their own acceptable false-positive rate p. Size every filter with the formulas from the article on the Bloom filter:
- the number of bits m = ⌈n · ln(1/p) / (ln 2)²⌉—the smallest integer not less than that value;
- the number of hashes k = round(m/n · ln 2), but at least 1;
- and the expected false-positive rate of the actual filter, (1 − e−kn/m)k—slightly different from the requested one, because m and k are rounded.
In every test the values are far from rounding boundaries, so any language with ordinary floating point computes the same.
Input
The first line holds the number of orders q (1 ≤ q ≤ 3000). Each of the next q lines holds an integer n (1 ≤ n ≤ 10⁹) and a fraction p (0 < p < 1).
Output
For each order, a line with m, k and the expected false-positive rate. The rate is checked with an absolute error of 10⁻⁷; print it with at least ten digits after the point.
Examples
Example 1
4 10000 0.01 10000 0.001 1000000 0.05 500 0.2
95851 7 0.0100390105 143776 10 0.0010000189 6235225 4 0.0502694654 1675 2 0.2020931100
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 5 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The task is to carry three formulas into code carefully. The dangerous part is rounding: which one goes up, and which to the nearest?
2The idea
There must be no fewer bits than the formula demands, or the error exceeds what was ordered—hence m is rounded up. And k is where the error is smallest as a function of the number of hashes; near its minimum the error curve is flat, and the nearest integer to the optimum beats a dropped fraction.
3Walkthrough
For each order compute m = ceil(n·ln(1/p)/ln²2), then k = max(1, round(m/n·ln 2)), and put both into the error formula. Put in the actual m and k, rather than echo the ordered p: the customer cares about what they will really get.
Note that n = 1 and p = 0.5 give m = 2, k = 1: one hash in a two-bit array, and an error of exactly 1 − e−1/2 ≈ 0.39—less than the half that was ordered, because m was rounded up.
3+Solution
4Complexity
O(1) per order, O(q) in all.
5Common mistakes
- int() instead of round() for k. At 9.6 bits per item you get 6 hashes instead of 7—the error is a little above the optimum, and the test catches it.
- Integer division. In Go,
m / non integers is an integer. Convert to float64 before dividing. - Too few digits. At p = 10⁻⁹, six digits after the point print zero.