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

731–740 of 772 posts

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

#731

Post by nemo1618 »

zachrip wrote: post #686
nemo1618 wrote: post #229

My contribution: the Binary Numeral Tree: https://eprint.iacr.org/2021/038 This is a tree-like structure where the structure of the tree is fully determined by the number of leaves N. Specifically, each 1-bit in the binary representation of N corresponds to one of the tree's perfect binary subtrees. For that reason, I think of it more as "structure imposed upon a list" rather than a typical mutable tree with pointers…

Can you dumb this down for me?

It might be easier to think about it as a stack, rather than a tree. Each element of the stack represents a subtree -- a perfect binary tree. If you ever have two subtrees of height k, you merge them together into one subtree of height k+1. Your stack might already have another subtree of height k+1; if so, you repeat the process, until there's at most one subtree of each height.

This process is isomorphic to binary addition. Worked example: let's start with a single leaf, i.e. a subtree of height 0. Then we "add" another leaf; since we now have a pair of two equally-sized leaves, we merge them into one subtree of height 1. Then we add a third leaf; now this one doesn't have a sibling to merge with, so we just keep it. Now our "stack" contains two subtrees: one of height 1, and one of height 0.

Now the isomorphism: we start with the binary integer 1, i.e. a single bit at index 0. We add another 1 to it, and the 1s "merge" into a single 1 bit at index 1. Then we add another 1, resulting in two 1 bits at different indices: 11. If we add one more bit, we'll get 100; likewise, if we add another leaf to our BNT, we'll get a single subtree of height 2. Thus, the binary representation of the number of leaves "encodes" the structure of the BNT.

This isomorphism allows you to do some neat tricks, like calculating the size of a Merkle proof in 3 asm instructions. There's some code here if that helps: https://github.com/lukechampine/us/blob/master/merkle/stack....

You could also check out section 5.1 of the BLAKE3 paper: https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blak...

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

#732

Post by 9935c101ab17a66 »

marcosdumay wrote: post #648
hn_throwaway_99 wrote: post #622

Earlier quoted context omitted.

not really quite lazy evaluation, thought, at least in Javascript. Promises begin execution as soon as they are created and there is no way to delay that.

Promises are an implementation of lazy evaluation for Javascript. This is exactly lazy evaluation. By the way, lazy evaluation is the one that offers no guarantees about when your code will be executed. If you can delay the execution, it's not lazy.

Promises in javascript are absolutely not considered 'an implementation of lazy evaluation.' Promises are invoked eagerly in javascript.

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

#733

Post by Nilithus »

dwaite wrote: post #222

Splay trees: These are binary search trees, but when you 'splay' the tree (such as by search) it rebalances the tree so that the search result is on top. This means while it is O(log n) for operations like other self-balancing trees, it optimizes tree depth in the face of non-random access so that recently accessed items are fewer steps into the tree. Piece tables: A bit more common for text editors, where you need t…

The VSCode Blog has a great article on Piece Tables talking about their adoption of that data structure https://code.visualstudio.com/blogs/2018/03/23/text-buffer-r...

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

#734

Post by pmontra »

whycombagator wrote: post #568

I really like this thread, but now I am concerned which of these will show up in a future interview. Edit: forgot to add mine. Not obscure by any means but Fenwick Trees are very cool IMO https://en.m.wikipedia.org/wiki/Fenwick_tree

"I remember a thread on HN about uncommon data structures. Do you also follow that site?"

It could be a good answer to start bonding with the interviewer. Then nobody knows everything. Go for a reference and show that you can understand it.

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

#735

Post by Shorel »

Sesse__ wrote: post #406
sicp-enjoyer wrote: post #137

Earlier quoted context omitted.

C++ STL uses trees because the generic requirement for them to work is a Ironically, due to caches, sorting and then using algorithms that rely on order tend to be superior than most hashing implementations, even though they are theoretically worse due to log(n) factor. So in a way, C++ algorithms are actually more modern.

