Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

news.ycombinator.com

Post reply on HN
Print view View original

331–340 of 772 posts

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

#331

Post by romes »

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 represent "f(x)" and "f(y)" in the e-graph, and then said "x == y" (merged "x" and "y" in the e-graph), then the e-graph, by congruence, would be able to tell me that "f(x) == f(y)"

e.g. If I were to represent "a*(2/2)", in the e-graph, then say "2/2 == 1", and "x*1 == x", by congruence the e-graph would know "a*(2/2) == a" !

The most recent description of e-graphs with an added insight on implementation is https://arxiv.org/pdf/2004.03082.pdf to the best of my knowledge.

P.S: I'm currently implementing them in Haskell https://github.com/alt-romes/hegg

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

#332

Post by jtwigg »

skrebbel wrote: post #297

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…

FYI, if you plan to do this in ASP netcore, combine with AsyncLazy for the most optimal results https://github.com/davidfowl/AspNetCoreDiagnosticScenarios/b...

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

#333

Post by TheFragenTaken »

zarzavat wrote: post #55

Spatial hashing. Say that you have data that is identified with points in 2D or 3D space. The standard way that CS students learn in school to represent this is via a quadtree or octree. However, these tree data structures tend to have a lot of "fluff" (needless allocations and pointer chasing) and need a lot of work to be made efficient. Spatial hashing is the stupidly simple solution of just rounding coordinates to…

I didn't think that would be an obscure data structure, but Locality-sensitive hashing [1] helps in so many cases. Like nearest neighbour search, collision detection, etc.

[1]: https://en.wikipedia.org/wiki/Locality-sensitive_hashing

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

#334

Post by ly3xqhl8g9 »

Dwedit wrote: post #232

Here's one I don't know if I've ever seen documented anywhere. If anyone knows a proper name for this one, let me know! Imagine it's for a text editor, and you want to map Line Numbers to Byte Positions. But then you want to insert a byte somewhere, and you need to add 1 to all your Byte Position values. Instead of actually keeping a big array of Byte Position values, you have a hierarchical array. The convention is…

Somewhat along these lines, I have formed a concept forcedly called "differentially composable string", or "deposed string", or more precise "poor man's git".

The intended use case is to obtain a compact representation of all the historic text entered into an input field (notes, comments, maybe long-form): all the stages of the text, where a stage is a tuple [add/remove, start_index, text/end_index]. Once you get the stages from the deposed string as JSON, you could transform them however you want then load them into a new deposed string.

You can read more on GitHub: https://github.com/plurid/plurid-data-structures-typescript#... or play around on my note-taking app implementing deposed strings and more: https://denote.plurid.com

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

#335

Post by anonymoushn »

Robin Hood tables are a common-ish hash map implementation that often shows up on benchmarks for fast inserts. Depending on the implementation, a Robin Hood table is also a sorted sparse array! This could be useful for data that needs random access and sequential access to a subset of the sorted data, like an order book.

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

#337

Post by _trackno5 »

Not really obscure, but I had never heard of it till recently (and most people I've talked had no idea about it): Difference Arrays.

Great for when you need to do ranged updates in constant time.

More info: https://codeforces.com/blog/entry/78762

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

#338

Post by jdthedisciple »

ralusek wrote: post #312
skrebbel wrote: post #297

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 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)

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

#339

Post by sph »

paskozdilar wrote: post #322

I've had a situation where I needed to stream blocks of data from a remote computer in soft-realtime, but still needed to share the same data with many different consumers. The code was simple, but effective (Go): import "sync" type Muxer[T any] struct { ret T mut sync.RWMutex } func (c *Muxer[T]) Multiplex(fn func() T) (ret T) { if c.mut.TryLock() { defer c.mut.Unlock() ret = fn() c.ret = ret } else { c.mut.RLock()…

I don't get it. It seems overengineered to me, but I can't formulate my reasoning well enough.

Why isn't the original value that you're returning protected by a RWLock, and all goroutines will just need to acquire a read lock, instead of using a write lock for what is basically a getter function?

Yeah, I don't get it.

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

#340

Post by nvarsj »

Probabilistic data structures are pretty cool.

Count-min sketch [1] is another one. It gives a reasonably accurate count of different events, even millions of unique events, in a fixed memory size. It shows up a bunch in high volume stream processing, and it's easy to understand like the bloom filter.

Another cool data structure is HeavyKeeper [2], which was built as an improvement on count-min sketch for one of its use cases: ranking the most frequent events (like for a leaderboard). It can get 4 nines of accuracy with a small fixed size even for enormous data sets. It's implemented by Redis's topk.

[1]: https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch

[2]: https://www.usenix.org/system/files/conference/atc18/atc18-g...

Post reply on HN