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

31–40 of 772 posts

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

#31

Post by drinkcocacola »

groby_b wrote: post #15

All probabilistic structures are fascinating to me. I'm most enamored with HyperLogLog - estimating the number of distinct elements in extremely large sets of data without having to build a set of seen elements - but the entire field is pretty awesome. The canonical use case for HLL is counting unique visitors. But any large dataset where you only need a good approximation is a valid target :)

I used to work for a mobile analytics company, and HLL made things SO much easier and fast that at the time we changed all our queries to be based on HLL. At the time, the ability of being able to sum uniques was like black magic, and still to this day I am quite impressed about HyperLogLog.

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

#33

Post by vosper »

kgeist wrote: post #14
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 like a priority queue

Is it the same thing? I'm trying to imagine how this would work with a priority queue.

I think you need an flexible number of priorities that is equal to the queue length, and the priority values come from an infinite counter that only goes up. Higher values = lower priority.

When a unique item comes into the queue you increment the counter and give it that value as a priority. This puts it on the end of the queue.

But if the new item is a duplicate of an existing item then you give it the priority of the existing item.

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

#34

Post by sgtnoodle »

ajjenkins wrote: post #29

I recently learned about deques in Python (other languages may have it too) which is like a linked list but it keeps pointers for the first and last elements. This allows you to insert/read/remove elements from the beginning or end of the list in constant time. I’ve never used it, but I could imagine it being useful in certain situations. https://docs.python.org/3/library/collections.html

A deque may be implemented as a linked list, but it's actually more common to be implemented on top of arrays.

Python in particular uses arrays under the hood for almost everything because modern computer hardware is so blazingly fast manipulating them.

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

#35

Post by [deleted] »

kgeist wrote: post #14
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 like a priority queue

[deleted]

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

#37

Post by rockwotj »

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

Do you have any documentation about how tries are used in mongo indexes? Or could you point to the source?

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

#38

Post by maxFlow »

rockwotj wrote: post #32

Interval trees. Really cool trees that allow fast lookups of all the ranges that contain a given point. https://en.wikipedia.org/wiki/Interval_tree

Found out about this DS in AoC 2021 Day 20+ problems if I remember correctly. Pretty interesting.

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

#39

Post by Tmpod »

kgeist wrote: post #14
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 like a priority queue

Not really. In a priority queue, an item with higher priority gets pulled out before one with lower priority, so you can have items that skip parts of the queue (or all of it) even if there are no items of the same priority in there already.

This structure seems to behave differently, in that an item may skip ahead in the queue if and only if another item with some matching characteristic is already contained. This makes it so you can never skip the whole structure, for example, assuming you get put after your "friend".

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

#40

Post by bmitc »

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?
Post reply on HN