Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Re: (OT) The Schwartzian Transform in Java

by fletcher_the_dog (Friar)
on Jun 10, 2003 at 21:14 UTC ( #264862=note: print w/replies, xml ) Need Help??


in reply to (OT) The Schwartzian Transform in Java

Please excuse my ignorance, but what is so cool about the Schwartzian Transform? All I can tell that it does is sort words by length. It seems that if that is all you wanted to do you could just do:
my @in = qw/foobarbazquux boo foobarbaz foobar/; my @out=sort {length($a) <=> length($b)} @in; foreach (@out) { print "$_\n"; }
What am I missing?

Replies are listed 'Best First'.
Re: Re: (OT) The Schwartzian Transform in Java
by Enlil (Parson) on Jun 10, 2003 at 21:27 UTC
    The Schwartzian Transform is a sorting technique (not just for sorting by length), that keeps you from having to keep from repeatedly calling a potentially slow expensive function in a sort. For more details be sure to check out this and the column on sorting merlyn has listed there.

    -enlil

Re: Re: (OT) The Schwartzian Transform in Java
by djantzen (Priest) on Jun 10, 2003 at 21:26 UTC

    This is only one very simple use of the Transform intended to demonstrate that it can be done in Java. You are correct that the problem as described is better solved in your code sample. The point of the Transform is to precompute expensive values to make the sort go faster. The general form is map, sort, map, but the bodies of those function calls may do whatever you want. A common example is sorting files based upon size:

    @sorted_by_size = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [$_, -s] } @files;

    HTH, djantzen


    "The dead do not recognize context" -- Kai, Lexx

      I was originally going to comment that I hated the style that you had used for the ST in your original code. But here you have it more or less as I would write it. Cool. :-) I find that emphasizing the bottom to top, or right to left effect of the chain, with as minimal obscuring parenthesis to be much more readable. And this is the point that most people get confused with about ST's and chaining list operators, the information flows right to left at first this can seem odd, but to me it makes total sense, in that the information flow involves an explicit or implicit assignment. Assignments are left associative, and flow to the left. However from the method invocation POV the right to leftness confounds their usual expectation of left to rightness. For instance in an oo language we might expect an ST to be written like (and i believe Ruby does it close to this)

      @newfiles=@files.map([-s($_),$_]).sort($a->[0]<=>b->[0]).map(pop @$_);

      but since we arent doing method invocation, but rather using list operators in an assignment statement we end up with the at first weird looking bottom to top, right to left. (here i was going to say "it wouldnt be hard to write an OO implementation", but I ended up writing a proof of concept instead, and I can say it wasnt that hard, except for some unexpected nonsense with sort.) Here it is:

      package main; my @x=Array->new( qw( bb cccc ddd aaaaa fffff qqq xxx iiiii ) ) ->map('[length($_), $_ ]') ->sort('$b->[0] <=> $a->[0] || $a->[1] cmp $b->[1]') ->map('pop @$_'); print "@x";

      So theres a perl OO implementation of the list operators in perl. :-) I kinda got carried away, sorry. :-) (The rest of this mail is what I originally intended to post, somehow this has become a major digression. My apologies.)

      Also, I have a little personal rule with ST's. I always put the payload on the end. This way your code becomes

      @sorted_by_size = map { pop @$_ } sort { $a->[0] <=> $b->[0] } map { [-s $_ , $_ ] } @files;

      I do this because if you need to add sort criteria you can, but when you see the criteria in a list, like:

      @sorted_by_ext_name_size = map { pop @$_ } sort { $a->[0] cmp $b->[0] || $a->[1] cmp $b->[1] || $a->[2] <=> $b->[2] || 0 } map { [reverse(lc($_)=~/([^\\\/]+?)(\.[^.]+)?$/),-s($_),$_ ] } @files=glob ('c:/winnt/*.*'); print join(",\n",@files); print join(",\n",@sorted_by_ext_name_size);

      You see all the slots. I suppose you could do it the otherway round, but then you have to say { shift @$_} or { $_->[0] } but I find { pop @$_ } is easier to type and somehow more suggestive of the underlying idea. The stylized way I wrote this is meant to make changing the criteria easier. By putting the 0 at the end, lines can be rearranged without worrying, and it has no real performance effect afaict. (For instance to remove the need for the reverse statement, all you need is a single cut and paste to reorder the sort criteria. Its to make this point that I put it in. :-)

      Anyway, just thought Id throw my 2 cents in. I know other people have other preferences, and as long as they are readable I dont mind that much. :-)
      ---
      demerphq

      <Elian> And I do take a kind of perverse pleasure in having an OO assembly language...

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (3)
As of 2023-10-04 22:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?