I'm very interested in what types of interesting data structures are out there HN. Totally your preference.
I'll start: bloom filters. Lets you test if a value is definitely NOT in a list of pre-stored values (or POSSIBLY in a list - with adjustable probability that influences storage of the values.)
Good use-case: routing. Say you have a list of 1 million IPs that are black listed. A trivial algorithm would be to compare every element of the set with a given IP. The time complexity grows with the number of elements. Not so with a bloom filter! A bloom filter is one of the few data structures whose time complexity does not grow with the number of elements due to the 'keys' not needing to be stored ('search' and 'insert' is based on the number of hash functions.)
Bonus section: Golomb Coded Sets are similar to bloom filters but the storage space is much smaller. Worse performance though.
It only works in languages where promises/futures/tasks are a first-class citizen. Eg JavaScript.
When caching the result of an expensive computation or a network call, don't actually cache the result, but cache the promise that awaits the result. Ie don't make a
but a This way, if a new, uncached key gets requested twice in rapid succession, ie faster than the computation takes, you avoid computing/fetching the same value twice. This trick works because:- promises hold on to their result value indefinitely (until they're GC'ed)
- you can await (or .then()) an existing promise as many times as you want
- awaiting an already-resolved promise is a very low-overhead operation.
In other words, the promise acts as a mutex around the computation, and the resulting code is understandable even by people unfamiliar with mutexes, locks and so on.