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

651–660 of 772 posts

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

#651

Post by thaumasiotes »

kragen wrote: post #273
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…

My writeup of union find is in https://dercuano.github.io/notes/incremental-union-find.html . I did not in fact find a way to make it efficiently support incremental edge deletion, which is what I was looking for.

> I did not in fact find a way to make it efficiently support incremental edge deletion, which is what I was looking for.

I don't understand this goal. The interior connections aren't relevant to a union-find structure; ideally you have a bunch of trees of depth 2 (assuming the root is at depth 1), but the internal structure could be anything. That fact immediately means that the consequence of removing an edge is not well-defined - it would separate the two objects joined by the edge, and it would also randomly divide the original connected set into two connected sets, each containing one of those two objects. Which object each "third party" object ended up being associated with would be an artifact of the interior structure of the union-find, which is not known and is constantly subject to change as you use the union-find.

If all you want is to be able to remove a single object from a connected set, on the assumption that your union-find always has the ideal flat structure, that's very easy to do - call find on the object you want to remove, which will link it directly to the root of its structure, and then erase that link.

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

#652

Post by dan-robertson »

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 schedule your .then function) you can get weird semantic bugs.

- changing the keys of the table incrementally instead of just using for memoisation can be really messy

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

#653

Post by vnorilo »

One of my favourites is treap [1], which doubles as a great excuse to forget how to balance binary trees. It is similarly "probably efficient" as HAMT, mentioned in other comments; both require a well-behaving distribution in the hash function.

1: https://en.m.wikipedia.org/wiki/Treap

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

#654

Post by anyfoo »

marcosdumay wrote: post #648
hn_throwaway_99 wrote: post #622

Earlier quoted context omitted.

not really quite lazy evaluation, thought, at least in Javascript. Promises begin execution as soon as they are created and there is no way to delay that.

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 problem--that's exactly what WHNF says). If not, we evaluate it down to WHNF.

Wikipedia states it as: "When using delayed evaluation, an expression is not evaluated as soon as it gets bound to a variable, but when the evaluator is forced to produce the expression's value."

So if evaluation begins effectively at the time the promise is issued, not at the time the promise is awaited, then I would not call that lazy evaluation, and what hn_throwaway_99 said sounds correct to me.

Is my rusty old PL understanding wrong?

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

#655

Post by [deleted] »

marcosdumay wrote: post #648
hn_throwaway_99 wrote: post #622

Earlier quoted context omitted.

not really quite lazy evaluation, thought, at least in Javascript. Promises begin execution as soon as they are created and there is no way to delay that.

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.

[deleted]

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

#656

Post by bloudermilk »

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…

Best practice in my experience is to use a timeout on all async operations to handle edge cases 1 & 2 above. The third case isn't possible with JavaScript AFAIK.

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

#657

Post by jll29 »

Associative memory? Store data in them and they will never complain they are full, but they may "forget" instead. Querying them with slightly wrong keys, they'll auto-correct the keys as long as they are not overloaded.

Binary fuse filters? (Xor|Bloom) filters on steroids.

Non-deterministic finite state transducers? Reversible, more elegant and more powerful version of non-deterministic finite state recognizers (transitions are labelled with two outputs, which can be interpreted as inputs versus outputs, but these roles can be swapped as they are symmetric).

Ropes? What, you are still using strings? Dude, please stop writing that newbie editor.

Caches with Time aware least recently used (TLRU) or Segmented LRU (SLRU) cache replacement strategies (Oh, you thought Least recently used (LRU) was cool?)

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

#658

Post by cstrahan »

marcosdumay wrote: post #648
hn_throwaway_99 wrote: post #622

Earlier quoted context omitted.

not really quite lazy evaluation, thought, at least in Javascript. Promises begin execution as soon as they are created and there is no way to delay that.

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.

Definition on Wikipedia says otherwise:

“In programming language theory, lazy evaluation, or call-by-need,[1] is an evaluation strategy which delays the evaluation of an expression until its value is needed (non-strict evaluation) and which also avoids repeated evaluations (sharing).”

Haskell would be an apt example here.

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

#659

Post by kube-system »

hmm-interesting wrote: post #636
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…

can you please explain this a bit more how this avoid fetching the same value twice? maybe with example.

It sounds like, if you have a process that takes a long time to do, you check to see if you already have initiated that process (see if the key is in the list of promises), rather than firing off another promise for the same request.

If you get 10 requests to fire function lookUpSomethingThatTakesAWhile(id) that returns a promise, rather than firing off 10 promises, you fire it off once, look up the ID in your map for the next nine, and return that same promise for the next 9.

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

#660

Post by talos2110 »

psytrx wrote: post #647
talos2110 wrote: post #608

Earlier quoted context omitted.

That right there is Cache Stampede[0] prevention. [0]: https://en.wikipedia.org/wiki/Cache_stampede

Interesting! This is an issue I had with an external API which I intended to cache on my serverless workers infra. I hit the API's rate limiter when the workers invalidated their cache, even though I staggered the lifetime of the cache keys for each replicated instance. This is how I found out how many Cloudflare workers run on a single edge instance. Hint: It's many. Didn't know it had a name. I'm delighted, thanks!

You’re welcome, happy to help. If you are in the .NET space I suggest you to take a look at FusionCache. It has cache stampede protection built in, plus some other nice features like a fail-safe mechanism and soft/hard timeouts https://github.com/jodydonetti/ZiggyCreatures.FusionCache
Post reply on HN