If you work forwards through the list, you can pass the computed values
onwards as parameters rather than recomputing them each time, which
should make the algorithm O(n) rather than O(n^2).

If you prefer, you can get the caching effect by using memoized
functions in Saxon (saxon:memo-function="yes"), but you have to ask for
this explicitly.

Michael Kay


> -----Original Message-----
> From: owner-xsl-list@xxxxxxxxxxxxxxxxxxxxxx 
> [mailto:owner-xsl-list@xxxxxxxxxxxxxxxxxxxxxx] On Behalf Of FC
> Sent: 27 November 2003 13:37
> To: XSL-List@xxxxxxxxxxxxxxxxxxxxxx
> Subject:  how to optimize recursive algorithm?
> 
> 
> 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.
> 
> Bye,
> Flavio
> 
> 
>  XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
> 


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