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(_at_)lists(_dot_)mulberrytech(_dot_)com
[mailto:owner-xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com] On Behalf Of
FC
Sent: 27 November 2003 13:37
To: XSL-List(_at_)lists(_dot_)mulberrytech(_dot_)com
Subject: [xsl] 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