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

301–310 of 772 posts

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

#301

Post by kragen »

progval wrote: post #251
Dwedit wrote: post #244

Earlier quoted context omitted.

That's good for representing the text, but I'm more focused on the part about being able to add X to everything past a particular point very quickly by manipulating parent values.

Ropes do this too; each node is labeled the size of its subtree. If you want to compute line numbers as well, add them as another label

That kind of thing is a common extension to ropes, because it makes them indexable containers like arrays, but it is not inherent to the definition of ropes. I don't think it's mentioned in the original Cedar rope paper.

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

#302

Post by throwaway17_17 »

moonchild wrote: post #218
throwaway17_17 wrote: post #146

Earlier quoted context omitted.

I have seen this general pattern in several decently large game object systems, although I can’t think of which ones off hand, if I’m recalling correctly it tend to be used in the longer lived (aka 10s of frames) object status/object existence checks, and often in AI subsystems, pathing and general decision making queries, etc.

Seems like games are an 'easy' case for this kind of thing, since you can synchronise every frame, and arbitrate destruction then; no?

For the most part. I think most of the usage was to allow more dynamic ‘objects’ and queries on them to be used in a low friction way without worrying about generational validity checks or null checks when reading data from those objects. It a lot like implementing a deterministic GC for a small set of memory objects.

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

#304

Post by kqr »

Not particularly innovative, but extremely useful: HDRHistograms let you very efficiently create, combine and query empirical probability distributions.

If I'm doing anything with random or random-looking variation, I prefer to store the full distribution in a HDRHistogram rather than just the last value, last few values, mean value, or whatever. Opens up so many possibilities for analysis later down the road.

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

#305

Post by btschaegg »

petethepig wrote: post #3

Tries (or prefix trees). We use them a lot at Pyroscope for compressing strings that have common prefixes. They are also used in databases (e.g indexes in Mongo) or file formats (e.g debug symbols in macOS/iOS Mach-O format are compressed using tries). We have an article with some animations that illustrate the concept in case anyone's interested [0]. [0] https://github.com/pyroscope-io/pyroscope/blob/main/docs/sto..…

Indeed, but it took a while for me to appreciate Tries.

Originally, i thought "nice idea", but I rarely ever encountered a problem where I really needed a prefix tree.

But while reading into HAMT and Clojure's datastructure implementations, it dawned on me that prefix trees aren't only useful for strings (or arbitrary byte sequences): Hashes in a dictionary, for example, are sequences of bits, too. And the design of a HAMT is exactly such that it doesn't concern itself with bytes but any blocks of N bits (determined by the branching factor; i.e. a factor of 32 implies 6-bit-blocks). And if you know the length of each sequence (hash), you know the maximum Trie depth, which also works for you, not against you.

That was rather eye opening for me at the time.

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

#306

Post by sgtnoodle »

sicp-enjoyer wrote: post #140
sgtnoodle wrote: post #72

Earlier quoted context omitted.

Neat, it's always best to look at the source. To be clear, a deque can be implemented on top of an array and still have constant time operations on the head.

If it's not constant time on both ends, it's not a deque. You can already insert items at any index in an array with linear cost.

I invite you to think about the problem for a while, and try to think of a way to implement a performant deque on top of a resize-able array. I promise you it's possible.

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

#308

Post by aliceryhl »

Link cut trees. They can be used to query information about paths in a forest, while also allowing you to add and remove edges in the forest.

For example, you could use them to store the minimum spanning tree of a graph, while supporting updates if edges are added to the graph.

They can also be used to speed up max flow algorithms by finding the augmenting path in logarithmic time.

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

#309

Post by eutectic »

endgame wrote: post #246
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 heard stories about annotating the edges with elements from a group rather than using unlabelled edges. Have you heard anything about that?

You can efficiently maintain count/max/sum/hash/etc. for each component. It's occasionally useful.

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

#310

Post by xxs »

sgtnoodle wrote: post #30

Disruptor queues are also fun. They are lock free multi-producer multi-consumer circular buffers. I figured out the basics on my own in a vacuum out of need, then discovered a relevant white paper. I used one to implement a fast shared memory pub-sub message bus for communicating across dozens of processes in a simulation framework.

I don't quite see how's that obscure; it's a standard circular buffer. The fast/low latency communication part comes from the busy wait (and L3 cache communication).
Post reply on HN