8 ms·
How to write a Bloom filter in C++
- deleted 10y ago[deleted]
- nate_martin 10y agoThis example works well for raw data but not for complex types. You could make the filter a template, taking the key and a "hasher" function as template args.
- schmatz 10y agoGreat suggestion; I wasn't sure the idiomatic way to template this, thanks for letting me know!
- nate_martin 10y agoProbably something like this: template< class Key, class Hash = std::hash<Key> > class BloomFilter;
- schmatz 10y agoI updated the blog post with your suggestion; CDN should be updated soon :)
- bradleyjg 10y agoI don't use c++ so I'm not sure how std:hash works or gets implemented, but the way that guava (Google's java library) does it is by passing in a key and a funnel object. The funnel object is essentially responsible for decomposing the object into a byte stream. The advantage of doing it this way rather than making the caller specify his own hash is that you can use murmurhash3 which you thought had the best properties for the bloom filter.
- mavam 10y agoEven better: N3980 [1] This proposal decouples the implementation of hash functions from how types get hashed. [1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3980.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n398...
- j_s 10y agoIs there a standard implementation "everybody uses"? Bloomd seems popular as a bloom filter server. https://github.com/armon/bloomd https://github.com/armon/bloomd
- m00dy 10y agoI have also experiments about Bloom Filter in python https://github.com/erenyagdiran/BloomFilter https://github.com/erenyagdiran/BloomFilter
- nvcken 10y agoHow is your laptop spec ? please
- barsonme 10y agoOr in C[0] or in Go[1]... [0] - https://github.com/EricLagergren/bloom https://github.com/EricLagergren/bloom [1] - https://github.com/EricLagergren/bloom-c https://github.com/EricLagergren/bloom-c
- nly 10y agoI feel the use of vector<bool> is an iffy choice. The Bitcoin codebase has a simple Bloom filter implementation you can take a look at that has been in use for some time https://github.com/bitcoin/bitcoin/blob/master/src/bloom.h https://github.com/bitcoin/bitcoin/blob/master/src/bloom.h https://github.com/bitcoin/bitcoin/blob/master/src/bloom.cpp https://github.com/bitcoin/bitcoin/blob/master/src/bloom.cpp
- bmohlenhoff 10y agostd::bitset is also a good choice if the number of desired bits is known at compile time
- schmatz 10y agoI think this would probably be the best choice after templating the filter
- mavam 10y agoWhat's wrong with vector<bool> (other than its name)? The interface is exactly what you need to implement a bit-level abstraction in a language where this isn't a first-class primitive.
- sokoloff 10y agoLearned something today. Thanks for the article. Minor nit: it will save readers time if you call out that "p is the false positive error rate". (You reference the error rate, but don't attach a variable name to it.) I had to go to an external reference to figure that out, which meant I learned something else of course.
- schmatz 10y agoGreat suggestion, thanks! I've updated the article accordingly :)