Re: Re: Grouping problem?

"Conal Tuohy" <conalt@xxxxxxxxxxxxxxx> wrote in message
news:000c01c30927$86c52f30$d9784fcb@xxxxxxxxxxxxxxxxxxxx
> Hi Lars. I think you're right about the correct definition of the problem.
> So I still didn't have my conditions right.
>
> Here's my 3rd version of the recursive solution, which now produces the
same
> output as Benjamin's.
>
> I would guess that this recursive solution would be quicker (for documents
> larger than a certain size), but on the other hand perhaps it could
produce
> stack-overflow problems on really large documents? As I understand it,
using
> tail-recursion is supposed to allow the XSLT interpreter to optimise the
> recursion by converting to it a loop, without pushing stack frames ... but
I
> don't know how many processors actually implement this? Does anyone know?
Is
> my code below appropriate for this kind of optimisation?
>
>
http://www-106.ibm.com/developerworks/xml/library/x-xslrecur/?dwzone=xml#opt
> 4
> http://info.astrian.net/jargon/terms/t/tail_recursion.html :-)


You can use a DVC (Divide and Conquer) style algorithm here. Split a
node-set into two and recursively solve the problem on them.

Your recursive template must accept some initial accumulated number as a
parameter -- the sum of the last group of elements of the first half will be
passed as this initial accumulation to the template invocation that
processes the second half.

The recursion depth of a DVC algorithm is only log2(N).

http://www.topxml.com/code/default.asp?p=3&id=v20020107050418

=====
Cheers,

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




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