Bloom Filter Types

In the implementation I am working with, a bloom filter allows us to determine if a particular item has been selected from a set. Both the set and subset can be large.

While speed is a benefit, the real benefit for us is the memory footprint. We can quickly determine if the item is (probably) selected, without maintaining a list of (large) keys.

I am researching various types of bloom filters that must fit within the following parameters:

  • Low false positive
  • Memory efficient
  • Deletable
  • No false negative

The last two pose the challenge. A standard implementation of a bloom filter does not have false negatives, but items cannot be deleted. Deletions without knowing if an item was previously inserted can cause false negatives in the following implementations:

  • counting bloom filter
  • cuckoo filter
  • dlbf (possibly, not tested)

Research links:

Git Tricks

Here are some tricks that I use. They’re here because I need a place to quickly refer to them.

  • Updating a fork with upstream changes:
  • Interactive rebasing:
    • git rebase -i <branch>
  • To avoid messing up a PR, you can do things like:
    • git reset –hard HEAD-1 # or HEAD-2, etc, or directly to a commit hash
    • git push –force origin branch_name
  • Always do a backup before reset or rebase

C++ Publish Subscribe

I had the need to make a publish-subscribe mechanism in C++. So as is common, I looked around at other examples to see how others have done it and found a simple example courtesy of GitHubGist user makomweb.

His didn’t include comments, so I’m commenting it on my own copy here.

As programmers, we learn from each other. Each piece of code we write or see helps us to reason, adjust, and form opinions.

Getting our hands dirty and coding is a great learning experience. But reviewing the code of others helps us to build skills.

Why did makomweb not just have the Subscriber class conform to an interface? The entire class could have been passed to the Producer instead of just saving off the method. Think about it.

Look at the Publisher.Publish method. Elegant. One line of code to call Event(). The magic happens in Event.operator(). It calls the method that was registered in the Event.Subscribe call.

Had we stored an object that complies to an interface, we could do the same thing. We store the object in a map. When a “Publish” happens, we iterate the map, calling the method from the interface.