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

541–550 of 772 posts

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

#541

Post by bschaeffer »

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 wrote a version of this with Elixir: https://github.com/bschaeffer/til/tree/master/elixir/gen_ser...

Didn't know what to call it but PromiseMaps is nice name for it.

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

#542

Post by Gravityloss »

Don't know if it fills the criteria, but some very basic concept: Circular arrays.

This is great for live updated time series data: you never have to expand your arrays, allocate memory etc. It is extremely fast, predictable and resource efficient.

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

#543

Post by JackFr »

jiggawatts wrote: post #25

Cache-Oblivious Data Structures: https://cs.au.dk/~gerth/MassiveData02/notes/demaine.pdf A vaguely related notion is that naive analysis of big-O complexity in typical CS texts ignores over the increasing latency/cost of data access as the data size grows. This can't be ignored, no matter how much we would like to hand-wave it away, because physics gets in the way. A way to think about it is that a CPU core is like a…

I saw an amazing presentation on Purely Functional Data structures with a really approachable and understandable proof on ho w a particular structure was asymptotically constant or linear time (I believe), and then followed up by saying that in practice none of it worked as well as a mutable version because of caching and data locality.

Oh well.

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

#545

Post by robertsdionne »

robertsdionne wrote: post #329

Posit numbers (a better floating point representation): https://www.johndcook.com/blog/2018/04/11/anatomy-of-a-posit... https://www.johngustafson.net/pdfs/BeatingFloatingPoint.pdf

Also, Learned Indexes Structures:

The Case for Learned Index Structures: https://arxiv.org/abs/1712.01208

Learned Indexes for a Google-scale Disk-based Database: https://arxiv.org/abs/2012.12501

And Noms/Dolt Prolly Trees:

How to Chunk Your Database into a Merkle Tree: https://dolthub.com/blog/2022-06-27-prolly-chunker/

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

#546

Post by Retr0id »

Gravityloss wrote: post #542

Don't know if it fills the criteria, but some very basic concept: Circular arrays. This is great for live updated time series data: you never have to expand your arrays, allocate memory etc. It is extremely fast, predictable and resource efficient.

Also known as ring buffers

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

#547

Post by strawhatguy »

I actually got to use a k-d tree before, I was naïvely brute forcing tiles together according to their 2d positions, the tiles being part of a larger image, and it was perfect.

Would run out of memory on a 96gb machine before, after it could process the tiles as quick as they came in from the camera, only a couple held in memory at a time.

When you have the right data structure, man it’s like night and day performance!

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

#548

Post by balls187 »

epolanski wrote: post #513
JimDabell wrote: post #475

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

It's not the cost of saving the resolved data.

If I understand the pattern correctly, it is to avoid multiple asynchronous requests to a resource that has yet to be cached.

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

#549

Post by sicp-enjoyer »

Sesse__ wrote: post #406
sicp-enjoyer wrote: post #137

Earlier quoted context omitted.

C++ STL uses trees because the generic requirement for them to work is a Ironically, due to caches, sorting and then using algorithms that rely on order tend to be superior than most hashing implementations, even though they are theoretically worse due to log(n) factor. So in a way, C++ algorithms are actually more modern.

> Ironically, due to caches, sorting and then using algorithms that rely on order tend to be superior than most hashing implementations This doesn't match my experience at all. C++ trees are not cache-friendly; they're pointer-chasing (and there's no arena implementation in the STL). Second, any sort of ordering structure (be it through a tree or through sorting + binary search) is notoriously prone to branch mispred…

> C++ trees are not cache-friendly

Agreed, they should use a B-tree to get cache locality and easy generics, but there is legacy code there.

I was referring to the performance of algorithms. For example `std::unique`, `std::lower_bounds`, etc. Many of these use sorted lists, whereas most other languages' standard libraries utilize hashing for these.

> is also comfortably ahead of something like std::lower_bound on a sorted array

I would be interested to learn more about when that's the case. But, it's also not very flexible. You can put an `int` in it, great. Can you put `std::pair` in it? Does it work as well?

Post reply on HN