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

381–390 of 772 posts

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

#381

Post by compressedgas »

Dwedit wrote: post #279

Here's another one I was thinking about. It's an idea for a hierarchical Free Space Bitmap. I don't know if anything like this has appeared in a real file system or not. At the lowest level, let's have one bit represent if a 4K chunk is free space or occupied. 64 bits at this level tells you the usage of 64 * 4096 bytes (256KB) Then Level 2. Two arrays. One bit at this level represents 64 bits in the level 1 array. O…

This reminds me of libswift's binmaps: https://github.com/gritzko/swift/blob/master/doc/binmaps-ale...

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

#383

Post by eru »

kragen wrote: post #271

Here's a few fun ones: the Burrows–Wheeler transform, suffix arrays in general, Kanerva's fully distributed representation, reduced-affine-arithmetic numbers, LSM trees, binary array sets, sparse array sets, and gap buffers. (I'm not sure how nobody had mentioned gap buffers yet on the thread, but if they did I didn't see it.) — ⁂ — The Burrows-Wheeler transform is the second character of each suffix in a (cyclic) su…

> Much better advice is found in The Practice of Programming: almost all programs can be written without any data structures but arrays, hash tables, linked lists, and, for things like parsing, symbolic algebra, or filesystems, trees. So just use those if you can.

In general, as much as possible use stuff you already have good libraries for.

Often, you can get away with much simpler data structures with a bit of clever pre-sorting (or sometimes: random shuffling). Relatedly, batching your operations can also often make your data structure needs simpler.

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

#384

Post by eru »

Soft heaps are pretty neat. They are like normal min-heaps, but support all operations you care about in O(1) instead of O(log n) time. The catch is that they are allowed to make a configurable proportion of errors.

They are basically only useful in theory, not in practice. They allow construction of some asymptotically optimal algorithms.

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

#385

Post by twic »

slazaro wrote: post #328

I don't know whether it already exists or if it has a name, but internally I call it Virtual List. - Reasoning: It's used in cases where you'd ideally use an array because you want contiguous memory (because you'll usually iterate through them in order), but you don't know beforehand how many elements you'll insert. But you can't use a resizeable version like std::vector, because it invalidates any pointers to the el…

I think you're describing an unrolled linked list: https://en.wikipedia.org/wiki/Unrolled_linked_list

Although specifically, in an unrolled linked list, the blocks are connected by a chain of pointers from one to the next. You can alternatively just keep pointers to each block in a top-level array. it's not clear from your description which you're doing.

The JDK has a twist on the latter, which it calls a spined buffer, where the blocks double in size every time one is added, which makes sense if you have absolutely no idea how many elements there will be when you start.

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

#386

Post by manuelabeledo »

nly wrote: post #366
manuelabeledo wrote: post #361

Earlier quoted context omitted.

Yeah, either that or you implement your own. Doing so with reference counts might not be too hard, though.

The reference count on each element would presumably require atomic operations that could race with those used to update the actual data structure, and therefore you'd lose all your concurrency guarantees?

Generally speaking, this shouldn't be an issue if you perform batch collections.

Either way, any new mechanism to release memory would need to take into account both the generation and the reference count, and the atomic release should be performed in the same GCAS fashion.

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

#388

Post by twic »

tresil wrote: post #275
loxias wrote: post #64

(Fantastic post idea OP. One of the best I've ever seen :D) Related to bloom filters, xor filters are faster and more memory efficient, but immutable. HyperLogLog is an efficient way to estimate cardinality. Coolest thing I've learned recently was Y-fast trie. If your dataset M is bounded integers (say, the set of all 128 bit numbers), you get membership, predecessor, or successor queries in log log time, not log, li…

Big fan of HLL Apache foundation has a fantastic DataSketches library that includes HLL and many other powerful data analytics algorithms: https://datasketches.apache.org/ Lee Rhodes has done an excellent introduction to this library - explaining some of the use cases, advantages, and things to be aware of when using these techniques: https://www.youtube.com/watch?v=nO9pauS-mGQ

On sketches, there is a genre of structure for estimating histogram-like statistics (median, 99th centile, etc) in fixed space, which i really like. Two examples:

t-digest https://github.com/tdunning/t-digest

DDSketch https://github.com/DataDog/sketches-java

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

#390

Post by stevefan1999 »

https://en.wikipedia.org/wiki/Fibonacci_heap?wprov=sfla1

Fibonacci heap is theoretically better than Binary heap but the cache behavior is terrible

https://en.wikipedia.org/wiki/Van_Emde_Boas_tree?wprov=sfla1

Well, I saw this in CLRS tho. Very clever way of abusing bit patterns for quick range query in O(log log M) where M is the integer size.

https://en.wikipedia.org/wiki/Suffix_array?wprov=sfla1

A simpler way to do text matching since suffix array is the preorder traversal of a suffix trie constructed using the same string. Not heavily used in practice, but I do know bioinfo people used it a lot.

https://study.com/academy/lesson/robin-hood-hashing-concepts...

Not a data structure, but still very underrated. Robinhood hash basically means you keep the first insertion order and the actual insertion order and compare their distance. Once the difference is bigger than expected, you put it in front to "steal from the rich" to have better expected access distribution, hence Robinhood. Getting more prominent today thanks to Rust popularizing it again, since the default hash table implementation of Rust uses hashbrown which uses Robinhood hashing scheme.

https://en.wikipedia.org/wiki/Skip_list?wprov=sfla1

The ordered linked list with a fast lane every log(n) level. Not used very much, but one of the place I know uses it is Redis

https://en.wikipedia.org/wiki/Double-ended_priority_queue?wp...

Basically one priority queue that does two things. Can ironically be implemented with two priority queues (dual)

Post reply on HN