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