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?