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

[aufflick]

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

[duff]

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. :-)

[Anonymous Monk]

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. :-)

[salva]

The paper is quite old, but sorting hasn't changed much in 5 years!

well, it has: Sort::Key!

[Anonymous Monk]

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!

[gaal]

I believe it is called "decorate-sort-undecorate" in the Python world (where it is being considered for entry into the core sort builtin).

[eyepopslikeamosquito]

Erm, no, Python's "decorate-sort-undecorate" is closer to the GRT than the Scwhartzian Transform ... as pointed out in this "old" fwp thread. Curiously, and following on from this, some years later davorg received a surprise free copy of the 2nd edition of the Python Cookbook! :-)

See also this classic "old" PM node: Advanced Sorting - GRT - Guttman Rosler Transform.

[MonkOfAnotherSect]

DSU (for short) is in list.sort() and the sorted() builtin as of 2.4 - eg: "mylist.sort(key=len)" will sort by length.

[Aristotle]

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.

[aufflick]

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 :)

[tilly]

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."

[jZed]

Is you is or is you ain't my baby?

[herveus]

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.

[monarch]

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..