Live data from Hacker News

Ask HN: What are some cool but obscure data structures you know about?

news.ycombinator.com

441–450 of 772 posts

Re: Ask HN: What are some cool but obscure data structures you know about?

#441

Earlier 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?

Iterating with async/await means you wait for every result before making another call. You basically execute the async calls one by one.

Promise.all runs them all simultaneously and waits until they are all complete. It returns an array of results in the same order as the calls, so it's usually pretty straightforward to use.

Both approaches have a purpose, so it's not like you "should" strictly use one. But you should be aware of both and be able to use the one that fits the need.

Re: Ask HN: What are some cool but obscure data structures you know about?

#442
post #139

Earlier quoted context omitted.

There are also Judy arrays: https://en.wikipedia.org/wiki/Judy_array

This sounded promising but then I saw a performance benchmark [1] that was done on a pentium(!) with a very suboptimal hash table design compared to [2] and [3]. The Judy site itself [4] is full of phrases like "may be out of date", when the entire site was last updated in 2004. If it was already out of date in 2004... It seems that Judy arrays are just kind of a forgotten datastructure, and it doesn't look promising…

It seems to me that the project is still active,: https://sourceforge.net/p/judy/bugs/29/

Re: Ask HN: What are some cool but obscure data structures you know about?

#443

Not 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…

I love this approach and have used it many times in JavaScript. I often end up adding an additional map in front with the resolved values to check first, because awaiting or then'ing a Promise always means you will wait until the next microtask for the value, instead of getting it immediately. With a framework like React, this means you'll have a flash of missing content even when it is already cached.

Re: Ask HN: What are some cool but obscure data structures you know about?

#444
The SO question "What are the lesser known but useful data structures?" has a good list

https://stackoverflow.com/questions/500607/what-are-the-less...

[edit: the link above has been discussed on HN multiple times https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu...]

Re: Ask HN: What are some cool but obscure data structures you know about?

#445
Not technically a data structure, but Reservoir Sampling is an interesting probabilistic sampling technique used to choose a random sample from a population of unknown size N in a single pass, so useful for a data structure that does not fit in memory.

https://en.wikipedia.org/wiki/Reservoir_sampling

Re: Ask HN: What are some cool but obscure data structures you know about?

#446
post #331

Equality 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…

Shameless plug, I also maintain an OCaml implementation of egraphs (named ego) at https://github.com/verse-lab/ego

While the most popular implementation at the moment seems to be egg in Rust, I find that OCaml serves as a much more ergonomic environment for quickly prototyping out uses of egraphs in practice. As a bonus, ego also shares the same logical interface as egg itself, so once you've finalised your designs, you shouldn't have much trouble porting them to egg if you need the performance gains.

Re: Ask HN: What are some cool but obscure data structures you know about?

#447
post #167

Earlier quoted context omitted.

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.

The same things get invented over and over again and named different things depending on the field. Sometimes it's not immediately clear that they are the same things mathematically.

Re: Ask HN: What are some cool but obscure data structures you know about?

#449
Purely Functional Data Structures[1] by Chris Okasaki is worth reading. There's a book version if you prefer vs reading a thesis.

Even though the domain application is functional programming, these datastructures can come in handy when you want to enable state sharing / keeping old versions around without having to copy data.

[1] https://www.cs.cmu.edu/~rwh/students/okasaki.pdf

Post reply on HN