Comment by araneae | Hacker News Reader

Comment by araneae | Hacker News Reader

Parent Full thread

I think that is in some way flawed.

For instance, it's possible to mathematically prove in some cases that one algorithm is better than another; a set of ten nested for loops simply has greater time complexity than one. You don't need to actually test which algorithm is better.

And secondly, your intuition can be bad, but it's not guaranteed to be wrong, either. If you're a very experienced developer you might have a feeling about what's a more efficient way to code something up that could be in general, correct. Not every decision you make needs to be tested.

However, there is absolutely no point in arguing whose algorithm is better if there IS an argument about it since it can be tested easily. Also, if you personally are not sure which approach is better, test it.

And finally, you're actually in luck if you have two algorithms that you can test and find the better one. That's an easy situation to deal with. It's actually much harder if you only have one algorithm and it's a slow memory hog. Testing is only as good as the options you give it.

(On a related note, this is especially important to remember in science, too- testing hypotheses is only as good as the hypotheses you come up with to test. There could always be a correct hypothesis out there and you never even conceived of)

> For instance, it's possible to mathematically prove in some cases that one algorithm is better than another; a set of ten nested for loops simply has greater time complexity than one. You don't need to actually test which algorithm is better.

At the risk of being pedantic, I want to point out that it's not always so clear-cut. Take sorting, for example. Everybody knows that quicksort is quick; it says so right there in the name. It runs in O(n lg n) time with small constant factors. But for small arrays, or arrays which are mostly sorted already, you can do better by using insertion sort, which runs in O(n^2) time. Somewhere in the bowels of glibc is a highly-optimized quicksort which does exactly this: it drops down to insertion sort for subarrays of size 6 or less.

And don't even get me started on the effects of cache locality. The point is, sometimes intuition and analysis of algorithms can only go so far; at some point you've got to either test it or just call it "good enough" and think about something else.

At the risk of being pedantic: quicksort has a worst-case runtime of O(n^2).

At the risk of being even more pedantic, quicksort with the O(n) deterministic median finding algorithm has a worst-case runtime of O(n log n) -- you use that algorithm to find the median each time and use that as the pivot.

The constants would make it less efficient for most cases, though.

empiricism has the potential benefit of including unconsidered factors, or exposing misleading priors. Cache locality is a great example of a possibly overlooked confounding factor.

there is no pure or complete ordering of reason, intuition or empiricism. Wisdom is knowing when each approach is the best fit, and understanding that even the best approach selection heuristic is not 100% reliable.

Reply on news.ycombinator.com