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}} ]