Re: [MacPerl] sorting algorithms

["Scott R. Godin" <mactech@webdragon.net>]

on 11/09/2000 07:05 PM, Paul McCann at pmccann@maths.adelaide.edu.au wrote:

> 
> Scott Godin wrote:
> 
>> $master_maps_list{$gametype}{lc($title)} = [$filename, $title, $size,
>> $review, $rating];
>> how do I sort this data by $size and then by $filename/$title for the subset
>> of one of the five $gametype's ?
> 
>> basically, for a single gametype, I'd like to optionally sort the maplist
>> for that gametype first by rating, and second by filename or title, so that
>> all the n-rated maps are sorted alphabetically instead of arbitrarily.
> 
> Here's an attempt to create what you want:
> 
> # first some sample data: I've not tried to condense things too much
> # in the hope that it makes the process somewhat clearer. The only real
> # difficulty with such a data structure is pinpointing the piece that
> # you wish to use in the comparison.
> 
> $gametype='assault';
> $master_maps_list{$gametype}{'a'}=['a','titlea',60,'y',9];
> $master_maps_list{$gametype}{'b'}=['b','titleb',73,'n',8.5];
> $master_maps_list{$gametype}{'c'}=['c','titlec',51,'n',9.5];
> $master_maps_list{$gametype}{'d'}=['d','titled',51,'n',9.5];
> $master_maps_list{$gametype}{'aa'}=['aa','titled',51,'n',9.5];
> 
> # first a reference to allow less typing in what follows.
> 
> $ref=\%{$master_maps_list{$gametype}};

Nice trick. I knew this existed, but really hadn't seen it in action in the
context of what I'm using the script for. I'll have to ponder this sort of
usage and see if it can help me any in the future. *thanks*

> # the "sort block" below compares file size first (index 2 of the array)
> # and then filename (index 0) if the file size is equal. That is, if the
> # first comparison returns a zero. This just plays on the short circuit
> # behaviour of the || operator; if it gets a "true" result from the first
> # chunk (the <=> piece) it returns that value, which will be 1 or -1 ; if
> # not, it has to evaluate the second part to see if the overall expression
> # is true or false, so it compares file names. You can also throw the
> # contents of this block into a subroutine -- say mysort() -- and call it
> # using     @sorted = sort mysort keys %{$ref}

..and again, the detailed commenting is MUCH appreciated.. I can see how
this works MUCH more clearly now. I'll definitely be able to use this
elsewhere too. 

> @sorted = sort 
> { $ref->{$a}[2] <=> $ref->{$b}[2]
>                ||
>   $ref->{$a}[0] cmp $ref->{$b}[0] }
> keys %{$ref}; 
> 
> # now print out the sorted values...
> 
> foreach(@sorted){
>     my $string= join " :: ",@{$ref->{$_}};  # join the entries of the array
>     print $string,"\n";
> } 

While eating dinner out this evening (nice quiet LARGE beer and Filet Mignon
to 'relax my synapses', I brought along the crusty old Programming Perl
book, and sifted through it at random eventually winding up at the tail-end
of it, looking through 'programmer efficiency' things, mostly unrelated to
this, (looking for other ways to improve efficiency), and stumbled across a
short passage which *immediately* shot out at me and said "WAIT! look more
closely!" 

that passage was this :

    "Sorting on a manufactured key array may be faster than using a
     fancy sort subroutine. A given array value may participate in
     several sort comparisons, so if the sort subrutine has to do much
     recalculation, it's better to factor out that calculation to a
     separate pass before the actual sort."

in essence, what occurred to me upon reading this, was that if I can figure
out a way to 

    A> test if the sort is requested (ridiculously easy)
      a> if so, build the hash somewhat differently in the form of  (harder)

    $master_maps_list{$gametype}{ &coerce($rating) . $filename } =
        [$filename, $title, $size, $review, $rating];

    sub coerce {
        my $inrating = shift; # (this next is the 'hard' part)
        #if the rating is -1 (not rated) simply reutrn the string "NA"
        # this subroutine would thereafter ensure that the rating value was
        # o rounded to the nearest .5 ( <.25 >.75 )
        # o treated as a string for the return purpose.
        # o prepended with a 0 if <10 (i.e. 07 02 10 05)
        # o post-pended with .0 if rounded to an integer.
        #   (i.e. 07.0 10.0 05.5 02.5)
        return $coerced_rating;
    }

then the sorting of

    foreach ( sort( keys %{$master_maps_list{$gametype}} ) )

would practically take care of itself.

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? 

your call? 



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