Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

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

by Jenda (Abbot)
on Feb 06, 2007 at 16:20 UTC ( #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.


Comment on Re: RFC:A brief tutorial on Perl's native sorting facilities.
Download Code
Re^2: RFC:A brief tutorial on Perl's native sorting facilities.
by BrowserUk (Pope) 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
Node Status?
node history
Node Type: note [id://598572]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (16)
As of 2014-09-18 15:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (116 votes), past polls