Live data from Hacker News

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

news.ycombinator.com

511–520 of 772 posts

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

#511

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…

This is clever, otherwise you have to coordinate your cache setter and your async function call between potentially many concurrent calls. There are ways to do this coordination though, one implementation I've borrowed in practice in python is modes stampede decorator: https://github.com/ask/mode/blob/master/mode/utils/futures.p...

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

#512

Succinct data structures are one of my favourites. The idea that we can very cleverly pack a collection of information into a much smaller form, but you can query the compressed form with good computational complexity, and without unpacking the data you need to read is amazing .

See Steve Hanov's classic article on the topic: http://stevehanov.ca/blog/index.php?id=120

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

#513

Earlier quoted context omitted.

Can someone explain to me why the second example is better. To me it seems to be the same thing. Replace result with int and I literally do not see a problem with the first one. Also why is a mutex or lock needed for Result in javascript? As far as I know... In a single threaded application, mutexes and locks are only needed for memory operations on two or more results. With a single value, say an int, within javascr…

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 completely useless, but at the end of the day you will be forced to add code logic to check all of those asynchronous computation results which will eventually outweight the cost of only saving the resolved data.

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

#515

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.

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

#516
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.

Looked to see what these things were. Realised it might be the reason I made a career in IT: I used this structure (I called it a box) to calculate residues (https://en.wikipedia.org/wiki/Residue_(complex_analysis)), which I figured would be simpler using an object-oriented hence I learned myself C++. This was during my PhD (theoretical physics).

Off course, never used C++ again (learned object oriented language ‘properly’ using SmallTalk, which I also never used again in real life). Now, 25 years later, seeing the first time that I was using an (adaption of) PR Quadtrees.

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

#517

https://en.wikipedia.org/wiki/Macaroons_(computer_science) are very interesting to me. Think of it as a JWT that you can narrow down the authorizations for without needing to communicate with a server, so if you have read permissions to all your photos you can add a caveat saying `photoid=123456` and share it, and the recipient can only read the photo 123456. The caveats can be anything, including requiring third par…

I’ve heard of these! The fly.io blog has a really cool write-up about them. Definitely an under appreciated concept. IIUC, you can even validate the “sub issued” macaroons offline, provided you know the validity of one of its ancestors up the chain. Is this correct, or am I misunderstanding?

I think that's correct since each added caveat builds on the previous one.

I don't have the formal knowledge to understand the full underpinnings of it, but it always seemed to me (from implementing validation of them and looking at many authZ systems) that many of the sharing and delegation features of current apps would be so much neater in a macaroon based system.

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

#519

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…

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…

This is similar to what I'm working on.

I am working on machine sympathetic systems. One of my ideas is concurrent loops.

Nested loops are equivalent to the Nth product of the loop × loop × loop or the Cartesian product.

  for letter in letters:
   for number in numbers:
    for symbol in symbols:
     print(letter + number + symbol)
If len(letters) == 3, len(numbers) == 3, len(symbols) == 3. If you think of this as loop indexes "i", "j" and "k" and they begin at 000 and go up in kind of base 3 001, 001, 002, 010, 011, 012, 020, 100 and so on.

The formula for "i", "j" and "k" is

  N = self.N
  for index, item in enumerate(self.sets):
    N, r = divmod(N, len(item))
    combo.append(r)
So the self.N is the product number of the nested loops, you can increment this by 1 each time to get each product of the nested loops.

We can load balance the loops and schedule the N to not starve the outer loops. We can independently prioritize each inner loop. If you represent your GUI or backend as extremely nested loops, you can write easy to understand code with one abstraction, by acting as if loops were independent processes.

So rather than that sequence, we can generate 000, 111, 222, 010, 230, 013 and so on.

Load balanced loops means you can progress on multiple items simultaneously, concurrently. I combined concurrent loops with parallel loops with multithreading. I plan it to be a pattern to create incredibly reactive frontends and backends with low latency to processing. Many frontends lag when encrypting, compressing or resizing images, it doesn't need to be that slow. IntelliJ doesn't need to be slow with concurrent loops and multithreading.

See https://github.com/samsquire/multiversion-concurrency-contro...

Loops are rarely first class citizens in most languages I have used and I plan to change that.

I think I can combine your inspiration of gray codes with this idea.

I think memory layout and data structure and algorithm can be 3 separate decisions. I am yet to see any developers talk of this. Most of the time the CPU is idling waiting for memory, disk or network. We can arrange and iterate data to be efficient.

Post reply on HN