Re: OOP experiments in Mathematica- The Stack
- To: mathgroup at smc.vnet.net
- Subject: [mg38682] Re: OOP experiments in Mathematica- The Stack
- From: "Steve S. Shaw" <steve at shawstudio.com>
- Date: Sat, 4 Jan 2003 07:27:26 -0500 (EST)
- References: <av374s$g0t$1@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).
He suggested using nested lists.
That is, {a, {b, {c} } } or { { {a}, b}, c}.
I had thought Append would give me an internal structure like this - but I
was thinking of Lisp "cons" - I did not understand that Mathematica was
storing in an array, so it kept having to copy my longer and longer arrays.
---------------------------------------------------------------------------
Discussion: I am not yet talking about "OO"; rather I am poking at the
fundamentals of "how to design software well".
The point here is the use of "abstraction":
the implementation of "stack"
SHOULD NOT EXPOSE TO A CLIENT THE INTERNAL STRUCTURE OF THE STACK.
Because I only "touched" my stacks using the carefully-designed functions
(new, isEmpty, top, push, drop), I can now change the implementation freely.
In this case, to get better performance.
This is the essence of a "Type" -
whether an OO type with inheritance,
or a simple custom type such as my "STACK",
or simply a pre-defined "Type" such as "Integer".
NOTE: Since Mathematica doesn't "protect me", if I had been using my first
implementation of stack for a long time, I could well have written
substantial code that relied on that returned stack structure.
That is, since my stack was a simple array, I might have used array
operations to get at elements in the stack.
For example, at some random place in some random project,
I might write an operator that added the top two items on the stack.
If I "knew" those were the first two items in an array, I might, without
thinking about it, do
s[[1]] + s[[2]
But that "shortcut" would suddenly break, if the stack implementation were
changed. Therefore, I would never dare change the stack implementation.
Then along comes someone who observes that my stack logic is very slow for
large stacks. Uh-oh.
In the "undisciplined" programming style possible (and probable) in
Mathematica, I wouldn't have a clue what I might break if I tinkered with my
stack implementation.
My goal is code that is easily UNDERSTOOD, and easily CHANGED.
I am even willing to put *reasonable* extra effort into writing the code in
the first place, to achieve that goal.
Ever tried to READ a large program written by someone else (except for the
rare person who methodically organizes and thoroughly documents what they
have done)?
Yuk.
So, let's explore ways to be more "disciplined" in Mathematica.
This is more important to me than that the solution be "OO".
But the solutions I know revolve around notions of "Type" and "Contract".
---------------------------------------------------------------------------
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!!!
- - - - -
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}
100,000 pushes after the change took about as long as 2,000 pushes before
the change!
Caution: if try this timing test with STACK undefined,
use a much smaller number of iterations, such as "2000".
Some timing tests:
---------------------------------------------------------------------------
(* TIMING utility *)
timing2[ func_,iter1_,iterRatio_ ]:=
Module[ {iter2,time1,time2,timeRatio},
iter2=iter1*iterRatio;
time1=Timing[ func[ iter1 ] ][[ 1 ]];
If[ (time1/Second)<0.0001 ,
"*** Increase iterations"//Print,
(time2=Timing[ func[ iter2 ] ][[ 1 ]];
timeRatio=time2/time1;
{"iters"[iter1,iter2],"times"[time1,time2],"ratios"
[iterRatio,timeRatio],
"Order^"<>ToString[ Log[ timeRatio ] /Log[ iterRatio ] ]}
)
]
]
timing2[ func_,iter1_ ]:=timing2[ func,iter1,2 ]
In[4]:=
timing2[ (sa={};Do[sa = {sa,i}, {i,#}])&,200000 ]
Out[4]={iters[200000,400000],times[0.491 Second,1.101 Second],
ratios[2,2.24236],Order^1.16502}
In[5]:=
timing2[ (sa={};Do[sa = {i,sa}, {i,#}])&,200000 ]
Out[5]= {iters[200000,400000],times[0.651 Second,1.072 Second],
ratios[2,1.6467],Order^0.719575}
In[6]:=
timing2[ (sa={};Do[sa = Prepend[ sa,i ], {i,#}])&,3000 ]
Out[6]= {iters[3000,6000],times[0.46 Second,1.583 Second],
ratios[2,3.4413],Order^1.78296}
In[7]:=
timing2[ (sa={};Do[sa = Append[ sa,i ], {i,#}])&,3000 ]
Out[7]= {iters[3000,6000],times[0.32 Second,1.522 Second],
ratios[2,4.75625],Order^2.24982}
In[8]:=
Clear[ STACK ];
timing2[ (sa=STACK[];Do[sa = STACK[sa,i], {i,#}])&,2000 ]
Out[9]= {iters[2000,4000],times[0.211 Second,0.981 Second],
ratios[2,4.64929],Order^2.21701}
In[10]:=
STACK="stack";
In[11]:=
timing2[ (sa=STACK[];Do[sa = STACK[sa,i], {i,#}])&,100000 ]
Out[11]= {iters[100000,200000],times[0.28 Second,0.591 Second],
ratios[2,2.11071],Order^1.07773}
In[12]:=
timing2[ (sa=STACK[];Do[sa = STACK[i,sa], {i,#}])&,100000 ]
Out[12]= {iters[100000,200000],times[0.391 Second,0.611 Second],
ratios[2,1.56266],Order^0.644004}
---------------------------------------------------------------------------
Revised stack notebook:
---------------------------------------------------------------------------
Notebook[{
Cell[BoxData[
\(\(\( (*\
Quiet\ the\ warnings\ about\ similarly\ spelled\ \
\(\(variables\)\(.\)\)\ *) \)\(\n\)\(Off[General::spell]; \ \ \ Off[
General::spell1];\)\)\)], "Input"],
Cell[BoxData[
\(\(\( (*\
TIMING\ utility\ *) \)\(\[IndentingNewLine]\)\(\
\[IndentingNewLine]\)\(timing2[\ func_, iter1_,
iterRatio_\ ] := \[IndentingNewLine]Module[\ {iter2, time1,
time2, timeRatio}, \[IndentingNewLine]iter2 =
iter1*iterRatio; \[IndentingNewLine]time1 = \(Timing[\
func[\ iter1\ ]\ ]\)[\([\
1\ ]\)]; \[IndentingNewLine]If[\ \((time1/Second)\) <
0.0001\ , \[IndentingNewLine]"\<*** Increase \
iterations\>" //
Print, \[IndentingNewLine]\((time2 = \(Timing[\
func[\ iter2\ ]\ ]\)[\([\
1\ ]\)]; \[IndentingNewLine]timeRatio =
time2/time1; \[IndentingNewLine]{"\<iters\>"[iter1,
iter2], "\<times\>"[time1,
time2], "\<ratios\>"\[IndentingNewLine][iterRatio,
timeRatio], "\<Order^\>" <>
ToString[\
Log[\ timeRatio\ ]\ /
Log[\ iterRatio\ ]\ ]}\[IndentingNewLine])\)\
\[IndentingNewLine]]\[IndentingNewLine]]\[IndentingNewLine]\
\[IndentingNewLine]
timing2[\ func_, iter1_\ ] :=
timing2[\ func, iter1, 2\ ]\)\)\)], "Input"],
Cell[BoxData[
\(\(\( (*\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\
\(===\)\(===\)\(===\)\(===\)\(===\)\(\[Equal]\)*) \)\(\
\[IndentingNewLine]\)\( (*\(--\ AXIOMS\) - \
True\ for\ all\ stacks . \ \
--*) \)\(\[IndentingNewLine]\)\(\(axiom1[] :=
empty[\ new[]\ ];\)\[IndentingNewLine]
\(axiom2[\ s_STACK, \
x_\ ] := \(! empty[\
push[\ s, \ x\ ]\ ]\);\)\[IndentingNewLine]
\(axiom3[\ s_STACK, \
x_\ ] := \((top[\ push[\ s, x\ ]\ ] ==
x)\);\)\[IndentingNewLine]
\(axiom4[\ s_STACK, \
x_\ ] := \((drop[\ push[\ s, x\ ]\ ] ==
s)\);\)\[IndentingNewLine]
\(allAxioms[\ s_STACK, \
x_\ ] := \((\[IndentingNewLine]axiom1[]\ && \
axiom2[\ s, x\ ]\ && \
axiom3[\ s, x\ ]\ && \ \ axiom4[\ s,
x\ ])\);\)\)\)\)], "Input"],
Cell[CellGroupData[{
Cell[BoxData[
\(\(\( (*\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\
\(===\)\(===\)\(===\)\(===\)\(===\)\(\[Equal]\)*) \)\(\
\[IndentingNewLine]\)\( (*\(--\
an\)\ example\ of\ stack\ \(usage\ --\)*) \)\(\
\[IndentingNewLine]\)\(\(s1 = new[];\)\[IndentingNewLine]
\(s2 =
push[\ push[\ push[\ s1, x1\ ], x2],
x3\ ];\)\[IndentingNewLine]
\(s3 = drop[\ s2\ ];\)\[IndentingNewLine]
\(s4 = new[];\)\[IndentingNewLine]
\(s5 = push[\ push[\ s4, x4\ ], x5\ ];\)\[IndentingNewLine]
\(s6 = drop[\ s5\ ];\)\[IndentingNewLine]
\(v1 = top[\ s6\ ];\)\[IndentingNewLine]
\(s7 = push[\ s3, v1\ ];\)\[IndentingNewLine]
\(s8 = push[\ s7, x6\ ];\)\[IndentingNewLine]
\(s9 = drop[\ s8\ ];\)\[IndentingNewLine]
\(s10 = push[\ s9, x7\ ];\)\[IndentingNewLine]
\(s11 = drop[\ s10\ ];\)\[IndentingNewLine]
\(result1 = top[\ s11\ ];\)\[IndentingNewLine]
result1\[IndentingNewLine] (*\
MUST\ BE\ TRUE\ for\ any\ implementation\ of\ STACK\ \
*) \[IndentingNewLine]
\(stackVerify = \((result1 \[Equal] x4)\);\)\)\)\)], "Input"],
Cell[BoxData[
\(top[
drop[push[
drop[push[
push[drop[push[push[push[new[], x1], x2], x3]],
top[drop[push[push[new[], x4], x5]]]], x6]],
x7]]]\)], "Output"]
}, Open ]],
Cell[BoxData[
\(\(\( (*\
TBD\ - \
throw\ exception?\[IndentingNewLine]Unless\ "\<test\>"\ is\ \
True, \ report\ \(\(error\)\(.\)\)\[IndentingNewLine]*) \)\(\
\[IndentingNewLine]\)\(assert[\ test_, message_\ ] :=
If[\ \(! TrueQ[\
test\ ]\), \[IndentingNewLine]"\<***Error: \>" <>
ToString[\ message\ ] // Print\ ];\)\)\)], "Input"],
Cell[BoxData[
\(\(\( (*\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\
\(===\)\(===\)\(===\)\(===\)\(===\)\(\[Equal]\)*) \)\(\
\[IndentingNewLine]\)\( (*\(--\ "\<Nested Lists\>"\)\ Implementation\ \
of\ \(Stack\ --\)*) \)\(\[IndentingNewLine]\)\(\(Clear[\ empty, \
top, \ new, \ push, \ drop, STACK\ ];\)\[IndentingNewLine]
\(STACK = "\<stack\>";\)\ (*\ when\ undefined\ symbol, \
was\ MUCH\ slower\ - \
and\ was\ Order^1.5*) \[IndentingNewLine] (*\(--\ \(Queries\ \
--\)\)*) \[IndentingNewLine]
\(empty[\
s_STACK\ ] := \((Length[\ s\ ] \[Equal]
0)\);\)\[IndentingNewLine]
\(top[\
s_STACK\ ] := \((\[IndentingNewLine]assert[\ \(! empty[\
s\ ]\), "\<stack.top- empty\>"\ ]; \
\[IndentingNewLine]First[\
s\ ]\[IndentingNewLine])\);\)\[IndentingNewLine] (*\(--\ \
\(Changes\ --\)\)*) \[IndentingNewLine]
\(new[] := STACK[];\)\[IndentingNewLine]
\(push[\ s_STACK, x_\ ] := STACK[\ x, s\ ];\)\[IndentingNewLine]
\(drop[\
s_STACK\ ] := \((\[IndentingNewLine]assert[\ \(! empty[\
s\ ]\), "\<stack.drop- empty\>"\ ]; \
\[IndentingNewLine]Last[\
s\ ]\[IndentingNewLine])\);\)\)\)\)], "Input"],
Cell[CellGroupData[{
Cell[BoxData[{
\(s1\), "\[IndentingNewLine]",
\(s2\), "\[IndentingNewLine]",
\(result1\), "\[IndentingNewLine]",
\(\(assert[\
stackVerify, "\<Bad Stack Implementation\>"\ ];\)\), "\
\[IndentingNewLine]",
\(allAxioms[\ new[], \ xx\ ]\), "\[IndentingNewLine]",
\(allAxioms[\ s1, \ xx\ ]\), "\[IndentingNewLine]",
\(allAxioms[\ s11, \ xx\ ]\)}], "Input"],
Cell[BoxData[
\("stack"[]\)], "Output"],
Cell[BoxData[
\("stack"[x3, "stack"[x2, "stack"[x1, "stack"[]]]]\)], "Output"],
Cell[BoxData[
\(x4\)], "Output"],
Cell[BoxData[
\(allAxioms["stack"[], xx]\)], "Output"],
Cell[BoxData[
\(allAxioms["stack"[], xx]\)], "Output"],
Cell[BoxData[
\(allAxioms["stack"[x4, "stack"[x2, "stack"[x1, "stack"[]]]],
xx]\)], "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[
\(\(\( (*\
Deliberate\ errors\ *) \)\(\[IndentingNewLine]\)\(top[\
s1\ ]\[IndentingNewLine]
drop[\ s1\ ]\)\)\)], "Input"],
Cell[BoxData[
\("***Error: stack.top- empty"\)], "Print"],
Cell[BoxData[
\(First::"first" \(\(:\)\(\ \)\)
"\!\(\"stack\"[]\) has a length of zero and no first \
element."\)], "Message"],
Cell[BoxData[
\(First["stack"[]]\)], "Output"],
Cell[BoxData[
\("***Error: stack.drop- empty"\)], "Print"],
Cell[BoxData[
\(Last::"nolast" \(\(:\)\(\ \)\)
"\!\(\"stack\"[]\) has a length of zero and no last \
element."\)], "Message"],
Cell[BoxData[
\(Last["stack"[]]\)], "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[
StyleBox[\(timing2[\ \((sa = new[];
Do[sa\ = \ push[sa, i], \ {i, #}])\) &, 100000\ ] //
Print;\),
FormatType->StandardForm]], "Input"],
Cell[BoxData[
\({"iters"[100000, 200000],
"times"[0.6010000000000002`\ Second,
1.1919999999999997`\ Second],
"ratios"[2, 1.9833610648918458`],
"Order^0.987947"}\)], "Print"]
}, Open ]]
},
FrontEndVersion->"4.2 for Microsoft Windows",
ScreenRectangle->{{0, 1280}, {0, 979}},
WindowSize->{772, 740},
WindowMargins->{{13, Automatic}, {Automatic, 6}}
]
- Follow-Ups:
- Re: Re: OOP experiments in Mathematica- The Stack
- From: Daniel Lichtblau <danl@wolfram.com>
- Re: Re: OOP experiments in Mathematica- The Stack