The problem with Max

Is, of course, the recursive call on line 2:
 
   Max[{x_, xs___}] := x if x > Max[{xs}];
 
While mathematically correct, it will cause recalculation over the tail, xs, for each element of the list, transforming a trivial linear algorithm into a quadratic. The solution, as usual, is to introduce another formal argument:
 
   Max[l_] := MaxHelper[l, -Infinity];
   MaxHelper[{}, a] := a;
   MaxHelper[{x_, xs___}, a] := MaxHelper[{xs}, x] if x > a;
   MaxHelper[{x_, xs___}, a] := MaxHelper[{xs}, a] otherwise;
 
Advertisements

~ by rebcabin on June 23, 2008.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: