Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Scientists find optimal space-time balance for hash tables

quantamagazine.org

Post reply on HN
Print view View original

51–60 of 67 posts

Re: Scientists find optimal space-time balance for hash tables

#51

Post by optimalsolver »

klyrs wrote: post #25

I'm a bit sad to see the anti-curious commentary here. This result is really cool, and finds the asymptotic sweet spot for hash table memory usage. Often times, the first algorithm to establish an asymptotic limit is entirely too complicated and doesn't help at human scale. If the world collectively ignores such results, as many here seem inclined to do, that's the end of the story. But when somebody continues bashin…

>Often times, the first algorithm to establish an asymptotic limit is entirely too complicated and doesn't help at human scale

https://en.wikipedia.org/wiki/Galactic_algorithm

Re: Scientists find optimal space-time balance for hash tables

#52

Post by eimrine »

klyrs wrote: post #25

I'm a bit sad to see the anti-curious commentary here. This result is really cool, and finds the asymptotic sweet spot for hash table memory usage. Often times, the first algorithm to establish an asymptotic limit is entirely too complicated and doesn't help at human scale. If the world collectively ignores such results, as many here seem inclined to do, that's the end of the story. But when somebody continues bashin…

I expected some cool graphics or livehacks but I see photos of researchers and it is not obvious what link I should follow to move from promotional content to more scientifical one.

Re: Scientists find optimal space-time balance for hash tables

#53

Post by im3w1l »

yalok wrote: post #27

Hash tables are nice & all, and it's very convenient to use them, BUT I really regret how they create propensity for junior developers to use them even in cases where they are not really needed and more memory-efficient (and perf too) data structure could be used. Anecdotally, in my recent year of interviewing new candidates, I keep asking this simple question: come up with the most efficient data structure to store…

Two lists one with keys and with values. The key list can be delta encoded and then compressed with the assumption that most of the deltas are small (even with adversarial keys this property must hold, as if there are too many big deltas then it would overflow the key type but we know all the keys are valid).

Re: Scientists find optimal space-time balance for hash tables

#55

Post by jmb99 »

gniv wrote: post #48
NooneAtAll3 wrote: post #44

Earlier quoted context omitted.

...spacebar? shouldn't "down a page" be done with PageDown? who came up with binding this behavior to a spacebar as well??

There is no PageDown on my MacBook keyboard.

Fn-down gives you page down. Also:

Fn-up: page up

Fn-right: end

Fn-left: home

Re: Scientists find optimal space-time balance for hash tables

#56

Post by coldtea »

eimrine wrote: post #52
klyrs wrote: post #25

I'm a bit sad to see the anti-curious commentary here. This result is really cool, and finds the asymptotic sweet spot for hash table memory usage. Often times, the first algorithm to establish an asymptotic limit is entirely too complicated and doesn't help at human scale. If the world collectively ignores such results, as many here seem inclined to do, that's the end of the story. But when somebody continues bashin…

I expected some cool graphics or livehacks but I see photos of researchers and it is not obvious what link I should follow to move from promotional content to more scientifical one.

How about searching for it in Google, instead of clicking a link?

Re: Scientists find optimal space-time balance for hash tables

#57

Post by Qwertious »

NooneAtAll3 wrote: post #44
madars wrote: post #5

Somewhat off-topic but does anyone have a bookmarklet that would remove annoying scrolling behavior on sites like Quanta? I.e. pressing space bar should immediately scroll down a page, not do it slowly with awkward mechanics. In exchange I'm happy to share a bookmarklet that "unsticks" sticky elements of the page (e.g. an ever-visible header like on WaPo, though they are not the worst offender): https://pastebin.com/…

...spacebar? shouldn't "down a page" be done with PageDown? who came up with binding this behavior to a spacebar as well??

>shouldn't "down a page" be done with PageDown?

PageDown doesn't reliably exist - plenty of laptops put it behind a function-key combo, making the only action you're doing on the page a two-handed affair.

> who came up with binding this behavior to a spacebar as well??

Apparently, it comes from the `more` command[1], because they couldn't reliably assume terminals would have a PageDown key, and because spacebar was the biggest key on the keyboard so it was the obvious choice for the one action in `more`.

[1] https://ux.stackexchange.com/questions/53110/why-does-the-sp...

Re: Scientists find optimal space-time balance for hash tables

#58

Post by j-pb »

dgacmu wrote: post #26
jiggawatts wrote: post #6

This kind of thing is unfortunately not useful at any scale. Real computer systems have performance that varies due to memory locality and size. Locality because of things such as cache hierarchy and even the size of cache lines and memory pages. Size because of physical implementation: larger memories are physically bigger and hence further away. The speed of light makes access to larger memories inescapably slower.…

This is a bit pessimistic. Most STOC papers don't directly give an incredibly practical algorithm. But what they do give is insight, and that insight can often be used to improve the practical state of the art. And new bounds get you thinking; there's power in just knowing we can do better. It's like breaking the 4 minute mile -- a lot follows. From a personal perspective: I quite like some of the techniques they use…

Cuckoo hashing is such a joy to work with, and feels like a gem produced from the pressure at the intersection of theory and practice.

They are much easier to implement yet feel more fundamental than other open accessing shemes.

I've used tiny cuckoo hash tables with a bounded size of 2,4,...,256 elements as a compression technique for an Adaptive Radix Trie that doesn't require heterogeneous nodes, and I think I've never had more fun in my career as a computer scientist/software engineer.

Re: Scientists find optimal space-time balance for hash tables

#59

Post by andersa »

vlovich123 wrote: post #16
andersa wrote: post #11

Earlier quoted context omitted.

Yep, it's the same thing every time. "We propose this new thing with optimal time complexity blah blah blah" - don't care. Show benchmark. What do you mean it's slower than this basic but cache efficient hash table implemented in 100 lines of c++?

This is a totally different result. It’s providing a proof of an algorithmic complexity. So let’s say you have 10^18 items, it’s likely you’d be using this even if certain algorithms are faster at smaller numbers. It’s also important to note the particularly interesting result is how the mathematicians proved that the earlier design was optimal (upper and lower bound). The technique is the valuable part as it adds to…

I'm struggling to think of any possible application that would need anywhere remotely close to 10^18 items. Do you have an example?

Re: Scientists find optimal space-time balance for hash tables

#60

Post by vlovich123 »

andersa wrote: post #59
vlovich123 wrote: post #16

Earlier quoted context omitted.

This is a totally different result. It’s providing a proof of an algorithmic complexity. So let’s say you have 10^18 items, it’s likely you’d be using this even if certain algorithms are faster at smaller numbers. It’s also important to note the particularly interesting result is how the mathematicians proved that the earlier design was optimal (upper and lower bound). The technique is the valuable part as it adds to…

I'm struggling to think of any possible application that would need anywhere remotely close to 10^18 items. Do you have an example?

I pulled that specific number out of the air and it was intentionally an over exaggeration. We don’t know the crossover point.
Post reply on HN