> Ironically, due to caches, sorting and then using algorithms that rely on order tend to be superior than most hashing implementations This doesn't match my experience at all. C++ trees are not cache-friendly; they're pointer-chasing (and there's no arena implementation in the STL). Second, any sort of ordering structure (be it through a tree or through sorting + binary search) is notoriously prone to branch mispred…

With a modern Intel processor, it was much faster to go through a 10k integers array than sort it first and then do binary search.

The small N is not that small anymore, and the difference speed between stack and heap is bigger now than ever.

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

#736

Post by hexomancer »

sn9 wrote: post #693
hexomancer wrote: post #672

Earlier quoted context omitted.

Is it in an old edition? I just downloaded an extremely legitimate version of Algorithms 4th edition but it has no section on union data structure.

It should be in Chapter 1 Section 5 of the 4th edition. It's even in the table of contents.

Sorry, my bad. I searched for the word "disjoint" expecting it to be prominent in this section but somehow this word only appears 3 times in this book non of which are in this section!

Anyway, while the figures in this work were indeed gorgeous, it was not what I was looking for. It did not even contain a non-intuitive analysis of the inverse ackermann complexity, much less an intuitive one!

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

#737

Post by ElCapitanMarkla »

FridgeSeal wrote: post #523
zbobet2012 wrote: post #274

Here is one not on the list so far: Set Sketches. They allow you compute the difference between two sets (for example to see if data has been replicated between two nodes) WITHOUT transmitting all the keys in one set to another. Say you have two sets of the numbers [1, ..., 1million] all 32 bit integers, and you know one set is missing 2 random numbers. Set sketches allow you to send a "set checksum" that is only 64…

Thank you! I always wondered about this problem and never knew what to look up to read more about it!

I’ve found that a couple of times in this thread. A way to describe a problem and have potentially applicable algorithms suggested would be cool

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

#738

Post by robalni »

phkahler wrote: post #676
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…

While reading your post I kept thinking "de-interleave the bits of a single counter" since I have used that before to great benefit. It does suffer from issues if your sizes are not powers of two, so your grey code modification seems interesting to me. I'll be looking in to that. FYI this also extends to higher dimensions. I once used it to split a single loop variable into 3 for a "normal" matrix multiplication to g…

Interestingly I get more cache misses with the gray code solution but still fewer switches between cache lines. This has to be because the cache line prefetcher can predict the memory usage in the simple version but it's harder to predict in the gray code or de-interleave version.

Also, I have never thought about de-interleaving bits without using gray code but that seems to work similarly. The main reason I used gray code is that then we don't have to switch memory blocks as often since only one of the indexes changes every time so one of the current memory blocks can always stay the same as in the previous iteration.

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

#739

Post by dan-robertson »

cmpolis wrote: post #593
remorses wrote: post #485

Struct 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.

this is a great way to store structured data in js since it saves the memory cost having repeated keys. e.g.: records = { time: [1000, 1001], price: [20, 25], volume: [50, 15] } records = [ { time: 1000, price: 20, volume: 50 }, { time: 1001, price: 25, volume: 15 } ] // not a big difference with 2 records, but for xxxx records...

In practice, most js engines these days can ‘recognise’ the ‘class’ of these objects (if you create them from scratch in a few places) and the memory representation would end up with a word for the ‘class’ which says that time is at field 0 and price at 1 and volume at 2, and then the data itself. The main reason is to speed up code that reads the fields rather than memory use.

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

#740

Post by dan-robertson »

wxnx wrote: post #684
dan-robertson wrote: post #652

Earlier quoted context omitted.

Be careful with this data structure. If the language allows async exceptions or you have a big where the promise won’t become deferred, there are a lot of edge cases. Examples of edge cases: - if the promise never becomes determined (eg bug, async exception) your app will wait forever - if the promise has high tail latency things can be bad - if the language eagerly binds on determined promises (ie it doesn’t schedul…

I wrote some Python code recently that uses a similar data structure (Futures instead of Promises, without knowing necessarily about the data structure's use in JavaScript). It wasn't really for caching. I modeled mine on the Django ASGI reference library's server implementation, which uses the data structure for maintaining references to stateful event consumers. Exception handling is done with a pre-scheduled long-…

Suppose the call to evaluate has a p95 of 5 seconds (this is very large of course). If your first call to compute a value hits it, all the subsequent requests for that cell are blocked for 5s. If you didn’t try to cache, only one might block for 5s and the rest could go through fast. On the other hand if you do 20 requests then about one of them will get the p95 latency.
Post reply on HN