in reply to Sort Array by length of Value

How can there be a node about sorting without mentioning the Schwartzian Transform? I know it is overkill in this case. 
use strict;
use Data::Dumper;
my @array = (
    'four',
    'three',
    'three|four',
    'two',
    'two|four',
    'two|three',
    'two|three|four',
    'one',
    'one|four',
    'one|three',
    'one|three|four',
    'one|two',
    'one|two|four',
    'one|two|three',
    'one|two|three|four'
);

@array = map {$_->[1]}
    sort {$b->[0] <=> $a->[0]}
    map {[length($_), $_]}
    @array;

print Dumper(\@array);

[download]
outputs: 
$VAR1 = [
          'one|two|three|four',
          'two|three|four',
          'one|three|four',
          'one|two|three',
          'one|two|four',
          'three|four',
          'two|three',
          'one|three',
          'two|four',
          'one|four',
          'one|two',
          'three',
          'four',
          'two',
          'one'
        ];

[download]

--

flounder

Replies are listed 'Best First'.
Re: Re: Sort Array by length of Value
by Roger (Parson) on Oct 07, 2003 at 03:54 UTC
    Out of interest, I have constructed the following test to compare the performance of various solutions:

    use strict;
use Benchmark qw(timethese cmpthese);

my @array = (
    'four',
    'three',
    'three|four',
    'two',
    'two|four',
    'two|three',
    'two|three|four',
    'one',
    'one|four',
    'one|three',
    'one|three|four',
    'one|two',
    'one|two|four',
    'one|two|three',
    'one|two|three|four'
);

timethese(  10000,
            {'Schwartzian' => '&Schwartzian()',
             'Orcish'      => '&Orcish()',
             'Direct Sort' => '&DirectSort()',
            }
        );

cmpthese(  10000,
            {'Schwartzian' => '&Schwartzian()',
             'Orcish'      => '&Orcish()',
             'Direct Sort' => '&DirectSort()',
            }
        );

sub Schwartzian()
{
    my @sorted_array = map {$_->[1]}
                       sort {$b->[0] <=> $a->[0]}
                       map {[length($_), $_]} @array;
}

sub Orcish()
{
    my %m;
    my @sorted_array = sort {
        ($m{$b} ||= length($b)) <=> ($m{$a} ||= length($a))
    } @array;
}

sub DirectSort()
{
    my @sorted_array = sort {length $b <=> length $a} @array;
}

    [download]
    And the result is as follows on a 1.8GHz Pentium 4:

    Benchmark: timing 100000 iterations of Direct Sort, Orcish, Schwartzia
+n...
Direct Sort:  4 wallclock secs ( 4.00 usr +  0.02 sys =  4.02 CPU) @ 2
+4900.40/s
    Orcish: 10 wallclock secs ( 9.47 usr +  0.00 sys =  9.47 CPU) @ 10
+560.78/s
Schwartzian: 13 wallclock secs (13.77 usr +  0.00 sys = 13.77 CPU) @ 7
+264.80/s
               Rate Schwartzian      Orcish      Direct Sort
Schwartzian  7272/s          --        -31%        -71%
Orcish      10561/s         45%          --        -58%
Direct Sort 24907/s        242%        136%          --

    [download]
    It turns out that the Schwartzian sort is the slowest of all. (The Orcish Maneuver was put in out of curiosity to see how expensive is the length function.)

    From the result I have deduced a couple of interesting results:

    1) Orcish Maneuver is useless unless on expensive operations, where the operation takes significantly longer time than the hash table insert and lookup.

    2) Schwartzian Transformation on a simple array is an expensive operation.

    3) Simplest sort is the best for very fast functions in the comparison, such as length.

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom