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]

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.

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.

I understand your point, but it is still a comparison, and it costs just as much as the other comparisons, and if other algorithms don't require that extra comparison (in the while loop), it has to count against the overall algorithm costs.

If you re-coded that part of your algorithm to be

# while( $i < @{ $ref } ) {
  for my $i ( 0 .. $#$ref ) {
[download]

Then you would avoid that comparison.

Or rather, the comparison still exists, the loop has to be terminated somehow (as is true of the other algorithms), but the comparison is being made at the C/assembler level rather than the Perl level. The difference is that perfroming the comparison at the Perl level requires a lot of extra processing to extract the values from Perl variables and getting them into appropriate registers for the comparison to be made, whereas doing at the C-level, the values are probably in registers already, or can be more cheaply loaded from local stack temporaries.

Efficiency in Perl is nearly always about allowing or pursuading Perl to do as much of the work as possible, which generally means using as few opcodes as possible.

For your algorithm to be beneficial, you would really need to code it in C, XS or maybe even assember. Comparisons are simply too cheap relative to memory accesses and stack manipulations for the 25% reduction in comparisons to be significant if achieving requires even a moderate increase of either.

---

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.

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.

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.

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