How to write a Bloom filter in C++ • Hacker News Board

Re: How to write a Bloom filter in C++

#11

Post by nvcken » Tue, Apr 12, 2016, 3:51 AM UTC

schmatz wrote: post #10

nvcken wrote: post #9

How is your laptop spec ? please

Intel Core i7-4980HQ

SSD, RAM ? I think maybe it affects performance

Re: How to write a Bloom filter in C++

#12

Post by schmatz » Tue, Apr 12, 2016, 4:02 AM UTC

nvcken wrote: post #11

schmatz wrote: post #10

Earlier quoted context omitted.

Intel Core i7-4980HQ

SSD, RAM ? I think maybe it affects performance

RAM is 1600MHz DDR3. I do have an SSD, but as the memory usage of the program was ~32MB, so I doubt it would have an effect haha

Re: How to write a Bloom filter in C++

#13

Post by barsonme » Tue, Apr 12, 2016, 6:41 AM UTC

Or in C[0] or in Go[1]...

[0] - https://github.com/EricLagergren/bloom [1] - https://github.com/EricLagergren/bloom-c

Re: How to write a Bloom filter in C++

#14

Post by nly » Tue, Apr 12, 2016, 10:17 AM UTC

I feel the use of vector 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.cpp

Re: How to write a Bloom filter in C++

#15

Post by sokoloff » Tue, Apr 12, 2016, 10:31 AM UTC

Learned 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.

Re: How to write a Bloom filter in C++

#16

Post by bmohlenhoff » Tue, Apr 12, 2016, 10:48 AM UTC

nly wrote: post #14

I feel the use of vector 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.cpp

std::bitset is also a good choice if the number of desired bits is known at compile time

Re: How to write a Bloom filter in C++

#17

Post by m00dy » Tue, Apr 12, 2016, 11:52 AM UTC

I have also experiments about Bloom Filter in python https://github.com/erenyagdiran/BloomFilter

Re: How to write a Bloom filter in C++

#18

Post by mavam » Tue, Apr 12, 2016, 2:58 PM UTC

nly wrote: post #14

I feel the use of vector 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.cpp

What's wrong with vector (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.

Re: How to write a Bloom filter in C++

#19

Post by schmatz » Tue, Apr 12, 2016, 3:54 PM UTC

sokoloff wrote: post #15

Learned 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.

Great suggestion, thanks! I've updated the article accordingly :)

Re: How to write a Bloom filter in C++

#20

Post by schmatz » Tue, Apr 12, 2016, 3:55 PM UTC

bmohlenhoff wrote: post #16

nly wrote: post #14

I feel the use of vector 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.cpp

std::bitset is also a good choice if the number of desired bits is known at compile time

I think this would probably be the best choice after templating the filter