Re: Re: OOP experiments in Mathematica- The Stack
- To: mathgroup at smc.vnet.net
- Subject: [mg38740] Re: [mg38682] Re: OOP experiments in Mathematica- The Stack
- From: "Steve S. Shaw" <steve at shawstudio.com>
- Date: Tue, 7 Jan 2003 07:28:54 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
"Steve S. Shaw" wrote: > > "Daniel Lichtblau" wrote: > > > > "Steve S. Shaw" wrote: > > > > > > 2. I replaced the "Null"s with "node[]". > > > > > > Result: huge speed up, and dropped to linear (Order^1). > > > [...] > > > > O(n*Log[n]), actually. You have a binary tree in the Husain example. > > That would make sense. But oddly, the measured timing values ranged from > O^0.9 to O^1.02 > > I tried it with different numbers of nodes, up to a million. > Near-perfect linearity. > > Any clues how that could be? > > -- Steve S. Found out what I was doing wrong. I defined "node" AFTER the function definitions. As a result, the function patterns didn't match - the definitions were to any undefined symbol, but my data was using a string "node" as the head. Mathematica was just building a big structure of "node" and "add" chunks, without actually calling any functions. Changed the code by moving the line node = "node" AHEAD of the "add[...]" definitions. Now I get time values around O^1.24, for 20,000 iterations. This looks consistent with an O(n*Log[n]) algorithm. Unfortunately, now that it is really doing the work, the performance is not great. I will need to investigate more, to see whether my <typeName>[...] scheme gives practical performance in Mathematica. -- Steve S.