Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

When does it pay to use the schwartzian transform?

by tphyahoo (Vicar)
on Dec 16, 2005 at 18:44 UTC ( #517329=perlquestion: print w/replies, xml ) Need Help??

tphyahoo has asked for the wisdom of the Perl Monks concerning the following question:

When is the S.T. the way to go for sorting? And why? Does it win you efficiency, or is it mainly just for readability? Can some wise ones present the community with scenarios when you just should to use S.T., versus sorting some other way?

(decided to do a SOPW on this after posting Re^2: Sorting an array on two computed fields.)

I feel like this has probably already been discussed elsewhere, but my preliminary searches didn't pull any slam dunks, so please link to where the good stuff is if you know!

UPDATE: After reading some of the follow up links posted, I understand why "Schwartzian" sort performs better when the sort involves calling an expensive filesystem call, such as chcking file size. (See in particular Benchmark, -s versus schwartzian)

I now wonder... are there other general types of situation where it "pays"?

UPDATE 2: However, merlyn concedes that the -s (file size operator) for showing off S.T. may actually be a bit contrived: Re: Benchmark, -s versus schwartzian.

UPDATE 3: Merlyn also characterizes S.T. as a less "ideal", but much more maintainable, approximation of sort using another technique, the GRT (Guttman Rossler Transform): •Re^4: Benchmark, -s versus schwartzian

  • Comment on When does it pay to use the schwartzian transform?

Replies are listed 'Best First'.
Re: When does it pay to use the schwartzian transform?
by Roy Johnson (Monsignor) on Dec 16, 2005 at 19:49 UTC
    Sorting is an O(n log n) operation, so the comparison sub gets called on average more than once for each element of the list being sorted. So if you have some sort of transformation to do to the data, you're going to be doing it multiple times for at least some of the elements if you include the transformation in the comparison sub.

    If the transformation is expensive relative to building an arrayref and dereferencing it, the ST will give you gains in efficiency as the number of elements to be sorted increases, because you do the transformation exactly once per element.

    Another way to get the do-it-only-once efficiency would be to Memoize (or cache the results from) the transformation function.


    Caution: Contents may have been coded under pressure.
      Another way to get the do-it-only-once efficiency would be to Memoize (or cache the results from) the transformation function.

      Also known as the Orcish Maneuver, and often more efficient.


      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
Re: When does it pay to use the schwartzian transform?
by runrig (Abbot) on Dec 16, 2005 at 18:53 UTC
    It "pays" when the cost of pre-computing the sort keys for all of your elements is significantly less than re-computing the sort keys each time you make a comparison. It depends on the cost of computing a sort key, and the number of elements.

      When in doubt, test it with the Benchmark module

      Jason L. Froebe

      Team Sybase member

      No one has seen what you have seen, and until that happens, we're all going to think that you're nuts. - Jack O'Neil, Stargate SG-1

      It "pays" when the cost of pre-computing the sort keys for all of your elements is significantly less than re-computing the sort keys each time you make a comparison.
      Well, in most of those cases, it pays to use the Gutman-Rossler Transform.
      Perl --((8:>*
Re: When does it pay to use the schwartzian transform?
by ChrisS (Monk) on Dec 16, 2005 at 19:24 UTC
Re: When does it pay to use the schwartzian transform?
by salva (Canon) on Dec 16, 2005 at 22:38 UTC
    the ST uses much more memory than plain sort, so if you have to sort lots of elements, the system can be forced to swap memory to disk and at this point the performace is going to degrade dramatically.

    ... and anyway, the ST (and the GRT) became obsolete the day I released Sort::Key ;-)

Re: When does it pay to use the schwartzian transform?
by GrandFather (Saint) on Dec 16, 2005 at 20:53 UTC
Re: When does it pay to use the schwartzian transform?
by merlyn (Sage) on Dec 16, 2005 at 20:20 UTC
Re: When does it pay to use the schwartzian transform?
by SolidState (Scribe) on Dec 18, 2005 at 06:34 UTC
    Repeating my answer from node 476724:

    A good place to read about sorting in Perl and specifically the "Schwartzian Transform", is Shlomo Yona's lecture slides on Sorting in Perl.
    This will give you not only a good explanation of the Schwartzian Transform itself but will also put it in context with other sorting techniques. Check out the "Orcish Maneuver" - sounds like something you would do in World of Warcraft :-)

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://517329]
Approved by BrowserUk
Front-paged by BrowserUk
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (6)
As of 2022-10-06 07:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My preferred way to holiday/vacation is:











    Results (26 votes). Check out past polls.

    Notices?