Services & ResourcesWolfram ForumsMathGroup Archive

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

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>