Re^2: minimum, maximum and average of a list of numbers at the same time
by davorg (Chancellor) on Nov 10, 2005 at 12:21 UTC

It does look temptingly simple doesn't it?
But you'd be iterating across the list three times  which isn't very efficient. You only really need to iterate across it once. Something like this (off the top of my head and untested).
# use 'mean' instead of 'avg' as it's unambiguous
sub min_max_mean {
my ($min, $max, $tot);
my $count = @_;
$min = $max = $tot = shift;
foreach (@_) {
$min = $_ if $_ < $min;
$max = $_ if $_ > $max;
$tot += $_;
}
return ($min, $max, $tot / $count);
}

< http://dave.org.uk>
"The first rule of Perl club is you do not talk about
Perl club."  Chip Salzenberg
 [reply] [d/l] 

Reducing the number of iterations or comparisons by a constant number may make a performance difference, depending on what gyrations you have to go through to make the reduction, but you're not changing the order of complexity. A 3N solution is the same order as a 3/2N solution, is the same as a singlepass (N) solution. They're all O(n). This is an important concept.
If you can reduce the order of a solution, your solution will scale better. We commonly look for O(n log n) solutions to replace O(n^{2}) solutions, so that working with large amounts of data doesn't make our app bog down. If you merely change by a constant factor (as we're talking about in this case), you may see a constantfactor improvement at any size, but you won't alleviate any scaling problems. You're in the realm of microoptimization.
Walking through the list is not going to be a significant portion of the computation, compared to the comparisons and math being done on the variables of interest. And it's really not worth trying to take the elements two at a time, because that ends up being a very inefficient way to walk through the list, compared to Perl's builtin for.
If our OP were to translate the algorithm into Inline::C, the reduced number of comparisons might compete well with three List::Util calls, with the difference being some constant factor on any size list.
Caution: Contents may have been coded under pressure.
 [reply] [d/l] 
Re^2: minimum, maximum and average of a list of numbers at the same time
by demerphq (Chancellor) on Nov 10, 2005 at 12:16 UTC

use List::Util qw/ reduce /;
sub min_max_avg {
$res= reduce {
my $r= ref $a ? $a : [($a) x 3];
if ($b < $r>[0]) {
$r>[0]= $b;
} elsif ($b > $r>[1]) {
$r>[1]= $b;
}
$r>[2]+=$b;
$r
} @_;
return @$res[0,1], $res>[2] / @_;
}

$world=~s/war/peace/g
 [reply] [d/l] 

And if you want to go even more FP...
sub Gen_Stats {
my $stat = {};
my ($cnt, $max, $min, $tot);
$stat>{ADD} = sub {
$cnt += @_;
for ( @_ ) {
$tot += $_;
$max = $_ if ! defined $max  $_ > $max;
$min = $_ if ! defined $min  $_ < $min;
}
};
$stat>{MAX} = sub { $max };
$stat>{MIN} = sub { $min };
$stat>{AVE} = sub { $cnt ? $tot / $cnt : undef };
$stat>{TOT} = sub { $tot };
$stat>{ADD}>( @_ );
return $stat;
}
my $stat_info = Gen_Stats();
while ( <DATA> ) {
chomp;
$stat_info>{ADD}($_);
}
print join "\t", map { $_>() } @{$stat_info}{qw/MAX MIN AVE TOT/};
This code was borrowed from RFC: Tool::Box. I recommend using List::Util when and wherever possible. It has been part of the core since 5.007003 and uses XS when possible. The only real limitation I see with it is that all the items in the list must be known at once as I pointed out in How A Function Becomes Higher Order.
 [reply] [d/l] 

Nice fast code, but does it return the right values?
I checked with the orig mma routine, the my_mma routine and your reduce_mma routine. Using the same set of @nums, the results differ.
use Benchmark qw(:all :hireswallclock);
my @nums = map {rand} 1 .. 10000;
my $subs = {
mma => sub { my @r = min_max_avg(\@nums) },
reduce_mma => sub { my @r = reduce_mma(\@nums) },
mymma => sub { my @r = my_mma(\@nums) }
};
cmpthese(1, $subs);
$count = 1000;
for my $sub (keys %$subs){
$t = timeit($count, $subs>{$sub});
print "$count loops of $sub:",timestr($t),"\n";
}
for my $sub (keys %$subs){
print "$sub results:\n";
print (join ' ', &{$subs>{$sub}} , "\n");
}
##### Subs to test ######
__END__
$ perl benchmark.pl
Rate mma mymma reduce_mma
mma 86.3/s  49% 100%
mymma 171/s 98%  100%
reduce_mma 89229/s 103265% 52110% 
1000 loops of reduce_mma:0.0114148 wallclock secs ( 0.00 usr + 0.00 s
+ys = 0.00 CPU)
1000 loops of mma:12.0897 wallclock secs (12.05 usr + 0.01 sys = 12.0
+6 CPU) @ 82.91/s (n=1000)
1000 loops of mymma:5.98583 wallclock secs ( 5.97 usr + 0.00 sys = 5
+.97 CPU) @ 167.56/s (n=1000)
reduce_mma results:
0.956444677504809 0.209810070551129 0.765697545177442
mma results:
0.000119859684559742 0.999992750475673 0.505291691541093
mymma results:
0.000119859684559742 0.999992750475673 0.505291691541093
 [reply] [d/l] 

I can't replicate your results and you dont show the code you are using. I do recall that when i first posted my solution I had a mistake in the code, which I updated shortly afterwards. (Soon enough that i didnt bother with noting the update  my bad i guess.) So if you downloaded that then yes, it isnt giving the correct results. But if you use the code that is in the thread now it should.

$world=~s/war/peace/g
 [reply] 
Re^2: minimum, maximum and average of a list of numbers at the same time
by LucaPette (Friar) on Nov 10, 2005 at 12:20 UTC

I'm not a perl expert... infact i'm not able to really understand the code of List::Util maybe you can clarify to me about this question: Do your code process three times the input list?  [reply] 

But you're not required to understand it. But then of course without even having seen it I'm sure it does process it three times. If that is really relevant, then indeed you may want or have to process it once yourself. And if it is very relevant, perhaps you may want to do it as a binary extension.
Well, the author may consider a adding to List::Util a function to calculate more than one relevant quantity at a time, e.g.
my ($min, $max, $sum) = calculate [qw/min max sum/], @list;
or perhaps with an OO interface:
my $stats=List::Util>calculate([qw/min max sum/])>of(@list);
print $stats>min, "\n";
possibly even with a mixed interface:
calculate [qw/min max sum/], @list;
print List::Util::lastrun>max, "\n";
 [reply] [d/l] [select] 

Do your code process three times the input list?
Indeed it does and as davorg and demerphq have pointed out in their replies it isn't terribly efficient, but that's a "perlish" solution for you.
 [reply] 
Re^2: minimum, maximum and average of a list of numbers at the same time
by bbacker (Initiate) on Nov 10, 2005 at 23:11 UTC

I don't know what the programmatic performance would be, but using
Statistics::Descriptive
would certainly cut the amount of time you, the human,
had to spend on this problem.  [reply] 