 "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?