I really like the splay tree. It optimizes itself during reads and writes such that it is optimal for a fixed probability distribution of accesses.
Ask HN: What are some cool but obscure data structures you know about?
581–590 of 772 posts
Re: Ask HN: What are some cool but obscure data structures you know about?
#582It's not a data structure but a really cool algorithm. Locality Sensitive Hashing. It allows like items to be hashed to the same value. So instead of a typical hashing functions that wants to avoid collisions this algorithm tries to optimize for collisions.
Re: Ask HN: What are some cool but obscure data structures you know about?
#583Structures good for Geospatial information like rtrees, quadtrees. https://en.m.wikipedia.org/wiki/R-tree Also concurrent data structures. https://youtu.be/jcqGSehrMGU
Yes, R-tree turned out to be a godsend when working with larger geospatial data and calculating intersections.
Yep, that's what I used it for! Intersections. Hard to make concurrent though. Ended up with concurrent map backed geohash.
Re: Ask HN: What are some cool but obscure data structures you know about?
#584> 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.
In the case of IPs, you just have to make 4 comparisons (for IPv4), if you store them in a tree.
Re: Ask HN: What are some cool but obscure data structures you know about?
#585Earlier quoted context omitted.
I have written many tools that do something like this, very useful. Just gotta be careful with memory leaks, so (for a TS example) you might want to do something like this: const promiseMap > = new Map(); async function keyedDebounce (key: string, fn: () => R) { const existingPromise = promiseMap.get(key); if (existingPromise) return existingPromise; const promise = new Promise(async (resolve) => { const result = awa…
You check for if(promiseMap.get(key)) and in the NO case you do promiseMap.delete(key)? Could you explain why that's necessary? (sorry probs a stupid question)
So if the promise still exists, that means that there is an active call out for a promise using this key already, so we'll just return it. We know this because when the function that is executing finishes, we delete the promise from the map.
A purpose of this might be, let's say you rebuild some structure very frequently, like hundreds of times per second or whatever. You can call this function for a given key as many times as you want while that async process is executing, and it will only execute it once, always returning the same promise.
Re: Ask HN: What are some cool but obscure data structures you know about?
#586Suffix trees are known to anyone who's done text search, but very neat! Fairly easy idea too: in order to allow quick substring search, build a mapping from all suffixes to documents. This is compressed as a tree, and prefix matching is done by partial traversal.
Re: Ask HN: What are some cool but obscure data structures you know about?
#587"This is the story of a clever trick that's been around for at least 35 years, in which array values can be left uninitialized and then read during normal operations, yet the code behaves correctly no matter what garbage is sitting in the array. Like the best programming tricks, this one is the right tool for the job in certain situations. The sleaziness of uninitialized data access is offset by performance improveme…
I was going to mention Sparse Arrays, thanks for mentioning it. One of my favorite data structures.
Re: Ask HN: What are some cool but obscure data structures you know about?
#588Equality graphs (e-graphs) for theorem proving and equality saturation and other equality-related things. They're awesome data structures that efficiently maintain a congruence relation over many expressions > At a high level, e-graphs extend union-find to compactly represent equivalence classes of expressions while maintaining a key invariant: the equivalence relation is closed under congruence. e.g. If I were to re…
I wonder if you could apply e-graphs to situations where the union-find data structure would be used, i.e. if there are any additional benefits gotten from the congruence relation.
More pointers and more processing in exchange for representing equivalence classes of many, often infinitely many graphs compactly and enumerating them efficiently. Usually not relevant when equivalence of simple nodes is the object.
Re: Ask HN: What are some cool but obscure data structures you know about?
#589Earlier quoted context omitted.
You can put the promise into the cache immediately but you can only put the result from the promise into the cache once the promise resolves. So if an identical request comes in a second time before the promise has been resolved, then if you are caching the promise you have a cache hit but if you are caching the result then you have a cache miss and you end up doing the work twice.
I am still not understanding the purpose of this as I believe it is grounded on the wrong assumption. Pretty much every single asynchronous operation other than some `Promise.resolve(foo)` where foo is a static value can fail. Reading from the file system, calling an api, connecting to some database, etc. If the original promise fails you're gonna return a cached failure. Mind you, I'm not stating this might be compl…
> If the original promise fails you're gonna return a cached failure.
In the scenario where that's an issue, you would need to add (extremely trivial 3-5 lines) logic to handle retrying a cached failure. The underlying data structure would continue to be a promise map.
Re: Ask HN: What are some cool but obscure data structures you know about?
#590I'll add: the count-min sketch[0]. Used for streaming top-k, where the set of keys may be too large to fit in memory. It's essentially a composite of a fixed size (k) heap and a counting bloom filter.
Instead of using a bit field for membership, use an integer field for tracking count.
When querying: take the min of each value in the field location given by the hash functions.
When updating: increment each field location given by the hash functions, take the min of new values. if the min is greater than the least value in the heap, push the updated key into the heap