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

521–530 of 772 posts

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

#521

Post by alexchro93 »

jtwigg wrote: post #332
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…

FYI, if you plan to do this in ASP netcore, combine with AsyncLazy for the most optimal results https://github.com/davidfowl/AspNetCoreDiagnosticScenarios/b...

Neat page from David Fowler. I didn't know about that one. Thank you.

To further explain why you want to use an AsyncLazy (or Lazy for synchronous programming) when working with ConcurrentDictionary I find this article to be helpful: https://andrewlock.net/making-getoradd-on-concurrentdictiona...

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

#522

Post by mkl »

synalx wrote: post #463

PR Quadtrees ( https://opendsa-server.cs.vt.edu/OpenDSA/Books/CS3/html/PRqu... ) got me my current job at Google. One of my interviewers asked basically "how would you design Google Maps?" and I based my answer on this data structure.

Why subdivide so far? I find it better to have leaf nodes contain an array of up to some small number of points, e.g. 20. That reduces the pointer chasing significantly, and a linear search through such a small array is very fast.

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

#523

Post by FridgeSeal »

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!

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

#524

Post by api »

I love the set reconciliation structures like the IBLT (Iterative Bloom Lookup Table) and BCH set digests like minisketch.

https://github.com/sipa/minisketch

Lets say you have a set of a billion items. Someone else has mostly the same set but they differ by 10 items. These let you exchange messages that would fit in one UDP packet to reconcile the sets.

Minisketch is more costly in CPU but has deterministic guarantees. IBLTs are very fast but have a chance of failure requiring a randomized iterative procedure.

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

#525

Post by cerved »

epolanski wrote: post #513
JimDabell wrote: post #475

Earlier 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…

You do one IO operation instead of two.

It's unlikely that always doing two is going to be more successful than just trying once and dealing with failure

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

#526

Post by DoubleFree »

celeritascelery wrote: post #515
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.

Wouldn’t that hurt locality? Since now you need to do multiple access across the entire heap to reconstruct one object.

It depends. For operations or aggregates on a single field, it improves cache locality, whereas if operations act on all, or most, fields of the struct, it hurts cache locality. The exact same tradeoff differentiates OLTP (transactional/row stored) databases and OLAP (analytics/column stored) databases.

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

#527

Post by JKCalhoun »

A certain ePub reader on MacOS used to use a bloom filter for text search. You would decompose an ePub into pages of text and generate a bit array for the text on each page. As the user types in the search field you could often reject large portions of the document — leaving perhaps only a handful of pages where the code would only then have to drop down to the more tedious string matching algorithm.

Very cool.

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

#528

Post by jacamera »

sgtnoodle wrote: post #326
jacamera wrote: post #16

Earlier quoted context omitted.

I recently learned about monotonic stacks thanks to this LeetCode problem: https://leetcode.com/problems/sum-of-total-strength-of-wizar... I feel like they're quite possibly the most deceptively simple data structure I've yet to encounter. That is to say that for me at least there was/is a wide gulf between simply understanding what the data structure is (doesn't get much simpler than a stack!) and when/how to actual…

Do folk genuinely get asked problems like that in technical interviews these days? I can't think of any plausible reason why anyone would want to do a calculation as contrived as that. I love the required modulo value too. I assume the trick is to somehow leverage the distributive property of multiplication to refactor the data to no longer require as much iteration? Is there supposed to be a linear time solution?

> Do folk genuinely get asked problems like that in technical interviews these days?

No idea! I'm still in interview prep mode though so I'm doing the LeetCode contests every weekend. Even if practicing problems like these is over-preparing I think it's probably a good idea for me because I imagine I'll be much more nervous and less performant during an actual live interview.

> Is there supposed to be a linear time solution?

Yes! Using a monotonic stack to find the "pivot points" of the contiguous subarray groups as well as both a prefix-sum array and prefix-product array to calculate the sum of all subarrays in each group in O(1) time after initially building the arrays in linear time.

There are some great explanations in the discussion section. This is one of the few problems that I got stuck on and wasn't able to solve on my own after a couple days of trying. The LeetCode community is awesome though and getting to see how other people solved the problem is a great educational resource.

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

#529

Post by asadawadia »

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…

Yeah, saves you from thundering herd problems

https://github.com/ben-manes/caffeine cache does something similar by caching the future that gets returned on look-ups if the value is still being computed

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

#530

Post by epolanski »

pdpi wrote: post #422
maest wrote: post #407

Earlier quoted context omitted.

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.

Referential transparency is a property of expressions, not type classes. Referential transparency is nowhere in the definition of a monad because a monad is obviously not an expression but a type class.

It is definitely true that Promise is a data type that _could_ admit a monad instance. It has:

- a data type M a which is Promise a

- a function pure with the signature a => M a, which is x => Promise.resolve(x)

- a bind function with the signature M a => a => M b => M b which is essentialy `then`

But a monad requires three properties to hold true: Right identity, Left identity and associativity. Right identity holds for every function `f: a => M b`, but left identity and associativity do not hold.

Post reply on HN