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: [mg38737] Re: [mg38682] Re: OOP experiments in Mathematica- The Stack
• From: "Steve S. Shaw" <steve at shawstudio.com>
• Date: Tue, 7 Jan 2003 07:27:17 -0500 (EST)
• References: <av374s$g0t$1@smc.vnet.net> <200301041227.HAA24547@smc.vnet.net> <3E173418.D041203@wolfram.com>
• Sender: owner-wri-mathgroup at wolfram.com

"Daniel Lichtblau" wrote:

> Actually O(n^2), I suspect. This phenomenon is discussed to some extent
> at
>
> http://forums.wolfram.com/mathgroup/archive/2002/Sep/msg00324.html

I just took a look at that example.
Went to the beginning of that thread:

http://forums.wolfram.com/mathgroup/archive/2002/Sep/msg00139.html

I took Husain's example, verified that it is quite slow just for a few
nodes,
plus is Order^2.

1. I defined node:
node = "node"

Result: 5x speed up, but still Order^2.

2. I replaced the "Null"s with "node[]".

Result: huge speed up, and dropped to linear (Order^1).

*** Conclusion: rather than working hard to re-arrange this code,
just avoid "Null", and avoid "undefined symbols".

I am quite relieved.  This shows that it is practical to use Mathematica's
pattern-matcher with custom heads - not necessary to convert everything to
"plain" lists.

Notebook expression included below.

-- ToolmakerSteve (Steve S. Shaw)

-----------------------------------------------------------------
Notebook[{
Cell[BoxData[
    \(\(\( (*\
      Quiet\ any\ 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[CellGroupData[{

Cell[BoxData[
    RowBox[{\( (*\
        Sorted\ tree . \[IndentingNewLine]Original\ by\ Husain@MIT .
            EDU . \[IndentingNewLine]Modified\ by\ ToolmakerSteve@
              ShawStudio . com . \[IndentingNewLine]*) \),
      "\[IndentingNewLine]",
      StyleBox[\(add[\ node[], x_Real\ ] :=
          node[\ x, node[],
            node[]\ ]\[IndentingNewLine]\[IndentingNewLine]
        add[\ node[], node[\ x_Real, lower_, higher_\ ]\ ] :=
          node[\ x, lower,
            higher\ ]\[IndentingNewLine]\[IndentingNewLine]
        add[\ node[\ x_Real, lower_, higher_\ ],
            y_Real\ ] := \[IndentingNewLine]If[\
            x > y, \[IndentingNewLine]node[\ x, add[\ lower, y\ ],
              higher\ ], \[IndentingNewLine]node[\ x, lower,
              add[\ higher,
                y\ ]\ ]\[IndentingNewLine]]\[IndentingNewLine]\
\[IndentingNewLine]
        add[\ node[\ x_Real, lowerx_, higherx_\ ],
            node[\ y_Real, lowery_,
              highery_\ ]\ ] := \[IndentingNewLine]If[\
            x > y, \[IndentingNewLine]node[\ x,
              add[\ lowerx, node[\ y, lowery, highery\ ]\ ],
              higherx\ ], \
            node[\ x, lowerx,
              add[\ higherx,
                node[\ y, lowery,
                  highery\ \ ]]\ ]\[IndentingNewLine]]\),
        FormatType->StandardForm]}]], "Input"],

Cell[BoxData[
    \(Null\^4\)], "Output"]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
    RowBox[{\( (*\
        PERFORMANCE - \[IndentingNewLine]1 - \ declare\ "\<node\>", \
        so\ isn' t\ undefined\ symbol; \[IndentingNewLine]2 - \
          use\ "\<node[]\>"\ instead\ of\ "\<Null\>", \
        for\ empty\ \(\(leaves\)\(.\)\)\[IndentingNewLine]*) \),
      "\[IndentingNewLine]",
      RowBox[{\(SeedRandom[5];\),
        "\[IndentingNewLine]", \(node = "\<node\>"; \ \ \ \(node //
            FullForm\) // Print;\), "\[IndentingNewLine]",
        StyleBox[\(timing2[\ \((nums == node[]; \
                    Do[nums = add[\ nums, Random[]\ ], \ {#}])\) &,
                50000\ ] // Print;\),
          FormatType->StandardForm]}]}]], "Input"],

Cell[BoxData[
    TagBox[
      StyleBox["\"\<node\>\"",
        ShowSpecialCharacters->False,
        ShowStringCharacters->True,
        NumberMarks->True],
      FullForm]], "Print"],

Cell[BoxData[
    \({"iters"[50000, 100000],
      "times"[0.16999999999999993`\ Second,
        0.33999999999999986`\ Second], "ratios"[2, 2.`],
      "Order^1."}\)], "Print"]
}, Open  ]]
},
FrontEndVersion->"4.2 for Microsoft Windows",
ScreenRectangle->{{0, 1280}, {0, 979}},
WindowSize->{745, 919},
WindowMargins->{{250, Automatic}, {Automatic, 11}}
]

• References:
  • Re: OOP experiments in Mathematica- The Stack
    • From: "Steve S. Shaw" <steve@shawstudio.com>