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

711–720 of 772 posts

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

#711

Post by clashmeifyoucan »

MichaelMoser123 wrote: post #478
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…

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

a textbook example of an algorithm that works very well with union-find is the kruskal's algorithm to find the minimum weight spanning tree given a graph. Using union-find improves the time complexity of the algorithm from O(V²) to O(ElogV).

This happens because kruskal's algorithm essentially selects the cheapest edge not already included in our spanning tree that won't cause a cycle. So union-find is able to speed up this potential cycle check which would otherwise be naively quadratic.

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

#713

Post by afiori »

feoren wrote: post #667
dan-robertson wrote: post #652

Earlier quoted context omitted.

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?

The reason not to do it is to limit the non-determinism of the order of execution.

In Javascript

    f1();
    p.then(f3);
    f2();
functions are always called in the relative order f1, f2, f3 and never f1, f3 , f2 even if p had already resolved.

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

#714

Post by idontwantthis »

unsupp0rted wrote: post #434
idontwantthis wrote: post #330

Earlier quoted context omitted.

It’s also the clearest and least buggy way to iterate over the results. Map over Await Promise.all(map).

Partly off-topic, but in JS I tend to avoid iterating over promises with maps because it's always confusing what will/won't work, so I use a basic FOR loop because async/await works in there. How bad is this? Should I switch to Promise.all instead?

Use my approach or yours, but never use forEach with await. I don’t remember exactly why, but it just doesn’t work and will lead to very confusing errors.

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

#716

Post by meowtimemania »

idontwantthis wrote: post #714
unsupp0rted wrote: post #434

Earlier quoted context omitted.

Partly off-topic, but in JS I tend to avoid iterating over promises with maps because it's always confusing what will/won't work, so I use a basic FOR loop because async/await works in there. How bad is this? Should I switch to Promise.all instead?

Use my approach or yours, but never use forEach with await. I don’t remember exactly why, but it just doesn’t work and will lead to very confusing errors.

Because Array.forEach doesn’t return a value or anything that could be awaited. If you use Array.map you can create an Array of promises that can be awaited with Promise.all

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

#717

Post by thaumasiotes »

kragen wrote: post #695
thaumasiotes wrote: post #685

Earlier quoted context omitted.

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

You are welcome to think about the union-find structure however you prefer to think about it, but I was describing the problem I was trying to solve, for which the correct description of union find I gave above is optimal. Contrary to your mistaken assertion, no contradictions arise from applying graph-theoretical concepts in this way; there is no problem of "coherency". It's just a form of description you aren't acc…

> You are welcome to think about the union-find structure however you prefer to think about it, but I was describing the problem I was trying to solve, for which the correct description of union find I gave above is optimal.

> If your way of thinking about union find makes it hard for you to understand the problem I was trying to solve, maybe it isn't the best way to think about it for the purpose of this conversation, even if it is the best way to think about it in some other context.

I'm not having any problems understanding the problem you were trying to solve. My problems are in the area of understanding why you thought a union-find might be an effective way to address that problem.

I'm telling you that, if you adjust your view of what a union-find is, you will have a better conception of where it can and can't be usefully applied.

> In general there is a very close correspondence between binary relations and digraphs, so it's usually easy to reformulate a statement about relations as an equivalent statement about digraphs, and vice versa. But one formulation or the other may be more perspicacious.

In this case, the relation is symmetric by definition, so you just have graphs. Yes, it's obvious how you can use a graph to describe a relation.

But the entire point of the union-find structure is to discard any information contained in an equivalent graph that isn't contained in the relation. (And there are many equivalent graphs, but only one relation!) The absence of that information is what makes the structure valuable. It shouldn't be a surprise that, if you want to preserve information from a particular graph, you are better served with graph-based algorithms.

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

#718

Post by kragen »

thaumasiotes wrote: post #717
kragen wrote: post #695

Earlier quoted context omitted.

You are welcome to think about the union-find structure however you prefer to think about it, but I was describing the problem I was trying to solve, for which the correct description of union find I gave above is optimal. Contrary to your mistaken assertion, no contradictions arise from applying graph-theoretical concepts in this way; there is no problem of "coherency". It's just a form of description you aren't acc…

> You are welcome to think about the union-find structure however you prefer to think about it, but I was describing the problem I was trying to solve, for which the correct description of union find I gave above is optimal. > If your way of thinking about union find makes it hard for you to understand the problem I was trying to solve, maybe it isn't the best way to think about it for the purpose of this conversatio…

Well, that's an interesting way to look at it; I see better where you're coming from now.

But I wasn't trying to get the unmodified data structure to handle deletion efficiently; I was trying to use it as a basis to design a structure that could. I thought I saw a minor modification that achieved this, but then I found out why it doesn't work. That's what my linked note above is about.

More generally, if you only try things that will probably work, you'll never achieve anything interesting.

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

#719

Post by rcpt »

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…

Neat use of these is the "fast multipole method" for stimulating galaxies.

If you want to compute the gravitational force on a given star exactly you need to figure out the forces from all other stars and add them up. This will be n^2 and slow. But turns out you can get a good approximation by dividing up space with a kd tree and using the average force from each cell to represent the stars underneath it in the tree. This gets you to nlogn

https://en.m.wikipedia.org/wiki/Fast_multipole_method

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

#720

Post by chakkepolja »

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…

http://queue.acm.org/detail.cfm?id=1563874

http://deliveryimages.acm.org/10.1145/1570000/1563874/jacobs...

Post reply on HN