News for hackers. Stuff that matters.
Re:Should CS students be graded on performance? by JoachimSchipper on Sunday March 06, 2011 @02:37AM (#2293725)
Actually, "fast on small n" does matter. Many real-world qsort() implementations have an insertion sort in the inner loop (e.g. for sorting chunks of 8 elements) - and while the number of elements is small, this routine is called often enough that it matters.

That said, some abstraction is useful too.

Re:Should CS students be graded on performance? by chalst on Sunday March 06, 2011 @03:00AM (#2293754)
But this optimisation is applied many times: it is the leaf case of such qsort algorithms. So it affects the constant scaling factor at all ns, not just for small ns.
Re:Should CS students be graded on performance? by JoachimSchipper on Sunday March 06, 2011 @06:53AM (#2294039)
I thought I was being totally clear, but seeing your comment and its upvotes, apparently not. What exactly did your "but" refer to? I think we're in complete agreement...

(I was trying to say: here's an example where properly using a fast-for-few-elements "toy" algorithm can improve real-world performance on a "serious" problem like sorting a big chunk of data. So big-O is not everything.)

Re:Should CS students be graded on performance? by chalst on Monday March 07, 2011 @03:52AM (#2296539)
The point is that this improvement doesn't deliver a speed up that is significant only for small n, but a speed up everywhere.

I agree that fast on small n does matter, it's just that this isn't an example.

Re:Should CS students be graded on performance? by JoachimSchipper on Monday March 07, 2011 @07:48AM (#2296943)
Thanks for clarifying! (Still, you get a global speedup because the "inner" algorithm is fast for small n.)