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

681–690 of 772 posts

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

#681

Post by NavinF »

cratermoon wrote: post #640
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…

> the increasing latency/cost of data access as the data size grows Latency Numbers Everyone Should Know https://static.googleusercontent.com/media/sre.google/en//st...

The ratios are mostly correct, but the absolute numbers are wrong these days. For example, memory read latency can be 45ns (not 100) with a decent DDR4 kit and data center latency can be 10us (not 500us) with infiniband.

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

#682

Post by bhl »

filoeleven wrote: post #266
jahewson wrote: post #211

Earlier quoted context omitted.

That’s what Immutable.js used under the hood.

Yes, I evaluated it. The complexity of knowing where to convert from/to plain JS, plus the extra library syntax to learn, plus the performance cost of toJS, made it a poor fit for my particular use case. Nearly as much of a hard sell at work as saying “let’s rebuild the UI in Clojurescript,” and without providing as much benefit. My use case is pretty atypical though, and it’s worth checking out if you have more reli…

Does immer have the same drawbacks as immutable? It uses proxies as opposed to hased array map tries.

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

#684

Post by wxnx »

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 wrote some Python code recently that uses a similar data structure (Futures instead of Promises, without knowing necessarily about the data structure's use in JavaScript). It wasn't really for caching.

I modeled mine on the Django ASGI reference library's server implementation, which uses the data structure for maintaining references to stateful event consumers. Exception handling is done with a pre-scheduled long-running coroutine that looks at the map.

I'm curious about your second point -- why exactly do things get bad with high tail latency? Is it only a weakness of the data structure when used for caching? I'm having trouble picturing that.

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

#685

Post by thaumasiotes »

kragen wrote: post #674
thaumasiotes wrote: post #651

Earlier quoted context omitted.

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

Union find takes as input some undirected graph N , E > and internally constructs (and progressively mutates) a directed graph N , E '> which it uses to efficiently answer queries about whether two nodes n ₁, n ₂ ∈ N are in the same connected component of N , E >. It additionally supports incrementally adding edges to E . My quest was to find a way to incrementally delete edges from E , not E '. You're talking about…

> Union find takes as input some undirected graph and internally constructs (and progressively mutates) a directed graph which it uses to efficiently answer queries about whether two nodes n₁, n₂ ∈ N are in the same connected component of .

I don't think this is a valuable way to think about the structure. That's not what it's for.

A union-find is a direct representation of the mathematical concept of an equivalence relation. The input is a bunch of statements that two things are equal. It will then let you query whether any two things are or aren't equal to each other.

This is captured well by the more formalized name "disjoint-set structure". You have a set of objects. You can easily remove an element from the set. But it makes no conceptual sense to try to "separate two of the elements in a set". They're not connected, other than conceptually through the fact that they are both members of the same set.

A union-find is a good tool for answering whether two vertices are in the same connected component of a graph because being in the same connected component of a graph is an equivalence relation, not because the union-find is a graph-related concept. It isn't, and there is no coherent way to apply graph-theoretical concepts to it.

Putting things another way:

You describe a union-find as something used to "efficiently answer queries about whether two nodes n₁, n₂ ∈ N are in the same connected component of [a graph]".

But you focused on the wrong part of that statement. What makes a union-find appropriate for that problem is the words "the same", not the words "connected component".

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

#686

Post by zachrip »

nemo1618 wrote: post #229

My contribution: the Binary Numeral Tree: https://eprint.iacr.org/2021/038 This is a tree-like structure where the structure of the tree is fully determined by the number of leaves N. Specifically, each 1-bit in the binary representation of N corresponds to one of the tree's perfect binary subtrees. For that reason, I think of it more as "structure imposed upon a list" rather than a typical mutable tree with pointers…

Can you dumb this down for me?

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

#687

Post by jitl »

ksbrooksjr wrote: post #228
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…

If the Record & Tuple proposal advances to stage 3 we'll finally have native immutable data structures in JS [1]. [1] https://github.com/tc39/proposal-record-tuple

I have beeen waiting aeons for this, and suspect will need to continue waiting effectively forever :(

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

#688

Post by brewmarche »

epolanski wrote: post #530
pdpi wrote: post #422

Earlier quoted context omitted.

Promises are not monads, for one simple reason: they're not referentially transparent. The whole point of OP's example is to double down and take advantage of that.

Referential transparency is a property of expressions, not type classes. Referential transparency is nowhere in the definition of a monad because a monad is obviously not an expression but a type class. It is definitely true that Promise is a data type that _could_ admit a monad instance. It has: - a data type M a which is Promise a - a function pure with the signature a => M a, which is x => Promise.resolve(x) - a b…

Maybe comonads fit better

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

#689

Post by l33t2328 »

cvoss wrote: post #147
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…

> In essence, as data size 'n' grows, the random access time grows as sqrt(n), because that's the radius of the growing circle with area 'n'. I was about to write a comment suggesting that if we made better use of three dimensional space in constructing our computers and data storage devices, we could get this extra latency factor down to the cube root of n. But then, I decided to imagine an absurdly large computer.…

How do you accurately include those sqrt(n)’s in your analysis?

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

#690

Post by almog »

almog wrote: post #459

The Hierarchical Timing Wheels is an efficient data structure/algorithm for managing timers (event scheduling) when: 1. The timers variance is large. 2. Timers are likely to be cancelled. 3. A fixed (configurable) precision is configurable. This talk provides a nice overview of different timing wheels implementations including hierarchial and hashed timing wheels.

Too late to edit but I forgot to paste the link to the timing wheels overview talk that I mentioned, so here it is:

https://www.youtube.com/watch?v=AftX7rqx-Uc

Post reply on HN