14,000x Speedup (2015) • Hacker News Board

Re: 14,000x Speedup (2015)

#171

Post by z3t4 » Tue, Oct 13, 2020, 4:58 PM UTC

hinkley wrote: post #144

mynegation wrote: post #39

Algorithms are important but are especially powerful in combination of knowing computer architecture and programming language intricacies. Many years ago I was asked to look at the program written in C++ that calculated Kendall-tau correlation matrix for a large amount of data. Basically Kendall Tau is a robust replacement for Pearson correlation and it had to be calculated for 0.5M^2 elements and calculation of each…

I was asked once in an interview what the hardest part of programming was, and I said it wasn't Order of Complexities, it was the C constant within it. Interviewer was not subtle in thinking that was stupid. My rationale was - and is - that C is not sexy. It's hard to motivate people to look into it, and it's often hard work because a sort algorithm or a lookup table tend to be compartmentalized, while C issues are d…

What is the C constant?

Re: 14,000x Speedup (2015)

#172

Post by dang » Tue, Oct 13, 2020, 4:58 PM UTC

All: some comments are finding fault with the article and the author in ways that aren't in the intended spirit of HN. When someone made a mistake or didn't find the best answer, it's great to explain why and supply correct information, but please avoid mixing in putdowns, and if your comment is just a putdown, please don't post.

Otherwise we end up with basically this: Person 1: "I am very smart." Person 2:" Rubbish. It is I who am very smart." That is not interesting, regardless of who is smarter. Worse, it all-too-easily turns a community like HN into an unfriendly place.

When in doubt, simply remember that the intended spirit is curious conversation, and then your comments will naturally contain interesting details and insights without the other stuff.

https://news.ycombinator.com/newsguidelines.html

Re: 14,000x Speedup (2015)

#173

Post by andi999 » Tue, Oct 13, 2020, 5:00 PM UTC

dang wrote: post #167

Ultimatt wrote: post #103

Earlier quoted context omitted.

You're not wrong. This entire article is a classic example of Computer Science failure. It's someone who knows program optimisation in the abstract and nothing about the actual target problem from a domain knowledge perspective. They went about optimising bad code as in quality of thought level, rather than actually getting to grips with the true requirement first. Though perhaps a computer science win, but a softwar…

Please don't post supercilious dismissals of other people or their work, even if they made a mistake and/or were supercilious in their own right. It just contributes to making this a nasty place. The differences between this comment and the GP comment are significant. The GP included specific information, where this comment is just a putdown, and the GP allowed for the possibility that there is missing information, i…

I usually agree, but in this case maybe the author needs to hear exactly that. At least the author might the want to stop boasting about these things (and save his future career etc).

Re: 14,000x Speedup (2015)

#174

Post by mynegation » Tue, Oct 13, 2020, 5:02 PM UTC

ath92 wrote: post #161

andruby wrote: post #120

Earlier quoted context omitted.

Sorry to correct your math here, but going from 6 hours (6*60=360 minutes) to 4 minutes is a 90x improvement, not 900x.

Interestingly, a speedup of 2 orders of magnitude seems to be about what you'd expect if you only apply the algorithmic optimization (going from N^2 to Nlog(N) with N being in the range of a few thousand, like OP said)

Like I mentioned - my memory is pretty hazy about the specific speedups.

Yes, N^2 to NlogN feels like it should be a bigger factor, but remember that constants in front of this matter. You are replacing 2-level nested but very straightforward loops that rip through cached memory at blazing speed without any disruption to CPU pipelines with a single loop that involves quite a bit of condition checking and array element swaps (cache is busted, pipelines are busted - conditions are very hard to predict). You gain some, you lose some.

Re: 14,000x Speedup (2015)

#175

Post by forgotpwd16 » Tue, Oct 13, 2020, 5:04 PM UTC

danielvf wrote: post #140

roter wrote: post #65

> In climate science we do a lot of downscaling. We take temperature and precipitation readings from a coarse scale Global Climate Model grid and map them to a fine scale local grid. Let’s say the global grid is 50x25 and the local grid is 1000x500. For each grid cell in the local grid, we want to know to which grid cell in the global grid it corresponds. Climate scientist here. Colour me a little confused. We have a…

I've upvoted this. Even the "optimized" solution here is so horrible that I almost thought the article was satire when I first read it. Maybe it is. Even if we ignore the fact that it's grid to grid conversion, (which should just let you math the answer, without any searching) the fact that all the data is sorted means you can do the equivalent of a merge sort and only have to look at a two point for each step. And h…

R in general and especially loops are slow; slower than even Python. Making a function and applying it on a vector is a simple way to boost performance. Also recursion seems[1] to be faster than iteration.

Seeing the code in article, it can be that a part in that speedup is because R is used and not only of a better algorithm.

[1]: https://predictivehacks.com/a-comparison-between-iteration-r...

Re: 14,000x Speedup (2015)

#176

Post by ultra_nick » Tue, Oct 13, 2020, 5:04 PM UTC

