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

611–620 of 772 posts

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

#611

Post by fanf2 »

bruce343434 wrote: post #348
jfim wrote: post #139

Earlier quoted context omitted.

There are also Judy arrays: https://en.wikipedia.org/wiki/Judy_array

This sounded promising but then I saw a performance benchmark [1] that was done on a pentium(!) with a very suboptimal hash table design compared to [2] and [3]. The Judy site itself [4] is full of phrases like "may be out of date", when the entire site was last updated in 2004. If it was already out of date in 2004... It seems that Judy arrays are just kind of a forgotten datastructure, and it doesn't look promising…

Judy arrays are (under the covers) a kind of radix tree, so they are comparable to things like ART (adaptive radix tree), HAMT (hashed array-mapped trie), or my qp-trie. Judy arrays had some weird issues with patents and lack of source availability in the early days. I think they are somewhat overcomplicated for what they do.

Regarding cache-friendiness, a neat thing I discovered when implementing my qp-trie is that it worked amazingly well with explicit prefetching. The received wisdom is that prefetching is worthless in linked data structures, but the structure of a qp-trie makes it possible to overlap a memory fetch and calculating the next child, with great speed benefits. Newer CPUs are clever enough to work this out for themselves so the explicit prefetch is less necessary than it was. https://dotat.at/prog/qp/blog-2015-10-11.html

I guess I partly got the idea for prefetching from some of the claims about how Judy arrays work, but I read about them way back in the 1990s at least 15 years before I came up with my qp-trie, and I don't know if Judy arrays actually use or benefit from prefetch.

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

#612

Post by CharanSriram »

This isn’t so much a data structure than an implementation of one, but map-represented trees are great.

For context, they were used by Figma to represent its scene-graph (https://www.figma.com/blog/how-figmas-multiplayer-technology...).

Essentially, it’s a way to represent a normal tree as a map; keys of the map represent individual nodes on the trees, and one key “ROOT” points to the rootmost node.

Each node is connected via the following relationship: parents have an unordered set of their children’s keys (not the actual node reference) and children know their parent’s key. Children also maintain a property to track their index using a technique called fractional indexing.

What’s great about this data structure is that you have O(1) transformations for most parts. If you need to change a node’s property, height for instance, (assuming this is a design tool or something), all you need is that nodes key. If you need to reposition a node under a new parent, simply remove the key from the parent’s set, change the node’s parent key, and update the index. This structure plays well with collaborative apps too as most edits to the tree are O(1)— edits are swift and can be communicated to other collaborative instances quite simply with small payloads.

Last thing I’ll touch on is fractional indexing. Very crudely put, it forces children nodes to track their position in a list via an “index” that can be a normal float. To reposition a child node, you first find its neighbors and average their indices to find a new index. Ordering the list is a sort from smallest indexes to largest.

In an example, say we had 3 nodes A, B, and C. A’s index is 0.1, B’s is 0.3, and C’s is 0.5. To insert an element D between A and B, I average A and B’s index (0.2), set that as the index of D and insert it into the parent node’s children set. At render, the set is ordered and we find A, D, B, C.

Shameless plug, but I’m using these techniques to build a multi-framework mobile app builder at phazia.com :). I love nerding out about these things so thanks for the chance to do so @op.

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

#614

Post by samsquire »

samsquire wrote: post #519
robalni wrote: post #486

Earlier quoted context omitted.

I was experimenting a while ago with something that I think is related to this. If you have a quadratic algorithm where you need to compare each pair of objects in a large array of objects, you might use a loop in a loop like this: for (int i = 0; i When this algorithm runs, it will access every cache line or memory page in the array for each item, because j goes through the whole array for each i. I thought that a b…

This is similar to what I'm working on. I am working on machine sympathetic systems. One of my ideas is concurrent loops. Nested loops are equivalent to the Nth product of the loop × loop × loop or the Cartesian product. for letter in letters: for number in numbers: for symbol in symbols: print(letter + number + symbol) If len(letters) == 3, len(numbers) == 3, len(symbols) == 3. If you think of this as loop indexes "…

Link to my concurrent loop repository.

https://github.com/samsquire/multiversion-concurrency-contro...

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

#615

Post by rramadass »

silverlake wrote: post #73

Most of the data structures posted here are taught in CS classes. Here’s an interesting list of more obscure ones: https://web.stanford.edu/class/cs166/handouts/090%20Suggeste...

This is great!

Exactly what this thread is about; everybody should go through this.

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

#616

Post by JackFr »

qwrshr wrote: post #595
JackFr wrote: post #543

Earlier quoted context omitted.

I saw an amazing presentation on Purely Functional Data structures with a really approachable and understandable proof on ho w a particular structure was asymptotically constant or linear time (I believe), and then followed up by saying that in practice none of it worked as well as a mutable version because of caching and data locality. Oh well.

Is there by any chance a publicly available recording of this presentation on purely functional data structures?

NE Scala Symposium Feb 2011

http://vimeo.com/20262239 Extreme Cleverness: Functional Data Structures in Scala

or maybe

http://vimeo.com/20293743 The Guerrilla Guide to Pure Functional Programming

(At work, so I can't check the video)

Both of them were excellent speakers

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

#617

Post by anewpersonality »

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 remember getting this in an interview without ever coming across it.. basically, fuck union find.

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

#618

Post by xxs »

sgtnoodle wrote: post #604
xxs wrote: post #356

Earlier quoted context omitted.

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

> You can have a single tail with an atomic add, and that's pretty much it. That's the primary difference. In a disruptor queue, there's two tails. The first one is used for producers to allocate space in the buffer to write to, and the second one is used to commit it so that it's available to consumers. It's true that there is a small amount of necessary synchronization across producers, because a producer can't com…

> there's two tail

My point about the sync part w/ the producers, the consumers won't be ready to read from the producers before it's ready. However another option would NOT using a contention point of a shared tail but marking each record as done - need write/write memory fence, so even if the consumers start reading, then can bail out if the write process has not committed.

> the buffer freely before that point, though, so in practice it's not a contention point.

Likely a false sharing between the producers, unless the impl. is careful enough to allocate cache-line sized records.

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

#619

Post by wingspan »

skrebbel wrote: post #480
wingspan wrote: post #443

Earlier quoted context omitted.

I love this approach and have used it many times in JavaScript. I often end up adding an additional map in front with the resolved values to check first, because awaiting or then'ing a Promise always means you will wait until the next microtask for the value, instead of getting it immediately. With a framework like React, this means you'll have a flash of missing content even when it is already cached.

This surprises me. I had expected the microtask to be executed right after the current one, ie before any layouting etc - isnt that the whole point the "micro" aspect?

I was able to reproduce this in a simple example [1]. If you refresh it a few times you will be able to see it flash (at least I did in Chrome on Mac). It is probably more noticeable if you set it up as an SPA with a page transition, but I wanted to keep the example simple.

[1] https://codesandbox.io/s/recursing-glitter-h4c83u?file=/src/...

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

#620

Post by okennedy »

xxs wrote: post #316
okennedy wrote: post #13

Linked Hash/Tree Maps, simple, but elegant. A Map with its nodes connected in a linked list so you can traverse them in insertion order (and O(n) time). Very useful for window queries over sequential data and other cases where you want FIFO access, but also quick access by a field of the data.

Why would Linked Hash Map be a obscure one? It's been a part of java collection framework for over 20y. It's a standard for LRU caches as well.

Hence the "simple but good". It's not really obscure, but also not on the common path. I've lost track of the number of times I've pointed this one out to a colleague or student.
Post reply on HN