maxima function
- To: mathgroup at smc.vnet.net
- Subject: [mg69981] maxima function
- From: dimmechan at yahoo.com
- Date: Thu, 28 Sep 2006 06:17:47 -0400 (EDT)
I know this old and classic one (since 1992 and a Mathematica
programming competition question as I read!) but your answers
will help me to get more insight of how pattern matching works.
Anyway let me consider the problem of finding a function which starts
with a list of numbers and returns the sublist of the numbers bigger
than all previous ones frrom the given list.
Here is one alternative using pattern matching
maxima1[(lis_)?ListQ] := lis //. {a___, x_, y_, c___} /; OrderedQ[{y,
x}] :> {a, x, c}
and here is another using functional programming
maxima2[(lis_)?ListQ] := Union[Rest[FoldList[Max[#1, #2] & , 0, lis]]]
The difference in times is considerable for big lists
dat = Table[Random[Integer, {0, 9}], {10000}];
Timing[maxima1[dat]][[1]]
2.3899999999999997*Second
Timing[maxima2[dat]][[1]]
0.016000000000000014*Second
Executing the following commands
Trace[maxima1[lst], OrderedQ]
Trace[maxima2[lst], Max]
I get an idea of why maxima1 is much slower. The pattern matched
function
is slowly because it applies repeatedly transformation rules.
Short[Trace[maxima1[lst], OrderedQ], 2]
{{OrderedQ[{7,4}],False},{OrderedQ[{
5,7}],True},{OrderedQ[{7,4}],False},{OrderedQ[{
2,7}],True},\[LeftSkeleton]4\[RightSkeleton],{
OrderedQ[{1,9}],True},{OrderedQ[{7,4}],False},{OrderedQ[{9,7}],False}}
Is it a way to modify maxima1 so that to avoid the appearance of e.g.
OrderedQ[{7,4}]
again and again which is the reason for the more needing time?