Re: [MacPerl] sorting algorithms

[Paul McCann <pmccann@maths.adelaide.edu.au>]

Hi Scott,

          On Friday, 10 November 2000 at 1:04PM  you wrote:

>Does this make any sense, or am I just imagining things? Did I just get
>*really* lucky to stumble across this germ of an idea and be in a state of
>mind to handle the 'epiphany' or am I totally wacked and smokin' da wrong
>sheiat? 

I'll vote for the former: you've milked the meaning from the PP passage.
Essentially do all the dirty stuff *outside of the sort subroutine*, sort on
the transformed data, and then perhaps reconvert. Almost everyone reading is
probably expecting the words "Schwartzian Transform" to appear here, so
there you go. 

[[Just in case someone reading *hasn't* tripped over this construct: the
Schwartzian Transform works something like...

(1) use a map operator to create an anonymous array for each element of the
array that you wish to sort, the second (and third/fourth etc if required;
see the example below) element of which is the number/string/construction on
which you wish to sort.

(2) sort using (in the simplest case) using

sort {$a->[1] <=> $b->[1]}   # ie use the already_transformed data

(this is obviously for a numerical sort; adjust as required, and add in
extra conditions using $a->[2] etc if you've built equality breaking data
into the third/fourth etc elements of the anonymous array)

(3) map things back to the format that you started with

map {$_->[0]}

For the example (cf previous messages) that we've been kicking around this
would look something like:

------------------------------------------------------------------------

$ref=\%{$master_maps_list{$gametype}};

@sorted = map{$_->[0]}                                #step 3
sort {$a->[1] <=> $b->[1] || $a->[2] cmp $a->[2]}     #step 2
map{[ $_,$ref->{$_}[2],$ref->{$_}[0] ]} keys %{$ref}; #step 1

------------------------------------------------------------------------

Whether or not it's quicker probably depends on the size of your hashes and
the complexity of the operation being performed. For large hashes and
moderately complex operations (eg finding the size of files in a directory
listing) you'll almost certainly get a decent increase in speed, because you
only make the transformations once per element instead of each time a
comparison is made.

The down side to the "multiple comparison" version is that in cases where
the second comparison is rarely needed you may end up doing *more* work
using the above technique because you've lost some of the short-circuiting
gains from the more traditional sorting routine presented earlier. Horses
for courses...

As always, corrections, clarifications and extensions are most welcome.]]

Cheers,
        Paul


# ===== Want to unsubscribe from this list?
# ===== Send mail with body "unsubscribe" to macperl-request@macperl.org