Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re: RFC:A brief tutorial on Perl's native sorting facilities.

by Jenda (Abbot)
on Feb 06, 2007 at 16:20 UTC ( [id://598572]=note: print w/replies, xml ) Need Help??


in reply to RFC:A brief tutorial on Perl's native sorting facilities.

I think another good node about sorting is Better sorting than the ST (was: Perl is dying), I think this "trick" should be included in the tutorial as well.

{ my @keys = map {...} @list; my @idx = sort {$keys[$a] cmp $keys[$b]} (0..$#list); @list = @list[@idx]; } # or { my @keys = map {...} @list; @list = @list[ sort {$keys[$a] cmp $keys[$b]} (0..$#list) ]; }
As it doesn't create lots of tiny arrays it should even be quicker than ST. And it doesn't have the restrictions of GRT.

Replies are listed 'Best First'.
Re^2: RFC:A brief tutorial on Perl's native sorting facilities.
by BrowserUk (Patriarch) on Feb 06, 2007 at 16:46 UTC

      GRT requires that you stringify (serialize) the values of the list you want to sort. That's not always possible. Eg. if it's a list of objects ...

      And even if it's just a list of references to some data structures, by serialization and deserialization you end up with copies of the data structures. Which may matter a lot if you keep other references (in)to the structures.

        That's not always possible. Eg. if it's a list of objects ...

        If the data is a list of objects to be sorted

        1. then their class(es?) would need to overload cmp and/or <=> in order that you sort to sort them.

          And if that is the case, then each pair of objects would need to be compared using that overloaded operator and there would be no benefit from using any of the indirect sorting methods.

        2. Or, the mapping step in what you describe, would need to return a stringified or numified representation (key) of the objects (to populate the @keys array in your examples), and these would then be compared using the standard non-overloaded comparison operators.

          In which case, the GRT would work just fine; avoid the creation of the keys array and the slice operation. That means the GRT would avoid the creation of several intermediate arrays and lists. It also avoids the callback into Perl code (it's main strength, and the reason for its performance), and so will normally be faster.

        And even if it's just a list of references to some data structures, by serialization and deserialization you end up with copies of the data structures.

        I do not understand what you mean by this? In particular, the GRT never requires the keys to be "deserialised".

        Whatever you put into the @keys array, has later to be compared using one of the standard comparison operators. With that being the case, using the GRT again avoids the need for callbacks and will be faster.

        I realise that I am probably missing something here, but do you have any practical examples of when this indexed sort method with outperform a GRT?


        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others having an uproarious good time at the Monastery: (5)
As of 2024-03-28 23:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found