"be consistent" PerlMonks

### Re: Finding the max()/min()

by elusion (Curate)
 on Nov 11, 2004 at 02:48 UTC ( #406887=note: print w/replies, xml ) Need Help??

in reply to Finding the max()/min()

What I really like is writing generic min/max routines that handle more than two variables. They show the beauty of recursive functions, even though Perl doesn't handle tail-recursion1.

Iterative:

```sub max {
my (\$max, @vars) = @_;
for (@vars) {
\$max = \$_ if \$_ > \$max;
}
return \$max;
}
Recursive:
```sub max {
my (\$max, \$next, @vars) = @_;
return \$max if not \$next;
return max( \$max > \$next ? \$max : \$next, @vars );
}
Interestingly enough, though this example works well in several languages, Perl's iterative version is remarkably short; I've never noticed this before. I guess I just proved myself wrong.
1Okay, so this isn't strictly true. Using a magic goto with the & sigil and @_, you can fake it. But it's not very pretty.

Update: Fixed my mistake. Thanks, pg. (I always want to use postmodifier if and for in the same statement.) Update: Okay, so I should test my code before I post. Or find where I left my brain. Snippet 2 is fixed.

Replies are listed 'Best First'.
Re^2: Finding the max()/min()
by itub (Priest) on Nov 11, 2004 at 04:32 UTC
Perhaps this will count as "cheating" for the purpose of this thread, but I just do this to find the min/max of a list

```use List::Util qw(min max);
\$min = min @list;
\$max = max @list;
;-)

A moderate annoyance of List::Util::m(in|ax) is that they dont operate on tied values or situations where there is some form of indirection involved (like finding the key whose value in a hash is the lowest). Then List::Util::reduce() is your friend:

```\$min = reduce { (\$a,\$b)[\$a < \$b] } @list;
\$min_key = reduce { (\$a,\$b)[\$x{\$a} < \$x{\$b}] } keys %x;

Working out max is left as an exercise :-)

---
demerphq

Re^2: Finding the max()/min() (stmt modifier form)
by demerphq (Chancellor) on Nov 11, 2004 at 10:47 UTC
```sub max {
my \$max=shift;
\$max < \$_ and \$max = \$_
for @vars;
return \$max;
}

Is marginally shorted and probably faster, but commits what some would call the crime of logic based control flow.

---
demerphq

Re^2: Finding the max()/min()
by pg (Canon) on Nov 11, 2004 at 02:52 UTC

Update:

Per elusion's update, he has already fixed both solutions.

============

Your solution one does not compile.

Your solution two does not work, and it does not print anything:

```use strict;
use warnings;

print max(1.23,2.6,55.1,4,5);

sub max {
my (\$max, \$next, @vars) = @_;
return if not \$next;
return max( \$max > \$next ? \$max : \$next, @vars );
}
Re^2: Finding the max()/min()
by sleepingsquirrel (Hermit) on Nov 11, 2004 at 19:47 UTC
Your recursive version of max is broken for lists like (-1,0,1,2) and (-1,undef,1,2). i.e. the code assumes it is at the end of the list whenever \$next==0 or \$next==undef (which isn't true in general). Here's a snazzy (if not the most efficient) recursive version with a hat tip to Zaxo...
```sub max {
my (\$x, @xs) = @_;
@xs ? (\$x, max(@xs))[\$x < max(@xs)] : \$x
}

-- All code is 100% tested and functional unless otherwise noted.
Your solution is calling max(@xs) twice each step. This leads to O(2^n) growth for what should be an O(n) problem. Modifying it slightly to call max once and save the value in a temp variable should save considerable time on long lists.
```sub max {
my (\$x, @xs) = @_;
@xs ? do { my \$m = maxdo(@xs); (\$x, \$m)[\$x < \$m] } : \$x;
}
Re^2: Finding the max()/min()
by Aristotle (Chancellor) on Dec 18, 2004 at 02:15 UTC

Here's another recursive form:

```sub max {
my( \$i, @l ) = @_;
my \$j = @l ? max( @l ) : \$i;
return \$i > \$j ? \$i : \$j;
}

And for that matter, an iterative form:

```sub max {
\$_[ 0 ] < \$_[ -1 ] ? shift : pop while @_ > 1;
return @_;
}

Makeshifts last the longest.

It's normally best to end recursive solutions with the recursive call. That allows the compiler to use tail-recursion to speed up the solution.

Of course, in Perl you need to jump through a few hoops to do use tail-recursion, so I mentioned but didn't include it in my original node. But with a bit if tinkering you can use it, and here it is now:

```sub max {
my \$max  = shift;
my \$next = shift;
return \$max if not \$next;
unshift @_, \$max > \$next ? \$max : \$next;
goto &max;
}
Which I estimate to be about 10x faster on a random 5000 element list. (Exact benchmarks are left to the reader as an exercise :-).

I wonder if Ponie (Perl 5 On New Internals Engine) will be able to detect and use tail-recursion.

There's a bug in that code, try finding the max of this list...
```@a = (1,0,3,2);

-- All code is 100% tested and functional unless otherwise noted.

That's all well and nice, but my goal was to use an approach which directly generalizes from the specific case of a two element list. As you'll also notice I used the value returned from the recursive call twice, it's both kind of difficult and beside the point to work on tail recursion here. Noone in their right mind writes a recursive max() outside a functional language anyway, and in a pure functional language I'd just write max( @l ) twice and let the compiler/VM figure out that the result need only be calculated once.

In any case, your new approach is just a variation on what was already posted in the parent node — no need for repetition…

Makeshifts last the longest.

Create A New User
Node Status?
node history
Node Type: note [id://406887]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (6)
As of 2019-10-19 19:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2019 the site I miss most is:

Results (47 votes). Check out past polls.

Notices?