adriangb opened a new pull request, #11088: URL: https://github.com/apache/arrow-rs/pull/11088
# Which issue does this PR close? No issue filed. This is a small API addition and the rationale is below; I can file one if you prefer. # Rationale for this change `Sbbf::fold_to_target_fpp` (added in #9628) already estimates a filter's false positive probability from its average per-block fill, but callers cannot read that estimate. A caller that needs it before folding, for example to discard a filter that is already over its target FPP at build size, must serialize the bitset and count set bits in the bytes. That copies the full bitset and duplicates the formula outside the crate. # What changes are included in this PR? - Add `Sbbf::estimated_fpp`, which counts set bits directly on the blocks and returns `fill^8`. It returns `1.0` for a filter with no blocks. - `num_folds_for_target_fpp` now uses the same fill calculation, so the public estimate and the folding decision cannot drift apart. # Are these changes tested? Yes. - `test_estimated_fpp_matches_serialized_bitset` checks that the result is bit-for-bit equal to counting set bits in the `write_bitset` output, for 32 B, 1 KiB, and 64 KiB filters with 0 to 100,000 inserted values. - `test_estimated_fpp_bounds` covers an empty filter, a full filter, and a filter with no blocks. - `test_estimated_fpp_increases_when_folded` checks that folding does not lower the estimate. The existing folding tests continue to pass. # Are there any user-facing changes? Yes, one new public method, `Sbbf::estimated_fpp`. There are no breaking changes. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
