4 ms·
If you sort objects as you insert them into the membership list of the bloom filter, it's O(n log n) for a comparison based sort and O(n) for a top down discrim
by KirinDave 8y ago
If you sort objects as you insert them into the membership list of the bloom filter, it's O(n log n) for a comparison based sort and O(n) for a top down discriminating sort. However, if you sort the list, then you don't need the bloom filter anymore.
I'm not sure if this actually would be faster in practice though. It will have heavy, heavy constants if your keys are not trivial.
- millstone 8y agoWhy would sorting objects matter when inserting them into the Bloom filter? The filter is independent of insertion order. The notion of O(n) for a "top down discriminating sort" is outrageous and needs serious justification!
- masklinn 8y agoThey posted sources there: https://news.ycombinator.com/item?id=19642485 https://news.ycombinator.com/item?id=19642485 They also linked to Data.Discrimination, which assets to provide O(n) `nub` (aka deduplicate): http://hackage.haskell.org/package/discrimination-0.3/docs/Data-Discrimination.html#v:nub http://hackage.haskell.org/package/discrimination-0.3/docs/D...
- KirinDave 8y agoAs I implied, I think the bloom filter is somewhat superfluous to any solution to this problem.
- KirinDave 8y agoIt is 20 year old computer science often discussed in upper division compsci courses.