Re^2: minimum, maximum and average of a list of numbers at the same time

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);
}
[download]

--
<http://dave.org.uk>

"The first rule of Perl club is you do not talk about Perl club."
-- Chip Salzenberg

Comment on Re^2: minimum, maximum and average of a list of numbers at the same time Download Code

Replies are listed 'Best First'.
Re^3: minimum, maximum and average of a list of numbers at the same time by Roy Johnson (Monsignor) on Nov 10, 2005 at 21:08 UTC
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 3-N solution is the same order as a 3/2-N solution, is the same as a single-pass (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²) 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 constant-factor improvement at any size, but you won't alleviate any scaling problems. You're in the realm of micro-optimization. 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 built-in `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]

Replies are listed 'Best First'.

Re^3: minimum, maximum and average of a list of numbers at the same time
by Roy Johnson (Monsignor) on Nov 10, 2005 at 21:08 UTC

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²) 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 constant-factor improvement at any size, but you won't alleviate any scaling problems. You're in the realm of micro-optimization.

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 built-in 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]