Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery

Re: Refactor my sort

by imp (Priest)
on Dec 22, 2006 at 16:07 UTC ( #591349=note: print w/ replies, xml ) Need Help??

in reply to Refactor my sort

As all of your values are numeric this looks like a good candidate for a Guttman Rosler Transform

Comment on Re: Refactor my sort
Re^2: Refactor my sort
by Herkum (Parson) on Dec 22, 2006 at 16:42 UTC
    Looking at it, you are probably right that my code would be a good candidate for this. However I am reading the documentation, and I will be honest, I don't understand it.

      My take on it is this: the comparison operator on a string is a bit slow since it has to take locale and such into account. The GRT basically packs the data into a string of bytes such that a simple numeric comparison would reliably sort the data.

      This saves you time because rather than go through the locale-conversion code to order the strings each time they're accessed, you perform the conversion once (during pack), then you just treat the keys as integers X bytes long, which are much simpler to compare.


        The GRT packs the data into a string, yes, but I'm pretty sure the sort is then lexical, not numeric. I believe that pack is the usual tool for creating the string but GrandFather did one here that used sprintf.



Re^2: Refactor my sort
by ikegami (Pope) on Dec 23, 2006 at 00:25 UTC

    I'm not so sure. Functions calls are expensive, but are they expensive enough and is there enough data to sort to make the drop in readability worth the gain in speed?

    Here's something you can use to benchmark.

    our @unsorted; local *unsorted = $self->teams(); my @sorted; # Allocate memory up front. $#sorted = $#unsorted; # Is it possible to do this faster? for my $i (0..$#sorted) { local *_ = \($unsorted[$i]); $sorted[$i] = pack 'C6N', 255-($_->get_wins_total()), # Descending 255-($_->get_wins_division()), # Descending 255-($_->get_wins_home()), # Descending 255-($_->get_runs_scored()), # Descending $_->get_runs_allowed(), # Ascending $_->get_reg_schedule_id(), # Ascending $i; } # In-place lexical sort. @sorted = sort @sorted; for my $i (0..$#sorted) { $sorted[$i] = $unsorted[unpack('x6N', $sorted[$i])]; }
Re^2: Refactor my sort
by throop (Chaplain) on Dec 23, 2006 at 05:11 UTC
    Q: And what sort of an honest man are you?
    A: I'm a sort-of honest man.
    This is indeed a good candidate for Guttman Rosler. But note carefully. He wants to sort some keys ascending, others descending. In addition to the pack, he'll need a transform which will turn descending keys into ascending ones (or vice versa.) E.g. subtract each descending key from 1000. That will only add trivially to the computation time. But it will add another layer of difficulty for the maintainer's comprehension.

    But many that are first shall be last; and the last shall be first. — Matt 19:30

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (7)
As of 2014-09-16 06:10 GMT
Find Nodes?
    Voting Booth?

    My favorite cookbook is:

    Results (157 votes), past polls