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

41–50 of 772 posts

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

#41

Post by OJFord »

NSMutableSet wrote: post #19
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..…

I wouldn't consider tries to be obscure tbh. They are the recommended solution for many leetcode-style interview problems involving string searching. I think anyone who has done serious interview prep has encountered them. https://leetcode.com/discuss/general-discussion/931977/begin...

The starting example was Bloom filters.

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

#42

Post by vvanders »

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…

Realtime collision detection[1] has a fantastic chapter in this with some really good practical examples if I remember right.

Great book, I used to refer to it as 3D "data structures" book which is very much in theme with this thread.

[1] https://www.amazon.com/Real-Time-Collision-Detection-Interac...

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

#43

Post by actually_a_dog »

Previously on HN:

https://news.ycombinator.com/item?id=1370847 (2010)

https://news.ycombinator.com/item?id=2363522 (2011)

https://news.ycombinator.com/item?id=3369454 (2011) -- Although not much is in the discussion, it points to a Stack Overflow post with some examples.

https://news.ycombinator.com/item?id=7079427 (2014)

https://news.ycombinator.com/item?id=28758106 (2021) -- Not exactly a data structure, but an interesting algorithm.

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

#44

Post by kaylynb »

Sparse sets.

They're often used in Entity Component System architectures since you have O(1) add/remove/find, & O(n) iteration. Iterations are also packed, which is a bonus for cache efficiency.

Can be difficult to implement well, but the concept is simple and a neat example of a useful specialty data structure. Take a look at https://github.com/skypjack/entt

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

#45

Post by sgtnoodle »

bmitc wrote: post #40
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.

Do you have a link to the white paper you found?

This doesn't look like I remember, but this sounds right.

https://lmax-exchange.github.io/disruptor/disruptor.html#_de...

The basic idea is that you maintain two atomically incremented counters. You increment one to allocate some buffer space to write your message into, and you increment the other once the message is written in. There's some tricky details to get right when multiple producers have messages staged up at the same time.

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

#47

Post by teraflop »

llimos wrote: post #4

The Israeli queue. Like a regular queue, but if something new that comes in sees its friend in the queue already, it can jump the queue and go and stand next to her. Useful for when something has a big overhead on top of its own processing, but the overhead can be shared between several similar entries. If you're doing it anyway for the one already in the queue, you get to make the most of it for its friends too. I c…

Sounds similar to the behavior of Guava's LoadingCache. If you try to fetch a key that's not in the cache, the supplied callback is used to fetch it. While the value is being loaded, other threads can access the cache concurrently, but if a second thread asks for the same key, it will wait for the first load to complete instead of redundantly fetching the same value.

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

#48

Post by scottcodie »

Reservoir sampling is a statistical technique used to randomly select a finite number of elements from a population. The elements are chosen such that each element has an equal probability of being selected. This technique is often used when it is impractical to select a random sample of elements from a very large population.

To do reservoir sampling, you first need to decide how many items you want in your sample. This number is called the size of the reservoir. Once you have the size of the reservoir, you can fill it by selecting items from the population at random.

The code is beautifully simple:

  for i = k to population.length-1
    j = random integer between 0 and i, inclusive
    if j

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

#49

Post by EnderShadow8 »

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

It's like a Red-Black tree in use case, but much faster to implement, which is good for competitive programming. The average case complexity is the same for all operations, but there's an unlikely degeneration to worst-case linked-list behaviour.

Lazy Propagation Segment Tree: https://cp-algorithms.com/data_structures/segment_tree.html

Like a segment tree in that it supports range queries in logarithmic time, but supports range updates in log time as well.

I know a few more fun ones that I occasionally use in contests, but I've never touched otherwise.

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

#50

Post by reality_inspctr »

Resource Description Framework (RDF)

The Resource Description Format (RDF) is the W3C standard for web data. It allows for data the be linked, anywhere, and to be "grounded" in semantic descriptions of the data. The core RDF data model is very simple: It is a set of triples orgainzed into a RDF Graph.

https://www.w3.org/egov/wiki/Resource_Description_Format

Post reply on HN