Here's one I don't know if I've ever seen documented anywhere. If anyone knows a proper name for this one, let me know! Imagine it's for a text editor, and you want to map Line Numbers to Byte Positions. But then you want to insert a byte somewhere, and you need to add 1 to all your Byte Position values. Instead of actually keeping a big array of Byte Position values, you have a hierarchical array. The convention is…
Ask HN: What are some cool but obscure data structures you know about?
241–250 of 772 posts
Re: Ask HN: What are some cool but obscure data structures you know about?
#242>Good use-case: routing. Say you have a list of 1 million IPs that are black listed. A trivial algorithm would be to compare every element of the set with a given IP. The time complexity grows with the number of elements. Not so with a bloom filter! A bloom filter is one of the few data structures whose time complexity does not grow with the number of elements due to the 'keys' not needing to be stored ('search' and…
OP is probably mentioning bloom filter because it is space efficient. A good filter will use less space than entire hash set making it a good candidate to be kept in RAM to filter out requests and reduce expensive calls to read disk.
Re: Ask HN: What are some cool but obscure data structures you know about?
#243The 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?
Re: Ask HN: What are some cool but obscure data structures you know about?
#244Here's one I don't know if I've ever seen documented anywhere. If anyone knows a proper name for this one, let me know! Imagine it's for a text editor, and you want to map Line Numbers to Byte Positions. But then you want to insert a byte somewhere, and you need to add 1 to all your Byte Position values. Instead of actually keeping a big array of Byte Position values, you have a hierarchical array. The convention is…
https://en.wikipedia.org/wiki/Rope_(data_structure)
That's good for representing the text, but I'm more focused on the part about being able to add X to everything past a particular point very quickly by manipulating parent values.
Re: Ask HN: What are some cool but obscure data structures you know about?
#245Invertible Bloom Lookup Tables. They're like Bloom filters but you can also remove elements and even reconstruct elements in certain cases. Useful for syncing 2 databases which are almost in-sync, by sending only a small amount of data between them. It's used by Bitcoin nodes to communicate the contents of newly mined blocks.
Re: Ask HN: What are some cool but obscure data structures you know about?
#246The 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 heard stories about annotating the edges with elements from a group rather than using unlabelled edges. Have you heard anything about that?
Re: Ask HN: What are some cool but obscure data structures you know about?
#247Use arrayanes instead of matrix efficiently in boardgames like tetris or chess"A bitboard is a specialized bit array data structure commonly used in computer systems that play board games, where each bit corresponds to a game board space or piece. This allows parallel bitwise operations to set or query the game state, or determine moves or plays in the game"
Re: Ask HN: What are some cool but obscure data structures you know about?
#248Finger trees allow you to do amazing things. In essence they let you build an index, or multiple indices, for your dataset and then store them in a single structure. When I go from Haskell back to imperative land I find myself greatly missing this ability. Sure I can make multiple hashmaps or trees or whatever but being able to stuff it all in one data structure is amazing. One structure I built with them that is muc…
Finger Trees Explained Anew is a great derivation of the data structure: https://www.youtube.com/watch?v=ip92VMpf_-A
Re: Ask HN: What are some cool but obscure data structures you know about?
#249Roaring bitmaps are compressed bitmaps and they're pretty great. https://roaringbitmap.org/about/
Re: Ask HN: What are some cool but obscure data structures you know about?
#250Here's one I don't know if I've ever seen documented anywhere. If anyone knows a proper name for this one, let me know! Imagine it's for a text editor, and you want to map Line Numbers to Byte Positions. But then you want to insert a byte somewhere, and you need to add 1 to all your Byte Position values. Instead of actually keeping a big array of Byte Position values, you have a hierarchical array. The convention is…
An annotated tree?