in reply to To use a module...or not.

How would you simplify/clarify the coding of ST?

By not using an ST in the first place. In practice I prefer something like 
my @array = @array[ do {
    my @rank = map &sortkey_calc @array;
    sort { $rank[$a] <=> $rank[$b] } 0 .. $#array;
} ];

[download]
It's also generally faster than an ST and degrades more gracefully, too.

Makeshifts last the longest.

Replies are listed 'Best First'.
Re^2: To use a module...or not.
by BrowserUk (Patriarch) on Jul 27, 2004 at 16:55 UTC

    By all means, go ahead and code that for the original problem :) It would be an interesting comparison.

    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "Think for yourself!" - Abigail
    "Memory, processor, disk in that order on the hardware side. Algorithm, algoritm, algorithm on the code side." - tachyon
[reply]
[d/l]

      It seems like that problem is needlessly being complicated by conflating key extraction and sorting. (This was an issue that was discussed on perl6-language about the current sort operator — how do we make it possible to isolate the extraction code from the actual sort order, which should then be possible to request declaratively?)

      sub order_of_sorted {
    my ( @num, @suff );
    for( @_ ) {
        m/ \A (\d+) \. (.*) /x or die "malformed data";
        push @num, $1;
        push @suff, $2;
    }
    sort { $num[$a] <=> $num[$b] or $suff[$a] cmp $suff[$b] } 0 .. $#_
+;
}

for my $outer ( ( values %hash )[ order_of_sorted keys %hash ] ) {
    for my $inner ( ( values %$outer )[ order_of_sorted keys %$outer ]
+ ) {
        # ...
    }
}

      [download]

      If you want to store the data rather than output it, you can transform the nested for-loops to an equivalent chain of maps (but note that that doesn't make it an ST).

      I know which version I'd prefer to maintain, even though this is probably slower than your GRT.

      Update: the following, which I originally wrote, is obviously wrong:

         for my $inner ( ( values %$outer )[ order_of_sorted keys %$inner ] 
+) {
   #                        ^^^^^^^ Correct.                ^^^^^^^ Oo
+ps.

      [download]

      Makeshifts last the longest.

[reply]
[d/l]
[select]

        Actually, it runs a fair bit quicker than either of my GRT versions. However, it does share the flaw that my first attempt at a GRT had; namely that there is no way to associate the keys with the resultant sorted values--which was a requirement for the OP.

        I'm not sure that there is any easy fix for that using an indexed sort on this type of data, but for shear speed it is hands down winner. 

        P:\test>376443 -NMAX=10 -AMAX=J >null
100 trials of ST (32.970s total), 329.704ms/trial

100 trials of GRT1 (15.892s total), 158.917ms/trial

100 trials of GRT2 (21.531s total), 215.313ms/trial

100 trials of indexed (8.344s total), 83.438ms/trial

100 trials of indexed2 (10.531s total), 105.313ms/trial

        [download]

        'indexed' is your code as posted. 'indexed2' is the same but using maps.

        Examine what is said, not who speaks.
        "Efficiency is intelligent laziness." -David Dunham
        "Think for yourself!" - Abigail
        "Memory, processor, disk in that order on the hardware side. Algorithm, algoritm, algorithm on the code side." - tachyon
[reply]
[d/l]

In Section Meditations