There are a lot of details to get right: how are elements compared? Is the sort stable? Is it efficient for small N? Is it efficient for nearly-sorted arrays? Is it efficient when almost all the elements compare equal? Is it guaranteed O(n log n) or average? If average, is there an input that reliably triggers n^2 behavior making it a DDoS vector?
Anything is a leaky abstraction when you care enough.
If the box is only labelled with O(nlog n) without specifying constants then there is a leak.
In much the same way, much of the interesting work with machine learning requires deep specialist knowledge in which selecting the best approach requires digging beneath the abstraction. Many specific applications have their own quirks, which is where significant gains are often made. (To be honest, I think the last year was more exciting for the advances in applied ML than in theoretical work.)
A co-worker wrote a library for distributed training of DNNs for a specialized use case. Because of certain quirks of our use case (think sparsity and consistent patterns in the data), there were certain optimizations he could make to the training process that gave nice linear scaling in the number of training nodes.
*incompetent - those who think they know something and are not willing to learn anything new
And then worst case? Best case? Average case? Which applies to random input? Nearly-sorted input? What's the overhead for a "short sort", can/should I use this to sort small sequences in a tight-ish loop or is it only for large sequences?
I was under the illusion that Big-O was always asymptotic complexity (ie worst case) and that other notations (little-o, big-omega, big-thetha etc) were used for best/average/etc case. Perhaps I'm wrong, however.
Which applies to random input? Nearly-sorted input? What's the overhead for a "short sort", can/should I use this to sort small sequences in a tight-ish loop or is it only for large sequences?
Indeed. The details matter.
My favourite example is how a naive linear search can perform better than a non-linear search with a better (in O() terms) algorithm if, for example, the linear search can do most of its work in cache (eg small input sizes or otherwise regular access patterns (predictable for prefetch)).
No, asymptotic notation only refers to the behaviour of the function (or algorithm) as you take the limit N->inf, e.g. changes to the size of the input. But the nature of the input often changes the behavior as well.
I was responding to a comment that I felt was needlessly dismissive. The default sort algorithm of any major language's standard library is usually not worth trying to beat, and calling someone "incompetent" for not reinventing the wheel each time they encounter data that needs to be sorted is absurd. Note: I said "usually", not "never". A competent programmer doesn't fix problems that don't exist, and you would absolutely have to profile code before convincing me that the choice of sorting algorithm was the source of a performance problem.
As far as the details go... In only a few languages (e.g. C) might you really even consider moving memory around rather than pointers. The semantics of standard library sort in Java, C#, Ruby, Python, Javascript... is sorting an array of primitives by value or objects by reference.
Great example :) You get different results if you use merge sort or quicksort.
The former is stable; the latter is not.
Okay...so you can be more specific with your API and specify whether stability is guaranteed. Eventually you can be specific enough that you essentially characterize the implementation.
Yes, if the performance is still not acceptable and you look into the problem and discover that your scenario could benefit from radix sort, or one of partial sorting, or some kind of intermittent sorting, all of which would require investigating the specific case at a "white box" level, ignoring the existence of a black-box O(n-log-n) sort API call.
I invite you to start sorting data which is often already sorted (or often all identical) and tell me you didn't need to worry about the details.
And neural networks using backpropagation to minimize an error function are definitely the former while the "go to" techniques of mathematics are generally the latter.
I think this is generally acknowledged, in fact.
Sooo it seems logical that students of these modern machine learning techniques should be impelled to "get their hands dirty" with the numericals processes involved since this will add to the data they use to drive the intuitions which allow them to avoid the multiple pitfalls of neural networks.
If every major language provides an O(n log n) sort function, is it still a leaky abstraction? I'd say no. You can use it without worrying much about the details.
But it sounds like the situation with back-propagation is different, since the internal details of the algorithm affect whether you get a usable answer at all.
A borderline case might be something like a SQL database, where in theory, creating an index shouldn't change query results, but in practice, the performance can change so much that it effectively does.
Unlike with back-propagation, you can tune database performance without worrying about queries returning different results (assuming they don't time out). So it's still a useful guarantee.