This is not really a comparison of the algorithm, but of how to write effective Perl. The algorithm is trying to reduce the number of comparisons from 2 per element to 3 per 2 elements. However, your code differs from the OP in a couple key ways that improve the efficiency. First, the OP dereferences the array pointer for each element access. Second, the OP winds up copying elements into temporary variables to work two at a time, whereas your code uses the nice aliasing behavior of for to avoid having to create new variables. In Perl the overhead of the extra comparisons are minor relative to the cost of creating new temporary variables.

He also isn't saving as many comparisons as he thinks.

I've added some counts to the following version of his implementation of the algorithm and where using three passes on 100 elements you would expect 200 comparisions, his code does 198--for a saving of just 2--, but he also does 302 dereferences (which admitedly is traded for allocating stack space for the arg list) and a mod operation.

Maybe the algorithm can be implemented more economically, but quite where the saving comes in escapes me.

#! perl -slw
use strict;

my( $comps, $mods, $derefs ) = (0)x3;

sub min_max_avg {
    my $ref = shift;
    my ( $min, $max, $agv, $i );
    my ( $current_min, $current_max );
    $comps++; $derefs++; $mods++;
    if ( @{$ref} % 2 == 0 ) {
        $comps++; $derefs +=4;
        ( $min, $max ) =
          $ref->[0] < $ref->[1]
          ? ( $ref->[0], $ref->[1] )
          : ( $ref->[1], $ref->[0] );
        $derefs += 2;
        $agv = $ref->[0] + $ref->[1];
        $i   = 2;
    }
    else {
        $derefs++;
        $min = $max = $agv = $ref->[0];
        $i = 1;
    }
    while ( $i < @{$ref} and ++$comps ) {
        $comps++; $derefs += 4;
        ( $current_min, $current_max ) =
          $ref->[$i] < $ref->[ $i + 1 ]
          ? ( $ref->[$i], $ref->[ $i + 1 ] )
          : ( $ref->[ $i + 1 ], $ref->[$i] );
        $comps++;
        $min = $current_min if ( $current_min < $min );
        $comps++;
        $max = $current_max if ( $current_max > $max );
        $derefs += 2;
        $agv += $ref->[$i] + $ref->[ $i + 1 ];
        $i   += 2;
    }
    $derefs++;
    return ( $min, $max, $agv / @{$ref} );
}


my( $min, $max, $ave ) = min_max_avg [ 1 .. 100 ];;

print "$min $max $ave";

print "comps:$comps derefs: $derefs mods: $mods";
[download]

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

thank you BrowserUk your replies are all very helpful for me, especially about testing the input parameter. Only a little disappointment... regarding the number of comparisons i believe that your code doesn't agree with my way of counting comparisons only why it counts also the comparisons in the while condition, the number 3(n/2) refers to comparisons among elements of the input list.

This is not really a comparison of the algorithm, but of how to write effective Perl. The algorithm is trying to reduce the number of comparisons from 2 per element to 3 per 2 elements.

right, but my point is that trying to minimimize the number of comparisons in order to find the best algorithm is senseless when programing in perl where other operations like assignement or branching are equally (or more) expensive.

Actually, I doubt that even when implemented in assembler or C this algorithm is faster than the simple one in all the moderm processors where comparisons are not specially expensive.

Thank you xdg, you found some sense for my benchmark! It does not suffer for all the optimisations salva cleverly used - which shows that sometimes a worse coder can do a cleaner work :)

Flavio
perl -ple'$_=reverse' <<<ti.xittelop@oivalf

Don't fool yourself.

thank you xdg, your reply helps me to understand what is the problem of my approach...

I've taken a cut at trying to get as perlish as possible with algorithm, eliminating as much overhead as I could quickly think of (and keeping similar approaches on dereferencing, etc.). The simple approach is still faster in pure perl -- doing the array overhead manually with splice versus using for still swamps the comparision savings.

Read more... (2 kB)

            Rate algorithm    simple
algorithm 1517/s        --      -30%
simple    2177/s       44%        --
[download]

-xdg

Code written by xdg and posted on PerlMonks is public domain. It is provided as is with no warranties, express or implied, of any kind. Posted code may not have been tested. Use of posted code is at your own risk.

#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw( cmpthese );

my @array = map { int rand 100 } 1 .. 1_000_000;
cmpthese -10, {
   op => sub {
      my ($min, $max, $avg) = min_max_avg(\@array);
   },
   simple => sub {
      my ($min, $max, $avg) = min_max_avg_simple(\@array);
   },
};

sub min_max_avg_simple {
   my $ref = shift;
   
   my $n_elements = scalar @$ref;
   return unless $n_elements > 0;
   
   my ( $min, $max, $sum ) = ($ref->[0]) x 3;
   my $i = 1; # Start from next element
   while ($i < $n_elements) {
      my $value = $ref->[$i];
      if ($value < $min)
         { $min = $value }
      elsif ($value > $max)
         { $max = $value }
      $sum += $value;
      ++$i;
   }
   return ( $min, $max, $sum / $n_elements );
}

sub min_max_avg {
    my $ref = shift;
    my ( $min, $max, $agv, $i );
    my ( $current_min, $current_max );
    if ( @{$ref} % 2 == 0 ) {
        ( $min, $max ) =
          $ref->[0] < $ref->[1]
          ? ( $ref->[0], $ref->[1] )
          : ( $ref->[1], $ref->[0] );
        $agv = $ref->[0] + $ref->[1];
        $i   = 2;
    }
    else {
        $min = $max = $agv = $ref->[0];
        $i = 1;
    }
    while ( $i < @{$ref} ) {
        ( $current_min, $current_max ) =
          $ref->[$i] < $ref->[ $i + 1 ]
          ? ( $ref->[$i], $ref->[ $i + 1 ] )
          : ( $ref->[ $i + 1 ], $ref->[$i] );
        $min = $current_min if ( $current_min < $min );
        $max = $current_max if ( $current_max > $max );
        $agv += $ref->[$i] + $ref->[ $i + 1 ];
        $i   += 2;
    }
    return ( $min, $max, $agv / @{$ref} );
}

__END__

       s/iter     op simple
op       1.13     --   -37%
simple  0.707    60%     --
[download]