Ask HN: What is your favorite data structure, what have you done with it?
Would like to check out and learn from practical and interesting implementations of data structures
6 comments
Aguri tries, which are bounded-sized radix trees with an LRU aggregation rule of joining sibling nodes.
The motivating use case is tracking metrics for IP addresses. You insert individual IP addresses into the tree, and when the tree fills, it starts rolling nodes for /32s into /31s, /30s, &c. Eventually, you get a picture of ranges of IP addresses in the data. That's neat, because, of course, IP packets themselves don't tell you anything about what subnets their IP addresses belong to.
The goofy thing I've done with them is apply them to memory addresses, so that I can collect individual pointers and bubble them up into allocation ranges, without instrumenting allocators.
The motivating use case is tracking metrics for IP addresses. You insert individual IP addresses into the tree, and when the tree fills, it starts rolling nodes for /32s into /31s, /30s, &c. Eventually, you get a picture of ranges of IP addresses in the data. That's neat, because, of course, IP packets themselves don't tell you anything about what subnets their IP addresses belong to.
The goofy thing I've done with them is apply them to memory addresses, so that I can collect individual pointers and bubble them up into allocation ranges, without instrumenting allocators.
Sounds cool. Thanks for writing. I found some links to followup:
What is an Aguri tree? http://goo.gl/mBWdbJ (this question on SO mentions your comment from previous HN threads on data structures)
Aguri: Coolest Data Structure You've Never Heard Of https://news.ycombinator.com/item?id=101969
Aguri: An Aggregation-based Traffic Profiler http://goo.gl/zA4Vl8
//links shortened for length
What is an Aguri tree? http://goo.gl/mBWdbJ (this question on SO mentions your comment from previous HN threads on data structures)
Aguri: Coolest Data Structure You've Never Heard Of https://news.ycombinator.com/item?id=101969
Aguri: An Aggregation-based Traffic Profiler http://goo.gl/zA4Vl8
//links shortened for length
I like when a simple data structure works in harmony with a simple algorithm to get really good performance. Like the algorithm would be completely mediocre if you replaced the data structure with something naive, but the data structure "unlocks" it and makes it fast:
- union-find data structure in Kruskal's minimum-spanning-tree algorithm, or for labeling connected components in binary images
- min-heap in Dijkstra's single-source-shortest-paths algorithm
- trie in the Apriori frequent-itemset data mining algorithm
Spatial partition data structures like octrees and kd-trees are really cool. Useful for anything that simulates physical space like games, graphics, CAD systems. Never implemented one myself though.
Least favorite is the red-black tree. It has nice theoretical properties but is so ugly and complicated. Most times I've thought about using one, I ended up choosing a hash table, trie, or sorted array instead. If I ever really need all its properties, I'll go all the way and use a b-tree for its cache friendliness.
- union-find data structure in Kruskal's minimum-spanning-tree algorithm, or for labeling connected components in binary images
- min-heap in Dijkstra's single-source-shortest-paths algorithm
- trie in the Apriori frequent-itemset data mining algorithm
Spatial partition data structures like octrees and kd-trees are really cool. Useful for anything that simulates physical space like games, graphics, CAD systems. Never implemented one myself though.
Least favorite is the red-black tree. It has nice theoretical properties but is so ugly and complicated. Most times I've thought about using one, I ended up choosing a hash table, trie, or sorted array instead. If I ever really need all its properties, I'll go all the way and use a b-tree for its cache friendliness.
A simple data structure (tree), but the process of laying it out for visualization (the Reingold-Tilmann algorithm) is more complex than you'd think.
But otherwise, I am the datastructure equivalent of a Blubber programmer :(.
But otherwise, I am the datastructure equivalent of a Blubber programmer :(.