That sounds a lot like the "Find the point nearest to this one on a 2s plane" interview question. Neat.

Re: 14,000x Speedup (2015)

#177

Post by dang » Tue, Oct 13, 2020, 5:07 PM UTC

andi999 wrote: post #173

dang wrote: post #167

Earlier quoted context omitted.

Please don't post supercilious dismissals of other people or their work, even if they made a mistake and/or were supercilious in their own right. It just contributes to making this a nasty place. The differences between this comment and the GP comment are significant. The GP included specific information, where this comment is just a putdown, and the GP allowed for the possibility that there is missing information, i…

I usually agree, but in this case maybe the author needs to hear exactly that. At least the author might the want to stop boasting about these things (and save his future career etc).

I appreciate the sentiment, but that is probably better reserved for personal interactions than internet pile-ons. There are lots of factors we don't know. Also, if we're to be honest with ourselves, internet pile-ons don't arise out of compassionate concern for the other. That's a justification that gets tacked on.

It's moot anyhow, because the main reason not to have threads go that way is that it does bad things to the community. Each time it happens, we deepen the pathways towards making HN nastier and more toxic, and since those are the default paths already, we need to consciously cultivate the opposite.

Re: 14,000x Speedup (2015)

#178

Post by jdmichal » Tue, Oct 13, 2020, 5:11 PM UTC

rgossiaux wrote: post #160

jdmichal wrote: post #62

Earlier quoted context omitted.

My rule is that the only sort I will ever write by hand is a bubble sort. It's basically impossible to write incorrectly. If and when that breaks performance, then I will bring in an external sorting library and figure out what works the best for the data. It's the equivalent philosophy to always buying the cheapest tool you can the first time around. When you break that tool, then you go out and buy the expensive on…

The cheapest tool you can find is surely the sort in your programming language's standard library. Writing your own sort seems crazy to me.

What can I say. Sometimes you're not working with the blessed standard data structures for which those algorithms are typically written.

Re: 14,000x Speedup (2015)

#179

Post by monksy » Tue, Oct 13, 2020, 5:14 PM UTC

mumblemumble wrote: post #81

mynegation wrote: post #39

Algorithms are important but are especially powerful in combination of knowing computer architecture and programming language intricacies. Many years ago I was asked to look at the program written in C++ that calculated Kendall-tau correlation matrix for a large amount of data. Basically Kendall Tau is a robust replacement for Pearson correlation and it had to be calculated for 0.5M^2 elements and calculation of each…

makes me think of https://ericlippert.com/2020/03/27/new-grad-vs-senior-dev/

That was a great write up explaining about not seeing the forest for the trees. However, it is still infuriating that we're getting these leetcode questions in interviews to see how much you can hack and optimize a toy problem. (As if you had lots of time to think about it and work through it)

Re: 14,000x Speedup (2015)

#180

Post by qayxc » Tue, Oct 13, 2020, 5:24 PM UTC

arcticbull wrote: post #112

qayxc wrote: post #82

Earlier quoted context omitted.

> It's largely only relevant when interviewing I find the opposite to be true, but it depends entirely on what problems you work with on a daily basis. Data structures and algorithms are a toolbox and the more you know, the more options you have at your disposal to tackle a specific problem. If you work in an area that doesn't benefit much from this specific set of tools, then yes, you only it during interviews; inte…

> I find the opposite to be true, but it depends entirely on what problems you work with on a daily basis. I suppose that's true, my perspective is as a client engineer where for the most part, someone's built the data structures for you. Yes you need to know their performance characteristics and when to use them, but otherwise if you're building them yourself you're doing something wrong. I'm sure that's not true in…

> I'm actually really passionate about recruiting and improving the recruiting process anywhere I work, I'd love you to elaborate on this.

Unfortunately this is a really complex topic and I'm afraid I'm not nearly knowledgeable or experienced enough to give any meaningful advice in a concise way.

Say a candidate is to be hired for developing and maintaining a line of business app. In this case it's important for them to know the programming environment, frameworks and tools, as well as working with large programs or legacy code if applicable.

Start by asking a few "no brainers" sprinkled into a general conversation about their previous work experience and increase the "difficulty level" from there.

There will come a point at which the only honest answer will be "I don't know" or "I'd have to look that up", which is the perfect opportunity to just hand them a tablet (or laptop) and let them do so. This is an excellent way to learn how they look-up technical information (which sites do they use, how long does it take them, do they use meaningful keywords).

Another effective way of judging someone's skill is asking them to point out problems with a small piece of code or have them discuss required modifications to meet some constraint (e.g. sort a dataset by one of a user-selectable set of criteria, but you can only read each item once and the dataset doesn't fit into memory - a common problem with archival data stored on tape).

These are just some pointers, but they all have two things in common: they require the interviewer to know what the candidate is going to work on and they need more preparation work than just a checklist that reads "knows how to implement an AVL-tree in Python" or "can tell the arguments of all 6 overloads of std::transform_reduce() in C++17".