Re: Re: HOWTO: convert flat list w/ level information

---- David Tolpin wrote:

> >  
> >  The following transformation achieves the same (level values are
> >  monotonous
> >  but not strictly consecutive, container/item info not used) and at 
> >  the same
> >  time is twice shorter and considerably less complex.
> >  
> >  It is just 33 lines (compared to 66 lines) and consists of just two
> >  templates one of which has one parameter and the other no parameters
> >  (compared to three templates one of which takes two parameters and 
> >  another
> >  which takes four parameters):
>  
> 
> Dimitre,
> 
> in my code I was trying to get rid of exponential computation times, so
> popular
> for XLST grouping problem, but often inadequate. My template processes 
> 100 lines 
> in 2 seconds, yours in 9 seconds. The same 100 lines repeated twice take

> 4 seconds with my template, and 106 seconds with yours. 
> 
> Of course, it depends on the problem to solve, but a couple of hundreds 
> of entries in a hierarchical table of contents is not uncommon.
> 
> David 

David,

It is nice to produce a fast algorithm but it is even nicer when this
algorithm is correct.

Your transformation produces not what is expected.

With this source.xml:

<node>
  <node level="0" type="c" name="toplevel"/>
  <node level="3" type="i" name="1. item"/>
  <node level="3" type="c" name="2. container"/>
  <node level="4" type="i" name="2.1 item"/>
  <node level="4" type="i" name="2.2 item"/>
  <node level="2" type="i" name="3. item"/>
  <node level="2" type="c" name="4. container"/>
  <node level="3" type="i" name="4.1 item"/>
  <node level="3" type="c" name="4.2 container"/>
  <node level="5" type="i" name="4.2.1 item"/>
  <node level="2" type="i" name="5. item"/>
</node>

the correct result is:

<node>
   <node level="0" type="c" name="toplevel">
      <node level="3" type="i" name="1. item"/>
      <node level="3" type="c" name="2. container">
         <node level="4" type="i" name="2.1 item"/>
         <node level="4" type="i" name="2.2 item"/>
      </node>
      <node level="2" type="i" name="3. item"/>
      <node level="2" type="c" name="4. container">
         <node level="3" type="i" name="4.1 item"/>
         <node level="3" type="c" name="4.2 container">
            <node level="5" type="i" name="4.2.1 item"/>
         </node>
      </node>
      <node level="2" type="i" name="5. item"/>
   </node>
</node>


However, the result of applying your transformation is:

<node>
   <node level="0" type="c" name="toplevel">
      <node level="3" type="i" name="1. item">
         <node level="3" type="c" name="2. container">
            <node level="4" type="i" name="2.1 item">
               <node level="4" type="i" name="2.2 item"/>
            </node>
         </node>
         <node level="2" type="i" name="3. item"/>
         <node level="2" type="c" name="4. container">
            <node level="3" type="i" name="4.1 item"/>
            <node level="3" type="c" name="4.2 container">
               <node level="5" type="i" name="4.2.1 item"/>
            </node>
         </node>
         <node level="2" type="i" name="5. item"/>
      </node>
   </node>
</node>

I would be happy to consider the efficiency of your algorithm once it is
correct. If there are no radical changes in it, expect it to have problems
with processing large inputs. I would be glad to help correct these
problems.

Unfortunately, I could not reproduce the timing results you claim hold for
the transformation I proposed. Probably you are using a very slow XSLT
processor on a slow machine.

The timing results I get with MSXML4 on a 800MHz Pentium with 512MB RAM
under W2K are the following:

With 100 nodes the stylesheet execution times vary in the range 90 - 140
milliseconds.

With 200 nodes the time range was 708 - 1106 milliseconds.

Of course, I haven't thought about any optimizations, but the observed
timings are not that bad as reported by you.





=====
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