5 ms·
I think you're sweeping an important distinction under the rug. If every major language provides an O(n log n) sort function, is it still a leaky abstraction?
by skybrian 10y ago
I think you're sweeping an important distinction under the rug.
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.
- nullc 10y ago> You can use it without worrying much about the details. 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.
- sirclueless 10y agoSpeaking from experience, I've had to worry about what implementation of sort is being used in many languages, from Java to C++, even Go and Python. 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.
- im3w1l 10y agoThose properties should ideally be part of the documentation so that the abstraction stops leaking.
- 4ad 10y agoOne could argue that if these details are necessary for correct/performant operation, then it is a leaky abstraction.
- im3w1l 10y agoTo me a leaky abstraction is an abstraction that does not expose all the relevant details. So if those details are written on the spec sheet of the black box then there is no leak. If the box is only labelled with O(nlog n) without specifying constants then there is a leak.
- ezanmoto 10y agoI feel that if you care that much about the internals of the abstraction then you don't necessarily want an abstraction anymore, but rather the concrete thing that is being abstracted over. I think abstraction is an admirable quality that has numerous advantages, but if you need guarantees on the properties of what's under the abstraction then an abstraction is probably not what's needed at that point.
- fizixer 10y ago> If every major language provides an O(n log n) sort function, is it still a leaky abstraction? 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.
- quelltext 10y agoThe implementation is a black box but the performance characteristics could very well be part of the API contract. When you require and it's feasible to use radix sort you probably know not to use the standard sort function.
- smallnamespace 10y agoYes, but reasoning about the API contract is exactly what being taught sorting algorithms helps you navigate, just like learning the guts of backprop helps the ML practitioner understand why things can go wrong.
- paulddraper 10y ago> If every major language provides an O(n log n) sort function, is it still a leaky abstraction? I'd say no. 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.
- joe_the_user 10y agoPerhaps the distinction would be between things that are "fundamentally a heuristic with some math behind it" versus things are "mostly theoretically settled with some corner cases you have to worry about" 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.
- hiddencost 10y agoExcept that for nontrivial use cases, the many different nlogn sort algorithms have trade offs which matter. A friend just wrote his own sort implementation optimized to maximize cache hits, because of certain quirks of his data that he knows ahead of time. 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.
- belvoran 10y agoWhat is O(n log n)? Time complexity? What about memory requirement? Last month I decreased memory requirement from 16GB to 100MB in one implementation of a "stable&fast" algorithm. Really, using a function just because it's O(n log n) without understanding its characteristic is like a blind surgeon randomly amputating limbs because maybe it will help. But that's fine for me, I have more work then, fixing software bugs made by incompetent* programmers is quite nice. *incompetent - those who think they know something and are not willing to learn anything new
- mypalmike 10y agoWhy do you assume the commenter doesn't understand the time and memory characteristics of quicksort?
- RyanZAG 10y agoNobody mentioned quicksort. You're assuming quicksort, which is what the issue is. Many languages don't actually use quicksort, fyi. The practical performance considerations of just quicksort itself also change depending on how you've implemented the small details - are you moving memory around, or just changing pointers? Huge difference in the real world, no difference in the algorithm.
- mypalmike 10y agoI oversimplified my response and it lost the point I was making. You are certainly correct that many languages don't use quicksort. My bad. 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.