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

41–50 of 67 posts

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

#41

Post by yalok »

TheDudeMan wrote: post #39
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…

OK but what is your point?

That junior engineers tend to use hash map in situations where it’s way less efficient and is not necessary…

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

#42

Post by yalok »

wenc wrote: post #29
yalok wrote: post #28

Earlier quoted context omitted.

(from https://python-fiddle.com/saved/lN9D7DOQl0bQ8sqnDA94?code=tr... )

> come up with the most efficient data structure to store highly sparse data (say vector), that will need to be access only sequentially. There's something even more efficient -- a sparse array. I worked in the sparse linear algebra space, and you can gain a lot from sparsity. Add this to your fiddle: from scipy.sparse import csc_array sp_array = csc_array(my_list, dtype=np.int32) print(SZ, " values sparse array size…

To validate your point, I think you need to modify my test and create a 1M elements array with 99% of zeros - then your sparse class will be way more efficient, also hiding the complexity of creating a compact sparse representation at the native level.

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

#43

Post by rurban »

Here is the code https://github.com/splatlab/iceberghashtable

(from https://prashantpandey.github.io/publication/sigmod23_iceber...)

Need to compare it against my other concurrent hash tables, as they measured only 64bit int performance for keys and values, which is a bit unrealistic. And they only used murmurhash.

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

#44

Post by NooneAtAll3 »

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??

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

#45

Post by iamflimflam1 »

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…

The trap with asking these kind of questions is that you have spent a long time thinking of your optimum solution and the arguments for and against it.

You now have an expectation that it should be obvious and easy.

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

#47

Post by kolinko »

iamflimflam1 wrote: post #45
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…

The trap with asking these kind of questions is that you have spent a long time thinking of your optimum solution and the arguments for and against it. You now have an expectation that it should be obvious and easy.

This solution is/should be obvious and easy to anyone who knows algorithms and data structures.

I didn't invent op's question, but an answer that it should be a list is obvious right after reading the question. The question is very similar to the most basic exercises from the very first lessons of any basic algorithmics course.

If I was programming in python, I'd still probably use a hashmap because it's the quickest to implement. But once it shows to be a bottleneck in terms of speed or memory use, I'd switch to lists.

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

#48

Post by gniv »

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??

There is no PageDown on my MacBook keyboard.

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

#49

Post by eviks »

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??

Someone who realized that page down is far away, space is close, and paging down is frequent

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

#50

Post by 082349872349872 »

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…

The anti-curious commentary strikes me as being analogous to meth cooks complaining about https://en.wikipedia.org/wiki/High-pressure_chemistry research results not being applicable to their (1 bar) "real world" problems.

(Edit: it would appear that meth cooks are more appreciative of theoretical advances than programmers; recent european lab busts have revealed synthesis pathways using [similar to Haber-Bosch and Bergius] hundreds of atmospheres of pressure)

Post reply on HN