Approximate Algorithms


#1

Hi all!

In video 10, @jeremy mentions approximate algorithms and how they are unappreciated. Does anyone have any resources to learn more about how to create approximate algos? Or to learn more about them?

Thanks!


(Matthijs) #2

A very basic approximate data structure is the bloom filter. The name is a little confusing, but it’s a collection like a set. But unlike a regular set it has a degree of uncertainty about which objects it actually contains.

The bloom filter can tell you whether an object is definitely not in the set, or that maybe it is in the set. The advantage, as with many approximate algorithms, is that it is very fast.

You can read more about the bloom filter here: https://github.com/raywenderlich/swift-algorithm-club/tree/master/Bloom%20Filter

Another cool approximate algorithm is HyperLogLog, which is used to count the number of distinct elements in a collection (like a database).