5 ms·
I guess I'm showing my youth here but I never imagined that sorting on a computed key was once known by such an exalted title as Schwartzian Transform. This is
by civilized 5y ago
I guess I'm showing my youth here but I never imagined that sorting on a computed key was once known by such an exalted title as Schwartzian Transform. This is basic, built-in functionality in Python.
- bsder 5y agoIt's not just that the key is computed, but that the key has an internal sort comparison which is way faster than a user code comparison. It was an example of the fact that "Big-Oh notation is nice, but constants sometimes matter." Both sorts have the same O(n log n) number of operations performance. However, in Perl, using an internal comparison for integers was a significant constant faster than using a user specified comparison function--at least an order of magnitude and sometimes two. Consequently, the 2*O(n) to decorate and undecorate the list with integers to sort by got swamped by the 1/10*O(n log n) sort improvement. I believe that this overhead eventually got reduced. However, I remember using this a LOT in Perl 4 and early Perl 5 days.
- civilized 5y agoSounds generally plausible to me. I learned all sorts of obscure tricks to make MATLAB run faster in my grad school days... I wouldn't be surprised if something like this was useful over there as well.