Re: In fact it's linear! (Was: Re: [xsl] Summary/Performance/Add Q: convert flat list w/ level information to a hierarcial one?)

[Dimitre Novatchev <dnovatchev@xxxxxxxxx>]

David,

> >  
> >  In fact, this transformation exhibits linear runtime behaviour!
> >  
> >  As for the potential problem with your transformation -- it is
obvious
> >  from the results.
> >  
> >  
> >  Thank you once again. I am glad that I was right to prefer the more
simple
> >  algorithm -- isn't small beautiful?  :o)
> >  
> 
> Dimitre,
> 
> 1) please repeat your experiment with other processors;

Would be glad to do this.

> 2) are your 3200 nodes nested within each other? This is the only case
> when stack overflow can happen. 

No, they are all siblings -- the logical nesting has a maximum depth of 3.

> Otherwise, that is, with proposed nesting
> levels upto 7, the stack overflow cannot simply be the case.

But it is.

> 3) the algorithm with lookahead for the next group is quadratic. by the 
> length
> of the nodes on the same level of hierarchy. It can only be linear if 
> all nodes
> are numbered sequentially.  Which is definitely not the usecase defined.

I do not understand this. I am using the data provided by the OP -- (with
different non-strictly consecutive values for @level) replicated many
times.

Could you, please, provide an xml document on which you think the
transformation would behave quadratically?

> 
> Please post your data or better mail it to me off-list. This is getting
> off-topic for the list, I think.

This is definitely a hot topic, because of number of reasons:

  1. The problems of writing correct and optimal algorithms are important
in XSLT development.

  2. The problems of writing efficient recursive algorithms in XSLT are
very important.

  3. There was a reference in one of your messages that exponential times
are typical of XSLT solutions and a hint that by simply using Haskell and
translating the Haskell functions to XSLT one would be creating more
efficient XSLT transformations.

Actually, it may turn out to be useful to translate the simple XSLT
transformation to Haskell :o).




David,



=====
Cheers,

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

__________________________________
Do you Yahoo!?
Free Pop-Up Blocker - Get it now
http://companion.yahoo.com/

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