Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

Old sorting paper holds the key to unlocking the secrets of the Schwartzian Transform

by aufflick (Deacon)
on Nov 07, 2005 at 04:27 UTC ( #506224=perlmeditation: print w/ replies, xml ) Need Help??

One of today's Meditation threads (To push and pop or not to push and pop?) mentioned "Shift, Pop, Unshift and Push with Impunity!" which in turn mentioned a paper by Uri Guttman and Larry Rossler called "A Fresh Look at Efficient Perl Sorting".

The link in that node is no longer valid, but it can be found on Uri's site http://www.sysarch.com/ here: http://www.sysarch.com/Perl/sort_paper.html.

The paper is quite old, but sorting hasn't changed much in 5 years! The main reason I am posting it here in Meditations is that this is the first document I have read that made me realise in only a few minutes exactly what the Schwartzian Transform does! It is basically a standard pre-caching sort manouvre, but using a pipeline of anonymous arrays instead of a temporary named hash.

Other than that, the paper is a good refresher of all that sorting algorithm thinking that you can never quite remember from University...

Update: Corrected the spelling of Uri's name - thanks sauoq

Comment on Old sorting paper holds the key to unlocking the secrets of the Schwartzian Transform
Re: Old sorting paper holds the key to unlocking the secrets of the Schwartzian Transform
by duff (Vicar) on Nov 07, 2005 at 04:51 UTC

    It's quite strange for me to see someone refer to such a recent work as "quite old". Newton's Principia is quite old; The Guttman-Rosler paper is quite new. :-)

      Newton's Principia is quite old; The Guttman-Rosler paper is quite new. :-)

      The Egyptian Book of the Dead is quite old; Newton's Principia is quite new. :-)

Re: Old sorting paper holds the key to unlocking the secrets of the Schwartzian Transform
by Anonymous Monk on Nov 07, 2005 at 05:18 UTC
    The transform is question is a basic technique and hardly deserves to be credited to the man with the name *sigh*.

    I wish there was a better name for it, something along the lines of keying records for the purpose of sorting.. it certainly is not some amazing special technique that could be one-day patented!

      I believe it is called "decorate-sort-undecorate" in the Python world (where it is being considered for entry into the core sort builtin).
        DSU (for short) is in list.sort() and the sorted() builtin as of 2.4 - eg: "mylist.sort(key=len)" will sort by length.

        Last I checked, Perl6 was also supposed to support decoupling the key comparison from the extraction of keys from list elements. In Perl5, key extraction is conflated with comparison in a single sub, which means the key extraction code for $a is often copypasted for $b. Given that key extraction is decoupled from comparison, you’d also often need simple forms of comparison only, so there were ideas being bandied about for a more declarative comparison syntax for those forms.

        Now the motivation for all this was to reduce duplication and make the trivial cases simpler, but such syntax would neatly allow the runtime to do ST sorting internally, without the programmer having to do anything explicit about it.

        I don’t know what came of it, but I’d be surprised if it hasn’t made it into the current form of Perl6 in some shape. I should go look into this.

        Makeshifts last the longest.

      Now that what it is is clearer to me, the amazing thing about it is actually Perl. The fact that you can chain the three stages together like that without the rigidity of traditional list based languages is really nice.

      On a related note, I know that you can chain the word "and" 5 times in a row in a gramatically correct English sentance - what's the most number of "is"s that people can chain together? I can do 3.

      Yes I know it's not really related, but I can never write a sentance with "is is" without then wondering :)

        How can you gramatically chain the word "and" more than once in a valid English sentence? I know you can do "that that" but "and and" escapes me..
        5 times for and?

        Would the sentence, "I put dashes between Fish and And and And and Chips in my Fish And Chips sign" be clearer if I put commas between Fish and and, and and and And, and And and and, and and and Chips?

        As for is, it is kind of cheating, but, "Is is is?" is "Is is is?"

        However the real record holder is buffalo. Buffalo can mean the city, the animal, or "to bewilder and confuse". Between those three meanings you can always find a correct gramatical parse for the word Buffalo, repeated any number of times. For instance, Buffalo buffalo buffalo buffalo buffalo Buffalo buffalo! means "Buffalo buffalo bewilder and confuse buffalo that bewilder and confuse Buffalo buffalo."

        Howdy!

        James, while John had had "had" had had "had had". "Had had" had had a better effect on the teacher.

        That's seven hads in a sentence, with eleven across a sentence break.

        yours,
        Michael
      Many Monks have begun calling this transform the Evan transform after the publishing of this node. While still a proper name not bearing any relation to the transform's function, it is at the least easier to pronounce.


      Evan Carroll
      www.EvanCarroll.com

      jdporter - fixed link

Re: Old sorting paper holds the key to unlocking the secrets of the Schwartzian Transform
by salva (Monsignor) on Nov 07, 2005 at 09:29 UTC
    The paper is quite old, but sorting hasn't changed much in 5 years!

    well, it has: Sort::Key!

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://506224]
Approved by Albannach
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (6)
As of 2014-09-17 02:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

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











    Results (56 votes), past polls