Linked list but where each entry in the list is fixed size array. O(1) inserts into the array. If the array fills you split it into two in the linked list. Amortizes the cost of traversing list pointers.
Ask HN: What are some cool but obscure data structures you know about?
551–560 of 772 posts
Re: Ask HN: What are some cool but obscure data structures you know about?
#552Struct of arrays (also called MultiArrayList in Zig), instead of storing big structs in an array you store each field in a separate array and if you need to fetch the full struct you reconstruct it from the arrays. The benefit is that the arrays items memory size is smaller and has no padding, it also increases cache locality.
Wouldn’t that hurt locality? Since now you need to do multiple access across the entire heap to reconstruct one object.
You wouldn't typically use this when you need lots of random accesses, but when you process the data sequentially.
It also simplifies and speeds up SIMD loads and stores, because you can load/store entire SIMD registers with a continuous, non-strided memory access.
Re: Ask HN: What are some cool but obscure data structures you know about?
#553The Bag. Also known as a Multiset. I can't believe it took me so many years to learn the name of the most basic data structure imaginable - it basically makes no promises whatsoever about the structure. Think of it like a Set that allows duplicates - you can put stuff in and take stuff out, just like a bag - what more could you want?
How is that any different from a list?
Two lists are equal only if they have the same contents and in the same order. Bags don’t have an order, they’re more like sets, so bags are equal so long as they have the same contents.
Re: Ask HN: What are some cool but obscure data structures you know about?
#554Earlier quoted context omitted.
You can put the promise into the cache immediately but you can only put the result from the promise into the cache once the promise resolves. So if an identical request comes in a second time before the promise has been resolved, then if you are caching the promise you have a cache hit but if you are caching the result then you have a cache miss and you end up doing the work twice.
I am still not understanding the purpose of this as I believe it is grounded on the wrong assumption. Pretty much every single asynchronous operation other than some `Promise.resolve(foo)` where foo is a static value can fail. Reading from the file system, calling an api, connecting to some database, etc. If the original promise fails you're gonna return a cached failure. Mind you, I'm not stating this might be compl…
Yep, I've been bitten by exactly this failure mode.
You have to invalidate/bust the cache when a failure is returned (which is racy, but since cache busting is on the sad path it's a fine place to protect with a plain ol' mutex, assuming you even have real parallelism/preemption in the mix).
Alternatively you can cache promises to functions that will never return failure and will instead internally retry until they succeed. This approach generalizes less well to arbitrary promises, but is more friendly to implementing the custom back off/retry scheme of your choice.
Re: Ask HN: What are some cool but obscure data structures you know about?
#555The BIP buffer.
It's a ring buffer compatible with APIs that don't specifically support it.
It's a great fit for any network I/O and I believe Android uses it under the hood.
https://www.codeproject.com/Articles/3479/The-Bip-Buffer-The...
Re: Ask HN: What are some cool but obscure data structures you know about?
#556HyperLogLogs! They're extremely useful for cardinality count estimation, and support set operations.
Re: Ask HN: What are some cool but obscure data structures you know about?
#557Equality graphs (e-graphs) for theorem proving and equality saturation and other equality-related things. They're awesome data structures that efficiently maintain a congruence relation over many expressions > At a high level, e-graphs extend union-find to compactly represent equivalence classes of expressions while maintaining a key invariant: the equivalence relation is closed under congruence. e.g. If I were to re…
I wonder if you could apply e-graphs to situations where the union-find data structure would be used, i.e. if there are any additional benefits gotten from the congruence relation.
Re: Ask HN: What are some cool but obscure data structures you know about?
#558Earlier quoted context omitted.
I am still not understanding the purpose of this as I believe it is grounded on the wrong assumption. Pretty much every single asynchronous operation other than some `Promise.resolve(foo)` where foo is a static value can fail. Reading from the file system, calling an api, connecting to some database, etc. If the original promise fails you're gonna return a cached failure. Mind you, I'm not stating this might be compl…
It's not the cost of saving the resolved data. If I understand the pattern correctly, it is to avoid multiple asynchronous requests to a resource that has yet to be cached.
Yeah, that's my understanding too.
It seems like an optimization to prevent lots of downstream requests that occur in rapid succession before the first request would have finished. I'd also suspect that the entry would be removed from the map on failure.
Re: Ask HN: What are some cool but obscure data structures you know about?
#559Treap: https://en.wikipedia.org/wiki/Treap It's like a Red-Black tree in use case, but much faster to implement, which is good for competitive programming. The average case complexity is the same for all operations, but there's an unlikely degeneration to worst-case linked-list behaviour. Lazy Propagation Segment Tree: https://cp-algorithms.com/data_structures/segment_tree.html Like a segment tree in that it supports…
Speaking of ease of implementation, I just discovered AA trees. They are probably not "obscure" but I think they are worthy of more fame because they perform jsut as well as red-black trees and are easier to implement. Finding clear comprehensive documentation about them was not easy though, so here is for you, the best I could find : https://www.cs.umd.edu/class/fall2019/cmsc420-0201/Lects/lec... And the, unhelpful…
The Wikipedia article on AA-Trees is good: https://en.wikipedia.org/wiki/AA_tree
Re: Ask HN: What are some cool but obscure data structures you know about?
#560Years ago as part of my thesis research I created a rather obscure family of data structures called DFI Filters or DFilters for short. The work centers around indexing typed trees such as abstract syntax trees or a web browser DOM such that you can answer arbitrary queries of the form "give me the set of all descendants of node P that are of type T" in something that in practice collapses to O(1) in the number of tree nodes. There are several versions of the data structure, but the general setup is a sort of "tree of trees" where the main tree is a binary search tree organized based on the depth-first indices of the nodes in the tree being indexed, and there are links into each type-specific variant of the main tree (in other words, simplified versions of the main tree containing only one type). The key intuition behind the whole thing, and the reason I called them DFI Filters, is the fact that if you are at some particular node in a tree, and you know ahead of time the depth first indices of your node and it's siblings, you actually already know exactly how many descendents your node has based on the difference in the DFI number between your node and its depth-first successor. Then you can build a variety of indexing approaches and data structures based on this insight -- I came up with ones that do it in truly constant time but are expensive to update as an undergrad, and in grad school I was able to build a version that updates on the fly but still retains ammortized O(1) for querying and ammortized O(m) for updating where m is the size of the update.
By the way if you're curious how I can get constant time when I'm returning a set of descendants, it's because I can give you the size and pointers to the first and last elements right off the bat.
The link to the original paper seems to be down (looking into it), but you can find the master's thesis covering all variants here: https://github.com/sam0x17/hierarch_old/blob/master/Master's...
I've been working on a rust implementation lately as well. There are a number of applications for DFilters including fast file-system searching, DOM traversal, very fast static analysis on abstract syntax trees, and more.