MathGroup Archive 2003

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

Search the Archive

Re: Re: OOP experiments in Mathematica- The Stack

  • To: mathgroup at smc.vnet.net
  • Subject: [mg38744] Re: [mg38682] Re: OOP experiments in Mathematica- The Stack
  • From: "Steve S. Shaw" <steve at shawstudio.com>
  • Date: Tue, 7 Jan 2003 07:32:22 -0500 (EST)
  • Sender: owner-wri-mathgroup at wolfram.com

"Steve S. Shaw" wrote:
>
> "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.

(Previous notebook I posted has a typo.)

After various experiments,
I conclude that the problem is the "Null"s,
NOT the use of heads other than List.

The notebook listed below shows the tests.

Results (for 2000/4000 iterations):

* Original version:
times[1.24 Sec,5.25 Sec]
Order^2.08

* Version using "{}" instead of "Null" (uses "node[...]"):
times[0.3 Seco,0.68 Sec]
Order^1.18

* Version using "{}" for Null, and "{...}" for node:
times[0.28 Sec,0.65 Sec]
Order^1.21

Within the accuracy of measurement, the latter two are the same, and are
O(n*Log[n]).

NOTE: My "Order^..." calculation would ideally yield
1.12591 for 2000/4000 iterations:
In:=
 Log[ ((4000Log[4000])/(2000Log[2000])) ] /Log[ 4000/2000 ]//N
Out:=
1.12591

-----------------------------------------------------------------
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[
    \( (*\ Sorted\ tree . \[IndentingNewLine]Original\ by\ Husain@
            MIT . EDU . \[IndentingNewLine]Modified\ by\ \
ToolmakerSteve@ShawStudio .
          com . \[IndentingNewLine]\(NOTE : \
            The\ algorithm\ is\ expected\ to\ be\ \(\(O^\((N\ log \
\((N)\))\)\)\(.\)\)\)\[IndentingNewLine]*) \)], "Input"],

