Tim sort.
Ask HN: What are some cool but obscure data structures you know about?
191–200 of 772 posts
Re: Ask HN: What are some cool but obscure data structures you know about?
#192The 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…
Is there a name for the data structure/algorithm?
It's called union-find, but also disjoint-set sometimes. The process of reparenting nodes is called path compression, and the optimization of using the larger set of the two as the parent when merging is usually just called "union by rank." Any of those terms should give you more details upon search.
Re: Ask HN: What are some cool but obscure data structures you know about?
#193The 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…
If at some point you have a cycle, you can then reparent and remove the cycle, right? This structure in general then can encode transitive relations effectively? Something like “a and b …” “b and c …” “c and a …”.
> If at some point you have a cycle, you can then reparent and remove the cycle, right?
You'd never have a cycle. The way a cycle would theoretically arise would have to be joining something to its own child. But you don't naively join the two objects you're given - you find their root objects, and join those. If - as would be necessary for a cycle to form - they have the same root, you can return without doing anything.
If we call
unite(a,b)
unite(b,c)
unite(c,a)
c
/ \
b a
> This structure in general then can encode transitive relations effectively?
Well... no. This structure embodies the concept of an equivalence relation. You wouldn't be able to use it to express a general transitive relation, only a transitive relation that is also symmetric and reflexive.
Re: Ask HN: What are some cool but obscure data structures you know about?
#194DLX https://en.wikipedia.org/wiki/Dancing_links
Stanford Lecture: Don Knuth — "Dancing Links" (2018) https://www.youtube.com/watch?v=_cR9zDlvP88
Re: Ask HN: What are some cool but obscure data structures you know about?
#195Spatial hashing. Say that you have data that is identified with points in 2D or 3D space. The standard way that CS students learn in school to represent this is via a quadtree or octree. However, these tree data structures tend to have a lot of "fluff" (needless allocations and pointer chasing) and need a lot of work to be made efficient. Spatial hashing is the stupidly simple solution of just rounding coordinates to…
Yeah, just reinvented it a few weeks ago and was like “whoa, that’s it?” It worked perfectly for my fast clustering use case.
Re: Ask HN: What are some cool but obscure data structures you know about?
#196(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…
A fantastic thing about HyperLogLog is that it can be merged, so you can split your data between multiple server, precompute HLL for all IPs every minute, and then ask "how many unique IPs was there yesterday". Discovered HLL because it's used in ClickHouse, which employ a ton of cool but obscure data structure.
Works well in analytics cubes since they can be combined.
You can retain them across time too, such that you can ask questions like "how many unique users were there over the last N days?" without needing the source data. Great for privacy-aware analytics solutions.
Re: Ask HN: What are some cool but obscure data structures you know about?
#197"This is the story of a clever trick that's been around for at least 35 years, in which array values can be left uninitialized and then read during normal operations, yet the code behaves correctly no matter what garbage is sitting in the array. Like the best programming tricks, this one is the right tool for the job in certain situations. The sleaziness of uninitialized data access is offset by performance improveme…
I remember this from Programming Pearls and I was going to post about it after reading the comments. Great stuff.
Re: Ask HN: What are some cool but obscure data structures you know about?
#198HAMT: 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 complain less if I could use Clojurescript professionally, because it and Clojure are built around them.
Re: Ask HN: What are some cool but obscure data structures you know about?
#199The humble array but with a twist for accessing its indices in a hardware multiplexer way with 'shift left' and 'or' bitwise operations. /* Bits: selected, hovered */ const colors = [ grey, // 00 green, // 01 blueA, // 10 blueB // 11 ] const color = colors[selected https://blog.uidrafter.com/bitwise-table-lookup
No hardware multipliers here: left shifts are handled by much cheaper hardware [1], and are almost part of the basic arithmetic logic unit taught in school -- it can do addition, subtraction, bitwise operations, shifts by one, and maybe shifts by any number less than their word size.
Re: Ask HN: What are some cool but obscure data structures you know about?
#200Trivial, but very useful - phase accumulator / numerically controlled oscillator.
With two unsigned integers, freq and phase, you get amazingly fine control over timing. You only use the top N bits of phase for output. It's saved my bacon in embedded systems more than once.