If somebody made a Youtube channel going over the data structures mentioned in this thread with clear examples of pros/cons, I'd watch the heck out of it and support it on Patreon.
Ask HN: What are some cool but obscure data structures you know about?
431–440 of 772 posts
Re: Ask HN: What are some cool but obscure data structures you know about?
#432Fenwick Trees (which, despite the name, are implemented using an array) allow counting prefix sums AND updating prefix sums in O(log n) time. Very useful when n is in the order of millions. I have used them a few times in Project Euler problems. https://en.wikipedia.org/wiki/Fenwick_tree
Was going to mention Fenwick Tree here as well, but since you've already did, I'll just add that this is IMO a great introduction to Fenwick Trees:
https://www.youtube.com/watch?v=kPaJfAUwViY
Re: Ask HN: What are some cool but obscure data structures you know about?
#433Earlier quoted context omitted.
That's how mongodb geospatial indexes work IIRC
Was about to mention this. If I recall correctly, the 2d-sphere index rounds geospatial coordinates to 5 decimals. Very occasionally, I found it would distort polygon geometries just enough to cause them to become invalid (e.g. overlapping geometries), which causes the index build to fail. In my recent experience working with collections containing million of documents, each containing a geoJSON-style polygon/multipo…
Seems exactly like broad phase and narrow phase in games physics engine.
Re: Ask HN: What are some cool but obscure data structures you know about?
#434Not a very deep CS-y one, but still one of my favourite data structures: Promise Maps. 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 Map but a Map > This way, if a new, uncached key gets requested twice…
It’s also the clearest and least buggy way to iterate over the results. Map over Await Promise.all(map).
Partly off-topic, but in JS I tend to avoid iterating over promises with maps because it's always confusing what will/won't work, so I use a basic FOR loop because async/await works in there.
How bad is this? Should I switch to Promise.all instead?
Re: Ask HN: What are some cool but obscure data structures you know about?
#435Earlier quoted context omitted.
I wonder if Swift's AsyncAwait could be used in such a way.
Sure it's possible, we need to await for the Task if it already exists on the dictionary, for example we could imagine writing something like this inside an actor to make it threadSafe. private var tasksDictionary: Dictionary > func getData(at urlString: String) async throws -> Data { if let currentTask = tasksDictionary[urlString] { return await currentTask.value } let currentTask = Task { return try await URLSessio…
Great! So much nicer than the Combine (or Rx) version.
Re: Ask HN: What are some cool but obscure data structures you know about?
#436Splay trees: These are binary search trees, but when you 'splay' the tree (such as by search) it rebalances the tree so that the search result is on top. This means while it is O(log n) for operations like other self-balancing trees, it optimizes tree depth in the face of non-random access so that recently accessed items are fewer steps into the tree. Piece tables: A bit more common for text editors, where you need t…
Came here for splay tree. I’ve found some really powerful applications for this in low level database engine work.
Being able to incrementally rebalance a tree and keep the set of deltas small each time is really powerful when you are dealing with append only IO abstractions.
Re: Ask HN: What are some cool but obscure data structures you know about?
#437Earlier quoted context omitted.
It’s also the clearest and least buggy way to iterate over the results. Map over Await Promise.all(map).
Partly off-topic, but in JS I tend to avoid iterating over promises with maps because it's always confusing what will/won't work, so I use a basic FOR loop because async/await works in there. How bad is this? Should I switch to Promise.all instead?
Promise.all/allSettled/etc will allow you to resolve your promises concurrently rather than awaiting each result in the for loop. Depends what your use case is, really.
Re: Ask HN: What are some cool but obscure data structures you know about?
#438Rope (or Cord)
Re: Ask HN: What are some cool but obscure data structures you know about?
#439https://github.com/facebook/folly/blob/main/folly/docs/Packe...
is pretty awesome and I’ve personally gotten big wins from it.
The parent mentioned Bloom Filters, HyperLogLog-type stuff is on that family tree and also very interesting and very useful.
But the coolest thing lately by far? Swiss table (and the largely equivalent F14).
That thing is a game changer in certain scenarios.
Re: Ask HN: What are some cool but obscure data structures you know about?
#440> Good use-case: routing. Say you have a list of 1 million IPs that are [deny listed].
Apparently, bloom filters make for lousy IP membership checks, read: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/
CritBit Trie [0] and possibly Allotment Routing Table (ART) are better suited for IPs [1].
[0] https://github.com/agl/critbit
[1] https://web.archive.org/web/20210720162224/https://www.harig...