xsl-list
[Top] [All Lists]

## Re: Re: Grouping problem?

2003-04-22 22:00:39
```
"Conal Tuohy" <conalt(_at_)paradise(_dot_)net(_dot_)nz> wrote in message
news:000c01c30927\$86c52f30\$d9784fcb(_at_)insurgentes(_dot_)local(_dot_)(_dot_)(_dot_)
```
```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

```
 Current Thread Re: Grouping problem?, (continued) Re: Grouping problem?, Simon Kelly Re: Grouping problem?, Simon Kelly Re: Grouping problem?, Simon Kelly Re: Grouping problem?, Benjamin Farrow RE: Grouping problem?, Lars Huttar RE: Grouping problem?, Conal Tuohy RE: Grouping problem?, Conal Tuohy Re: Grouping problem?, Dimitre Novatchev RE: Re: Grouping problem?, Lars Huttar RE: Re: Grouping problem?, Conal Tuohy Re: Re: Grouping problem?, Dimitre Novatchev <= Tail recursion (WAS: Grouping problem?), Conal Tuohy Re: Tail recursion (WAS: Grouping problem?), Mike Brown Re: Tail recursion (WAS: Grouping problem?), Dimitre Novatchev RE: Re: Grouping problem?, Michael Kay Re: Re: Grouping problem?, Dimitre Novatchev RE: Re: Grouping problem?, Benjamin Farrow