Re^3: Sort undef

The Wikipedia author is being polite.

Doing it the 1960s way:

@sorted = sort { foo($a) cmp foo($b) } @unsorted;
[download]

Doing it the 1990s way^*:

@sorted = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map  { [$_, foo($_)] }
               @unsorted;
[download]

The author then gently chastises the older approach:

While it is shorter to code, the naive approach here could be much less efficient if the key function (called foo in the example above) is expensive to compute.

The explanation on the Wikipedia page is also pretty straightforward. This should probably be considered a core Perl technique within the profession; that is to say, while not knowing about the Schwartzian Transform is no crime, it is a tragedy compelling immediate correction for anyone in the business, should the topic come up. The efficiency gains, when applied to appropriate circumstances, are too great to ignore. Perl programmers should learn not only the technique, but why it is better so they are empowered to better choose when to use it.

^*We've put people on the Moon in the meantime, so forward progress is not only permissible, but recommended.

Comment on Re^3: Sort undef Select or Download Code

Replies are listed 'Best First'.

Re^4: Sort undef
by marioroy (Prior) on Jun 13, 2017 at 07:02 UTC

Update: Added undef's to the list to imitate the OP's request regarding undef's. After sorting, move any undef's from the start of the list to the end.

The following is a fun exercise if wanting to simulate work inside the foo function.

Thank you, Randal L. Schwartz for the Schwartzian transform technique.

use strict;
use warnings;

# http://www.perlmonks.org/?node_id=1192544

use List::Util 'shuffle';
use Time::HiRes 'time';

sub foo { sleep 0; $_[0] }

srand 0;

my @unsorted = shuffle ( 'aaaa'..'zzzz', (undef) x 7 );

printf "Number of elements to sort    : %d\n",
  scalar @unsorted;

{
  no warnings 'uninitialized';

  my $start  = time;
  my @sorted = sort { foo($a) cmp foo($b) } @unsorted;

  # move any undef's from the start of the list to the end
  my $i = 0; $i++ until ( defined $sorted[$i] );
  push @sorted, splice(@sorted, 0, $i) if $i;

  printf "Without Schwartzian transform : %6.3f seconds\n",
    time - $start;
}

{
  no warnings 'uninitialized';

  my $start  = time;
  my @sorted = map  { $_->[0] }
               sort { $a->[1] cmp $b->[1] }
               map  { [ $_, foo($_) ] } @unsorted;

  # move any undef's from the start of the list to the end
  my $i = 0; $i++ until ( defined $sorted[$i] );
  push @sorted, splice(@sorted, 0, $i) if $i;

  printf "With ++ Schwartzian transform : %6.3f seconds\n",
    time - $start;
}

__END__

Number of elements to sort    : 456983
Without Schwartzian transform : 24.939 seconds
With ++ Schwartzian transform :  2.832 seconds
[download]

Perl is fun. I'm always learning and had no idea the speed gain possible with the Schwartzian transform until now. I also tried without sleep 0 inside foo to better understand the overhead imposed by method calling. The Schwartzian transform is still faster. Wow!

sub foo { $_[0] }

Number of elements to sort    : 456983
Without Schwartzian transform :  4.680 seconds
With ++ Schwartzian transform :  2.053 seconds
[download]

Regards, Mario

[reply]
[d/l]
[select]


XP is just a number
	PerlMonks