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

421–430 of 772 posts

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

#421

Post by skrebbel »

andrewingram wrote: post #377
ralusek wrote: post #312

Earlier quoted context omitted.

I have written many tools that do something like this, very useful. Just gotta be careful with memory leaks, so (for a TS example) you might want to do something like this: const promiseMap > = new Map(); async function keyedDebounce (key: string, fn: () => R) { const existingPromise = promiseMap.get(key); if (existingPromise) return existingPromise; const promise = new Promise(async (resolve) => { const result = awa…

Could you use a WeakMap for this instead?

If the key is a type that you expect to be GC'ed, yes, totally. If the key is a simple value type eg a string then it behaves the same as a regular Map or an object.

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

#422

Post by pdpi »

maest wrote: post #407
skrebbel wrote: post #297

Not a very deep CS-y one, but still one of my favourite data structures: Promise Maps. It only works in languages where promises/futures/tasks are a first-class citizen. Eg JavaScript. When caching the result of an expensive computation or a network call, don't actually cache the result, but cache the promise that awaits the result. Ie don't make a Map but a Map > This way, if a new, uncached key gets requested twice…

More generally, I believe this is a monad structure.

Promises are not monads, for one simple reason: they're not referentially transparent. The whole point of OP's example is to double down and take advantage of that.

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

#423

Post by pdpi »

itamarst wrote: post #80
jiggawatts wrote: post #25

Cache-Oblivious Data Structures: https://cs.au.dk/~gerth/MassiveData02/notes/demaine.pdf A vaguely related notion is that naive analysis of big-O complexity in typical CS texts ignores over the increasing latency/cost of data access as the data size grows. This can't be ignored, no matter how much we would like to hand-wave it away, because physics gets in the way. A way to think about it is that a CPU core is like a…

Does anyone actually use cache-oblivious data structure in practice? Not, like, "yes I know there's a cache I will write a datastructure for that", that's common, but specifically cache-oblivious data structures? People mention them a lot but I've never heard anyone say they actually used them.

Cache-obliviousness is an important part of the whole array-of-structs vs structs-of-arrays. One of the advantages of the struct-of-arrays strategy is that it is cache-oblivious.

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

#424

Post by hcs »

stevefan1999 wrote: post #390

https://en.wikipedia.org/wiki/Fibonacci_heap?wprov=sfla1 Fibonacci heap is theoretically better than Binary heap but the cache behavior is terrible https://en.wikipedia.org/wiki/Van_Emde_Boas_tree?wprov=sfla1 Well, I saw this in CLRS tho. Very clever way of abusing bit patterns for quick range query in O(log log M) where M is the integer size. https://en.wikipedia.org/wiki/Suffix_array?wprov=sfla1 A simpler way to do…

A suffix array is useful as a part of binary diff, finding a longest matching substring to copy from an old file. Bsdiff makes heavy use of this, it's used in Courgette for patching after preprocessing.

And once you have a suffix array, you're on the way to the Burrows-Wheeler Transform for e.g. bzip2 compression! https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf...

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

#425

Post by withinboredom »

stickupkid wrote: post #413
withinboredom wrote: post #349

Earlier quoted context omitted.

Won’t JS garbage collect orphaned references? Why is this necessary?

It does, but the map has a reference to it, so it will "leak" (in gc languages an unwanted reference is considered a leak). If this map got rather large, you could end up with a rather large heap and it would be un-obvious why at first.

Do Promises hold a reference to the chain of functions that end in the result? If so, that seems like a bug.

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

#426

Post by fulmicoton »

pure algorithm & perf stuff... - exponential unrolled linked list: I don't know what they are called, so I called them that way https://fulmicoton.com/posts/tantivy-stacker/. - radix heap. I actually had to use that data structure on a real use case. - radix tree. Actually super useful. - HashMap where the string and the value are contiguous in memory. Weirdly I've never seen that one... The hashmap can stores the full hash in its hash table anyway, so false positive are super rare. It will have to check the string anyway... You can improve your locality by keeping the key and the value in the same place in RAM.

just practical stuff, in python, I often use a magic dict defined as follows.

``` from collections import defaultdict >>> def MagicDict(): ... return defaultdict(MagicDict)

```

then you can use your MagicDict as a weird json-like map.

``` c = MagicDict() c[3]["aaa"][2] = 5 ```

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

#427

Post by unrealhoang »

moonchrome wrote: post #419
skrebbel wrote: post #297

Not a very deep CS-y one, but still one of my favourite data structures: Promise Maps. It only works in languages where promises/futures/tasks are a first-class citizen. Eg JavaScript. When caching the result of an expensive computation or a network call, don't actually cache the result, but cache the promise that awaits the result. Ie don't make a Map but a Map > This way, if a new, uncached key gets requested twice…

Just make sure Map access is thread safe - awaiting promises is - but updating/reading map keys usually isn't.

js is single-threaded so no problem there.

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

#428

Post by robalni »

robalni wrote: post #359
filoeleven wrote: post #198

HAMT: 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 comp…

What I like about HAMTs is that they can be super simple to implement if you make them one bit per level. They are like a combination of a binary search tree and hash table but without any of their annoyances. * In binary search trees, you need to balance the tree every time you insert something because the tree will be linear if you insert the nodes in order. In a HAMT the positions are determined by the hash, so th…

Here is an implementation of a binary HAMT that allows you to add and find nodes:

https://gist.github.com/robalni/311afd0756f25c4f234b2ae332cd...

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

#429

Post by moonchrome »

unrealhoang wrote: post #427
moonchrome wrote: post #419

Earlier quoted context omitted.

Just make sure Map access is thread safe - awaiting promises is - but updating/reading map keys usually isn't.

js is single-threaded so no problem there.

Since OP mentioned Mutexes I assumed he's dealing with multithreaded code, but with JS this works as advertised :)

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

#430

Post by almog »

EnderShadow8 wrote: post #392
gordaco wrote: post #124

Fenwick Trees (which, despite the name, are implemented using an array) allow counting prefix sums AND updating prefix sums in O(log n) time. Very useful when n is in the order of millions. I have used them a few times in Project Euler problems. https://en.wikipedia.org/wiki/Fenwick_tree

Segment trees are objectively superior in all ways except implementation length

Another advantage to Fenwick Tree: while it shares asymptotic space complexity with Segment Tree, it has better constant factors, which can be useful in very restricted environments.
Post reply on HN