Re: Re: OOP experiments in Mathematica- The Stack
- To: mathgroup at smc.vnet.net
- Subject: [mg38688] Re: [mg38682] Re: OOP experiments in Mathematica- The Stack
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Sun, 5 Jan 2003 06:33:51 -0500 (EST)
- References: <av374s$g0t$1@smc.vnet.net> <200301041227.HAA24547@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
>A series of OOP experiments in Mathematica. >msg#2 - The Stack, part#6: Timing. > >Thanks to Daniel Lichtblau at Wolfram for pointing out that using either >Append or Prepend results in Order^2 timing. >(n-squared: pushing ten times as many items would take one hundred >times as long). You are welcome. >He suggested using nested lists. > >That is, {a, {b, {c} } } or { { {a}, b}, c}. Yes. I actually meant "Use List" (literally, rather than e.g. STACK) for exactly the reason you uncover below. But your work-around is also fine. >Details: >I wrote a new STACK implementation, using nested lists: > push[ s, x ]:= STACK[x, s] > >I am using a head of "STACK", so my stack structure looked like >this (after 3 pushes): >STACK[ a, STACK[ b, STACK[ c, STACK[] ] ] ] > >Result: >The program hardly sped up at all. :-( > >Reason: >*** nesting "heads that are undefined symbols" >slows Mathematica down to about Order^1.5 >on this simple nesting of lists!!! Actually O(n^2), I suspect. This phenomenon is discussed to some extent at http://forums.wolfram.com/mathgroup/archive/2002/Sep/msg00324.html >- - - - - >Solution: > >STACK="stack"; > >Result: >Instantly, the nested list solution zoomed up in speed. Indeed, it is now >Order^1 (linear). > >The timing test ("timing2" is defined below the "-----"): > timing2[ (sa=new[];Do[sa = push[sa,i], {i,#}])&,100000 ] >Output: >{iters[100000,200000], > times[0.601 Second,1.192 Second], > ratios[2,1.98336], >Order^0.987947} This is fine. One potential advantage to using List as your head is that it tends to be faster when one wants to convert to a vector using Flatten. For your purposes this is may actually be a disadvantage because you want to impose strict stack functionality, and that does not allow for such a conversion. Daniel Lichtblau Wolfram Research
- References:
- Re: OOP experiments in Mathematica- The Stack
- From: "Steve S. Shaw" <steve@shawstudio.com>
- Re: OOP experiments in Mathematica- The Stack