Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid

Re^4: Better sorting than the ST

by Aristotle (Chancellor)
on Feb 13, 2007 at 04:29 UTC ( #599632=note: print w/replies, xml ) Need Help??

in reply to Re^7: Perl is dying (better sorting than the ST)
in thread Perl is dying

it appears to me that with an ST you have N steps to create the arrays, and N steps to unpack them, with your code you have N steps to create the key array, and N steps to map the sorted keys back to real values.

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.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://599632]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (2)
As of 2020-08-09 23:29 GMT
Find Nodes?
    Voting Booth?
    Which rocket would you take to Mars?

    Results (55 votes). Check out past polls.