Cell[BoxData[
    RowBox[{\( (*\ PERFORMANCE : \ Original\ version, \
        using\ "\<Null\>"
          s\ to\ terminate\ tree . \[IndentingNewLine]\(RESULT : \
              In\ Mathematica\), \
        this\ is\ about\ O^2. \[IndentingNewLine]*) \),
      "\[IndentingNewLine]",
      RowBox[{\(Clear[\ add\ ];\), "\[IndentingNewLine]",
        StyleBox[\(add[\ Null, x_Real\ ] :=
              node[\ x, Null, Null\ ];\),
          FormatType->StandardForm], "\[IndentingNewLine]",
        StyleBox[\(add[\ Null, node[\ x_Real, lower_, higher_\ ]\ ] :=
              node[\ x, lower, higher\ ];\),
          FormatType->StandardForm],
        StyleBox["\[IndentingNewLine]",
          FormatType->StandardForm],
        StyleBox[\(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]];\),
          FormatType->StandardForm],
        StyleBox["\[IndentingNewLine]",
          FormatType->StandardForm],
        StyleBox[\(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[CellGroupData[{

Cell[BoxData[{\(SeedRandom[5];\), "\[IndentingNewLine]", \(nums =
      Null; \ Do[\ nums = add[\ nums, Random[]\ ], \ {6}\ ]; \
    nums // Print;\), "\[IndentingNewLine]",
    StyleBox[\(timing2[\ \((nums = Null; \
                Do[nums = add[\ nums, Random[]\ ], \ {#}])\) &,
            2000\ ] // Print;\),
      FormatType->StandardForm]}], "Input"],

Cell[BoxData[
    \(node[0.7865985779841621`,
      node[0.6128273120449554`,
        node[0.39803759651651716`,
          node[0.23801182511533805`, Null, Null],
          node[0.5172315671024557`, Null, Null]], Null],
      node[0.8483394783354097`, Null, Null]]\)], "Print"],

Cell[BoxData[
    \({"iters"[2000, 4000],
      "times"[1.2409999999999997`\ Second,
        5.248000000000001`\ Second], "ratios"[2, 4.228847703464949`],
      "Order^2.08026"}\)], "Print"]
}, Open  ]],

Cell[BoxData[
    RowBox[{\( (*\
        PERFORMANCE : \ "\<node\>"\ still\ undefined\ symbol . \
\[IndentingNewLine]Use\ "\<{}\>"\ instead\ of\ "\<Null\>" . \
\[IndentingNewLine]\(Result : \
                O^\((N\ log \((N)\))\) . \ \ As\ fast\ as\ "\<list\>"\
\ \(version!\)\)\[IndentingNewLine]*) \), "\[IndentingNewLine]",
      RowBox[{\(Clear[\ add, node\ ];\), "\[IndentingNewLine]",
        StyleBox[\(add[\ {}, x_Real\ ] := node[\ x, {}, {}\ ];\),
          FormatType->StandardForm],
        StyleBox["\[IndentingNewLine]",
          FormatType->StandardForm],
        StyleBox[\(add[\ {}, node[\ x_Real, lower_, higher_\ ]\ ] :=
              node[\ x, lower, higher\ ];\),
          FormatType->StandardForm],
        StyleBox["\[IndentingNewLine]",
          FormatType->StandardForm],
        StyleBox[\(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]];\),
          FormatType->StandardForm],
        StyleBox["\[IndentingNewLine]",
          FormatType->StandardForm],
        StyleBox[\(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[CellGroupData[{

Cell[BoxData[
    RowBox[{"\[IndentingNewLine]",
      RowBox[{\(SeedRandom[5];\),
        "\[IndentingNewLine]", \(nums = {}; \
        Do[\ nums = add[\ nums, Random[]\ ], \ {6}\ ]; \
        nums // Print;\), "\[IndentingNewLine]",
        StyleBox[\(timing2[\ \((nums = {}; \
                    Do[nums = add[\ nums, Random[]\ ], \ {#}])\) &,
                2000\ ] // Print;\),
          FormatType->StandardForm]}]}]], "Input"],

Cell[BoxData[
    \(node[0.7865985779841621`,
      node[0.6128273120449554`,
        node[0.39803759651651716`,
          node[0.23801182511533805`, {}, {}],
          node[0.5172315671024557`, {}, {}]], {}],
      node[0.8483394783354097`, {}, {}]]\)], "Print"],

Cell[BoxData[
    \({"iters"[2000, 4000],
      "times"[0.29999999999999893`\ Second,
        0.6810000000000009`\ Second],
      "ratios"[2, 2.270000000000011`], "Order^1.18269"}\)], "Print"]
}, Open  ]],

Cell[BoxData[
    RowBox[{\( (*\
        PERFORMANCE : \
          Version\ using\ "\<List\>"
            s\ only . \[IndentingNewLine]\(Result : \ \(\(O^\((N\ log \
\((N)\))\)\)\(.\)\)\)\[IndentingNewLine]*) \), "\[IndentingNewLine]",

      RowBox[{\(Clear[\ add\ ];\), "\[IndentingNewLine]",
        StyleBox[\(add[\ {}, x_Real\ ] := {\ x, {}, {}\ };\),
          FormatType->StandardForm],
        StyleBox["\[IndentingNewLine]",
          FormatType->StandardForm],
        StyleBox[\(add[\ {}, {\ x_, lower_, higher_\ }\ ] := {\ x,
                lower, higher\ };\),
          FormatType->StandardForm],
        StyleBox["\[IndentingNewLine]",
          FormatType->StandardForm],
        StyleBox[\(add[\ {\ x_, lower_, higher_\ },
                y_Real\ ] := \[IndentingNewLine]If[\
                x > y, \[IndentingNewLine]{\ x, add[\ lower, y\ ],
                  higher\ }, \[IndentingNewLine]{\ x, lower,
                  add[\ higher, y\ ]\ }\[IndentingNewLine]];\),
          FormatType->StandardForm],
        StyleBox["\[IndentingNewLine]",
          FormatType->StandardForm],
        StyleBox[\(add[\ {\ x_, lowerx_, higherx_\ }, {\ y_, lowery_,
                  highery_\ }\ ] := \[IndentingNewLine]If[\
                x > y, \[IndentingNewLine]{\ x,
                  add[\ lowerx, {\ y, lowery, highery\ }\ ],
                  higherx\ }, \[IndentingNewLine]{\ x, lowerx,
                  add[\ higherx, {\ y, lowery,
                      highery\ \ }\ ]\ }\[IndentingNewLine]];\),
          FormatType->StandardForm]}]}]], "Input"],

Cell[CellGroupData[{

Cell[BoxData[{\(SeedRandom[
        5];\), "\[IndentingNewLine]", \(nums = {}; \
    Do[nums = add[\ nums, Random[]\ ], \ {6}]; \
    nums // Print;\), "\[IndentingNewLine]",
    StyleBox[\(timing2[\ \((nums = {}; \
                Do[nums = add[\ nums, Random[]\ ], \ {#}])\) &,
            2000\ ] // Print;\),
      FormatType->StandardForm]}], "Input"],

Cell[BoxData[
    \({0.7865985779841621`, {0.6128273120449554`, \
{0.39803759651651716`, {0.23801182511533805`, {}, {}}, \
{0.5172315671024557`, {}, {}}}, {}}, {0.8483394783354097`, {}, \
{}}}\)], "Print"],

Cell[BoxData[
    \({"iters"[2000, 4000],
      "times"[0.2810000000000006`\ Second,
        0.6509999999999998`\ Second],
      "ratios"[2, 2.3167259786476815`], "Order^1.21209"}\)], "Print"]
}, Open  ]]
},
FrontEndVersion->"4.2 for Microsoft Windows",
ScreenRectangle->{{0, 1280}, {0, 979}},
WindowSize->{916, 902},
WindowMargins->{{115, Automatic}, {Automatic, 7}}
]




  • Prev by Date: Re: Irreducible Polynomial over GF(2)
  • Next by Date: Re: Re: OOP experiments in Mathematica- The Stack
  • Previous by thread: Re: Re: OOP experiments in Mathematica- The Stack
  • Next by thread: Re: Pasting tables into Excel