Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2006
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

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?


  • Prev by Date: plot questions
  • Next by Date: Re: Performance comparison Mac OSX vs. Windows XP
  • Previous by thread: plot questions
  • Next by thread: a summary of MathML use cases that don't work with Mathematica (stuff WRI should fix for the next go-round)