Re: how to optimize recursive algorithm?

"FC" <flavio@xxxxxx> wrote in message
news:000c01c3b4eb$8f1f8e30$6501a8c0@xxxxxxxxx
> Houston, we've got a problem.
> I have a transformation calculating the position of certain graphical
> elements and each element's position is affected by the position of its
> ancestors and preceding siblings. The recursive algorithm I wrote works
> well, meaning that the result is correct but is painfully slow when
dealing
> with big documents.
> This is no surprise because I am fully aware of the functional language
> constraints, but I am wondering if there is no viable workaround.
> For instance, I don't know the constraints imposed to the optimizer but I
> would expect some sort of "caching" of values calculated previously when
the
> same node is processed over and over by the same piece of code.
>
> For instance, say you have a source document like this:
>
> <top>
>     <a/>
>     <b/>
>     <c/>
>     <d/>
> </top>
>
> and the output of "b" depends on the position of "a", "c" depends on "b"
and
> so on.
> When the processor (recursively) processes "d", it should find, somewhere,
> the value calculated for "c" previously and (magically) save time.
>
> Now, since I really don't know what kind of optimizing mechanism is in
place
> for the xslt engines I've been using so far (Saxon, Altova, Microsoft), I
am
> asking if you have any idea as how to make recursive algorithms faster in
> cases like those just described.

Recursive algorithms can be designed in such a way so that they do not need
to be further optimized.

One technique is to use the DVC (Divide and Conquer) style. Another is to
use the "foldl" or "foldr" function from FXSL. These functions accept a
"zero" argument, which in further recursive calls contains all accumulated
intermediate results.

Of course, there are DVC-style implementations of foldl and foldr in FXSL
and I will probably end up removing any non-DVC functions so that the users
will only use the optimized DVC-style functions.

In many cases the optimization can be carried out still further, by
eliminating recursion altogether -- see for example the description of the
step by step optimizations performed in implementing "EXSLT for MSXML4" -- 
published under the same name in xml.com in August 2003.


=====
Cheers,

Dimitre Novatchev.
http://fxsl.sourceforge.net/ -- the home of FXSL




 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list