Perl: the Markov chain saw | |
PerlMonks |
Re^4: Better sorting than the STby Aristotle (Chancellor) |
on Feb 13, 2007 at 04:29 UTC ( [id://599632]=note: print w/replies, xml ) | Need Help?? |
I was talking about memory, not efficiency. Even if Perl had tuples, ST still requires extra memory for container structures proportional to the size of the list being sorted, whereas index sorting only requires a single container. Although in terms of big-O, that’s irrelevant, since if you consider the keys as well, then the ST requires extra memory on the order of n · (s + a) (where s and a are constants and stand for the overhead of a scalar and array, respectively) whereas index sorting only requires n · s + 1 · a; but these are both O(n). My bad. Of course, in Perl, there’s a huge difference between the two because n · a easily becomes a considerable quantity. However, I don’t see how index sorting is a premature optimisation. It’s not just parsimonious with memory, it’s also easier to follow (in my opinion) than the ST for someone who has never seen either idiom. The real way to go about making sorting faster would of course be to decouple key extraction from the comparator function, which would allow almost all sorts to be written declaratively. There was discussion about this on perl6-language back when I was subscribed, but I don’t know if anything came of it. Makeshifts last the longest.
In Section
Meditations
|
|