Re: RE: Re: Why is my Implementation of Sorted Trees So Slow?

*To*: mathgroup at smc.vnet.net*Subject*: [mg36679] Re: [mg36649] RE: [mg36644] Re: [mg36485] Why is my Implementation of Sorted Trees So Slow?*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Wed, 18 Sep 2002 02:10:22 -0400 (EDT)*References*: <200209160433.AAA07056@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

DrBob wrote: > > This code is almost identical to yours in principle, yet 30% faster: > > (compared with the code in your notebook, not the code in the post > below) > > ClearAll[emptyTree, treeInsert]; > emptyTree = {}; > > treeInsert[emptyTree, elem_] := {emptyTree, elem, emptyTree} > treeInsert[tree_, elem_] /; SameQ[tree[[2]], elem] := tree > treeInsert[tree_, elem_] /; OrderedQ[{tree[[2]], elem}] := > {First[tree], tree[[2]], treeInsert[Last[tree], elem]} > treeInsert[tree_, elem_] := {treeInsert[First[tree], elem], tree[[2]], \ > Last[tree]} > > Here's an even simpler version, same speed: > > ClearAll[emptyTree, treeInsert]; > emptyTree = {}; > > treeInsert[emptyTree, elem_] := {emptyTree, elem, emptyTree} > treeInsert[tree_, elem_] := Which[ > SameQ[tree[[2]], elem], tree, OrderedQ[{tree[[2]], elem}], > {First@tree, tree[[2]], treeInsert[Last@tree, elem]}, > True, {treeInsert[First@tree, elem], tree[[2]], Last@tree}] I had tried variations on this but they all seemed ever so slightly slower. Might be version an OS dependent. > I see one obvious advantage of your algorithm over Husain's and my > earlier code; though I'm not sure it explains its better behavior. That > is, while my algorithm made pattern matching more burdensome, yours > virtually eliminated it. > > Also, the biggest improvement I've seen comes simply from replacing Null > with anything else in Husain's code. Again, that seems to suggest that > time spent on pattern matching is the problem. All the algorithms do > approximately the same real work on the tree structure. > > I really like how Flatten changes your tree into a sorted list. Very > nice! Goes by the name of "tree sort". Using Flatten is basically a shortcut for walking the tree left-to-right. > Bobby Treat It seems I did not look hard enough at the original post or the follow-ups. In point of fact, regarding speed, there IS no obvious advantage of my code over that first version. The advantage is there, of course, as timing checks indicate. But it is quite far from obvious. The reason is related to the (rare) need for Update. It is pointed out in the manual that "infinite" evaluation is not in fact possible (no surprise thus far). A consequence is that Mathematica requires internal optimization features to keep reevaluation to a minimum. Update may be required in cases where such optimizations are overzealous. What we have in the case of this example is, roughly, the opposite. The code that determines need for reevaluation is simply not working sufficiently well. It does make the correct determination, but only after looking over the entire structure that is being evaluated. As we have a structure growing linearly in the number of iterations, and it gets mostly traversed each iteration, the algorithmic complexity becomes at least O(n^2). Not a disaster unless the appropriate complexity is smaller, which was the case for this example. This is not a bug insofar as it is a (regretably) necessary consequence of Mathematica evaluation semantics. The problems it can cause are all the same quite undesirable. We've made some inroads on this problem by enlarging substantially the class of expressions for which reevaluation may be quickly short-circuited, with the idea of fixing all but the most pathological of examples. The status of that work is unfortunately not known to me at present, though I'll try to find out about it. Daniel Lichtblau Wolfram Research