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

351–360 of 772 posts

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

#351

Post by sgtnoodle »

moonchild wrote: post #219
foolswisdom wrote: post #62

Earlier quoted context omitted.

Arrays aren't efficient when you want to add/remove to the head. Deque in python exists so there is a data structure with constant time pop/push to the head. And it is in fact implemented as a doubly linked list, with various optimizations: https://github.com/python/cpython/blob/v3.8.1/Modules/_colle... .

It is not commonly done, but there is no reason why you can't have an array with amortised constant-time insertion at both the head and the tail.

I think it's more common than not to implement deques on top of arrays. There's a meaningful performance difference at the hardware level due to the spatial locality in memory. Linked lists in general cause the CPU to jump all over the place in memory, causing pressure on the cache and whatnot.

I believe the standard C++ deque implementation consists of a vector of vectors. The purpose of the two layers is at least two-fold. It guarantees that elements stored within the deque remain at a stable memory location at all times, even during a reallocation. Also, the memory getting shifted around during a reallocation consists of relatively tiny vector metadata rather than the application data.

To speculate, I suspect the reason it's a linked list in python is due to the age of the module. It was likely written relatively early on in python's development, and the linked list implementation was simple and elegant. Now enough stuff uses it that it would be painful to change.

Dicts are hashmaps in python rather than binary trees for similar performance reasons. You can't even find any binary tree based containers in python's standard library. You can find containers with the same performance characteristics and semantics of binary trees, but under the hood they're implemented on top of arrays because it better maps to hardware.

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

#353

Post by hashingroll »

hexomancer wrote: post #289
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 always wanted to really understand this data structure. Sure, I can follow the analysis with the potential functions and all, but I never really understood how Tarjan came up with the functions in the first place. Does anybody have a resource which intuitively explains the analysis?

This might a long read but it is well-written reader-friendly analysis of Tarjan's proof with chain of reasoning. https://codeforces.com/blog/entry/98275

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

#354

Post by xigoi »

mentater wrote: post #243
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…

Wouldn't that be extremely useful and a polynomial solution for 3-SAT, which is NP complete?

How is it a solution to 3-SAT?

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

#355

Post by OJFord »

NSMutableSet wrote: post #75
OJFord wrote: post #41

Earlier quoted context omitted.

The starting example was Bloom filters.

I'm not sure what the point of your post is. While bloom filters are heavily used in actual production code throughout the industry, it is very rare for anyone to need to code their own, or make changes to a prior legacy implementation. Not all educational programs will cover bloom filters, and for those that do, there's no guarantee that the students will retain the information, and be able to recall it. I don't kno…

I just didn't think it was necessary to be judgemental/'gate-keep' about what's obscure or interesting 'enough' - better to let anyone share what's interested them and why.

To your points, personally I do fall in a 'younger cohort' I imagine; have come across bloom filters on HN way more frequently, and I dimly recall tries from university but I knew them as prefix trees. Without submissions like this one I wouldn't learn what a trie is/to make that alias in my head.

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

#356

Post by xxs »

sgtnoodle wrote: post #342
xxs wrote: post #310

Earlier quoted context omitted.

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

A standard circular buffer is only single-producer single-consumer. The producer manipulates the head and the consumer manipulates the tail. Extending a circular buffer to allow multiple consumers is relatively straight forward; you just give each consumer its own tail and accept the loss of back pressure. Extending it to allow multiple producers without introducing locks is where the complexity shoots up drastically…

>Extending it to allow multiple producers without introducing locks is where the complexity shoots up drastically.

You can have a single tail with an atomic add, and that's pretty much it. The consumer needs to know, if the data is available, so there has to be a serialization point that with each producer has to wait - effectively a locking mechanism... or the consumer has to check all the producers progress.

It doesn't feel harder. The disruptor part/fame mostly came as it didn't have to allocate new memory.

For example writing a lock-free, max capacity limited, FIFO requires a single long (64bit) in each node and then reading head (1st), then tail one by the producers. Same idea - 64bits are too many to cause an integer overflow when increasing one-by-one.

It has been awhile since the time I wrote lock free stuff (occasional CAS and COW do not count). My current job doesn't really need it.

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

#357

Post by zeugmasyllepsis »

A GADDAG[1] is a combination pre-/suffix trie that's used for move generation in Scrabble. Unlike a traditional dictionary to find anagrams for words, a GADDAG makes it easier to identify plays based off of available letters already on the board. I made a little visualization of how they work for a data visualization class a few years back.[2]

[1] https://en.wikipedia.org/wiki/GADDAG [2] https://www.axioms.me/gaddag/#?page-5

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

#358

Post by benou »

scottcodie wrote: post #48

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

I was going to mention it too! The really cool thing about reservoir sampling is that it can be done "online" (ie process input incrementally) which makes it super useful when you want to compute statistical properties of something in the field without blowing up your cpu and memory.

For example, let's say I have a server serving queries. I want to measure min/max/avg/stdev/99p you name it. You can do it cheaply with reservoir sampling, without having to save all data points.

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

#359

Post by robalni »

filoeleven wrote: post #198

HAMT: Hash Array Mapped Trie. This data structure makes efficient immutable data possible. You can update a list of a million items, and keep a reference to the original list, by changing 3 or 4 references and some bytes. This should replace copy-on-write for scripting languages. I really want to see it in a JS spec soon. There are libraries that can do it, but they add translation penalties and extra steps. I’d comp…

What I like about HAMTs is that they can be super simple to implement if you make them one bit per level. They are like a combination of a binary search tree and hash table but without any of their annoyances.

* In binary search trees, you need to balance the tree every time you insert something because the tree will be linear if you insert the nodes in order. In a HAMT the positions are determined by the hash, so the positions will be random-like and not depend on the order you insert the nodes in.

* In binary search trees, you need to perform some complicated steps to remove a node. In a HAMT, you can either just mark the node as deleted, or if you want to fill the gap, find a leaf node that has the removed node on its path and just put it there.

* In hash tables, when it starts to get full you need to rehash it or put the added item in the "wrong" slot or something. A HAMT never gets full because it's a tree so you just add another child node.

Here I have written an explanation of a simple HAMT: https://www.robalni.org/posts/20220507-a-hash-table-you-dont...

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

#360

Post by mungoman2 »

Not really a pure data structure, but I like hash tables where the entries expire after some time. This is very useful in interactive situations like in games or chat bots, where for example you want the AI/bot to remember a conversation or piece of information for some time.

Simplest to implement is to just wrap a hash table and insert time checks in the accessors.

Post reply on HN