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

661–670 of 772 posts

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

#661

Post by hinkley »

dan-robertson wrote: post #652
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…

Be careful with this data structure. If the language allows async exceptions or you have a big where the promise won’t become deferred, there are a lot of edge cases. Examples of edge cases: - if the promise never becomes determined (eg bug, async exception) your app will wait forever - if the promise has high tail latency things can be bad - if the language eagerly binds on determined promises (ie it doesn’t schedul…

I have a couple pieces of code where we had to add rate limiting because it was just too easy to make too many async calls all at once, and things only got 'worse' as I fixed performance issues in the traversal code that were creating an ersatz backpressure situation.

Philosophically, the main problem is that promise caches are a primary enabler of the whole cache anti-pattern situation. People make the mistake of thinking that 'dynamic programming' means memoization and 'memoization' means caching. "Everything you said is wrong." Trying to explain this to people has been a recurring challenge, because it's such a common, shallow but strongly-held misunderstanding.

Youtube recently suggested this video to me, which does a pretty good job of explaining beginning and intermediate DP:

https://www.youtube.com/watch?v=oBt53YbR9Kk

What I love most about this video is that it introduces memoization about 10 minutes in, but by 20% of the way through it has already abandoned it for something better: tabulation. Tabulation is an interative traversal of the problem that gathers the important data not only in one place but within a single stack frame. It telegraphs a information architecture, while recursive calls represent emergent behavior. The reliance on cache to function not only obscures the information architecture, it does so by introducing global shared state. Global shared state and emergent behavior are both poison to the long-term health of a project, and here we have a single data structure that represents both in spades.

We are supposed to be fighting accidental coupling, and especially global variables, not engaging in word games to hide what we are doing.

So I think my answer to OP's question is 'tabulation', which is part data structure and part algorithm.

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

#662

Post by ignoramous »

sfvisser wrote: post #261
filoeleven wrote: post #198

HAMT: Hash Array Mapped Trie. This data structure makes efficient immutable data possible. You can update a list of a million items, and keep a reference to the original list, by changing 3 or 4 references and some bytes. This should replace copy-on-write for scripting languages. I really want to see it in a JS spec soon. There are libraries that can do it, but they add translation penalties and extra steps. I’d comp…

Another interesting approach to copy-on-write for immutable collections (for example arrays) is where you actively mutate the array in place, but leave the original as a lazy description/view of how to get back to the before state. From the outside the effect is the same, but the performance is optimized for accessing the updated collection and only possibly using the old value. Great for cases where you want the imm…

See also this cppcon talk by Juan Pedro https://youtu.be/sPhpelUfu8Q

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

#664

Post by sn9 »

hexomancer wrote: post #289
jtolmar wrote: post #171

The union-find data structure / algorithm is useful and a lot of fun. The goal is a data structure where you can perform operations like "a and b are in the same set", "b and c are in the same set" and then get answers to questions like "are a and c in the same set?" (yes, in this example.) The implementation starts out pretty obvious - a tree where every element either points at itself or some thing it was merged wi…

I have always wanted to really understand this data structure. Sure, I can follow the analysis with the potential functions and all, but I never really understood how Tarjan came up with the functions in the first place. Does anybody have a resource which intuitively explains the analysis?

Robert Sedgewick has a great explanation in his Algorithms book. He has gorgeous diagrams alongside his explanations.

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

#665

Post by hendler »

loxias wrote: post #64

(Fantastic post idea OP. One of the best I've ever seen :D) Related to bloom filters, xor filters are faster and more memory efficient, but immutable. HyperLogLog is an efficient way to estimate cardinality. Coolest thing I've learned recently was Y-fast trie. If your dataset M is bounded integers (say, the set of all 128 bit numbers), you get membership, predecessor, or successor queries in log log time, not log, li…

I like https://en.wikipedia.org/wiki/Cuckoo_filter which allows for delete, unlike Bloom

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

#666

Post by BeetleB »

fumblebee wrote: post #610
MichaelMoser123 wrote: post #478

Earlier quoted context omitted.

Can you give some examples where union-find is applied to great benefit?

A while back I had to perform an entity resolution task on several million entities. We arrived at a point in the algorithm where we had a long list of connected components by ids that needed to be reduced into a mutually independent set of components, e.g. ({112, 531, 25}, {25, 238, 39, 901}, {43, 111}, ...) After much head banging about working out way to do this that wouldn't lead to an out-of-memory error, we fou…

Exactly the same for me. We had a defect management system, and a defect can be connected to others as dupes. We'd have whole chains of dupes. We used union find to identify them.

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

#667

Post by feoren »

dan-robertson wrote: post #652
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…

Be careful with this data structure. If the language allows async exceptions or you have a big where the promise won’t become deferred, there are a lot of edge cases. Examples of edge cases: - if the promise never becomes determined (eg bug, async exception) your app will wait forever - if the promise has high tail latency things can be bad - if the language eagerly binds on determined promises (ie it doesn’t schedul…

- if the language eagerly binds on determined promises (ie it doesn’t schedule your .then function) you can get weird semantic bugs.

What would be an example of this? If the promise has been determined, why not just immediately run the .then function?

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

#668

Post by Sohcahtoa82 »

anyfoo wrote: post #654
marcosdumay wrote: post #648

Earlier quoted context omitted.

Promises are an implementation of lazy evaluation for Javascript. This is exactly lazy evaluation. By the way, lazy evaluation is the one that offers no guarantees about when your code will be executed. If you can delay the execution, it's not lazy.

Wait. I thought lazy evaluation is defined as evaluation at the time a value is needed . After that I think it will then be in Weak Head Normal Form, which can be thought of as "evaluated at its top level"... but I'm a bit rusty. Basically, an expression gets used somewhere (e.g. pattern matched, in the ADT sense). If it's in WHNF, cool, it's evaluated already (subexpressions within may not yet, but that's their prob…

> Wait. I thought lazy evaluation is defined as evaluation at the time a value is needed.

Correct.

You've got it right, GP comment has it wrong.

Lazy does not simply mean "evaluated later". From what I understand, in JS, if you call an async function without `await`, it essentially gets added to a queue of functions to execute. Once the calling function stack completes, the async function will be executed.

A queue of functions to execute does not constitute "lazy evaluation" on its own.

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

#670

Post by abetusk »

Succinct Data Structures [0] [1]. It encompass many different underlying data structure types but the overarching idea is that you want small data size while still keeping "big O" run time.

In other words, data structures that effectively reach a 'practical' entropy lower bound while still keeping asymptotic run time.

[0] https://en.wikipedia.org/wiki/Succinct_data_structure

[1] https://github.com/simongog/sdsl-lite

Post reply on HN