[xsl] Re: Collating riffled lists

Subject: [xsl] Re: Collating riffled lists
From: "Dimitre Novatchev" <dnovatchev@xxxxxxxxx>
Date: Tue, 30 Sep 2003 11:12:26 +0200
Hi Mat,

Using the "zipWith" template from FXSL I observe a steady linear behaviour
(all times below are in milliseconds, the tests were performed on a 1.7GHz
PC with 256MB RAM using W2K and MSXML4 latest SP):

Nodes:                     15         30      300         3000       30000
============================================
Naive solution      0.294   0.421   4.860          270       24784

zipWith                0.550   0.884   7.076             76           846


Here's the code:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
 xmlns:myZip="my:Zip"
 exclude-result-prefixes="myZip">

 <xsl:import href="E:\xml\msxml\XML
SDK\Samples\Tests\Generic\FP\Fxsl\Exslt-Based\zipWithDVC.xsl"/>

 <xsl:output method="text"/>

 <xsl:variable name="vfunZip" select="document('')/*/myZip:*[1]"/>

  <xsl:template match="/">
    <xsl:variable name="vA" select="/*/item[substring(., 1, 1) = 'a']"/>
    <xsl:variable name="vB" select="/*/item[substring(., 1, 1) = 'b']"/>

    <xsl:call-template name="zipWith">
      <xsl:with-param name="pFun" select="$vfunZip"/>
      <xsl:with-param name="pList1" select="$vA"/>
      <xsl:with-param name="pList2" select="$vB"/>
      <xsl:with-param name="pElName" select="'t'"/>
    </xsl:call-template>
  </xsl:template>

  <myZip:myZip/>
  <xsl:template match="myZip:*">
    <xsl:param name="pArg1" select="/.."/>
    <xsl:param name="pArg2" select="/.."/>

    <xsl:value-of
    select="concat(substring($pArg1, 2), substring($pArg2, 2))"/>
  </xsl:template>
</xsl:stylesheet>


It produces slightly different result from what you want, but this can be
adjusted (e.g. in order to get also the number one may use zipWith3).


 a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6


The zipWith template *does not* use any extension functions.

=====
Cheers,

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







"Mat Myszewski" <mmyszew@xxxxxxxxxxx> wrote in message news:004d01c386ef$a9b
f7b30$65f2da18@xxxxxxxxxxx
> Michael
>
> Thanks for the info. I tried it and it works on the abstract problem as
> advertised.
>
> And thanks for your XSLT book! It's been a great help to this XSLT newbie.
>
> Unfortunately, the real-life problem is less well-structured than the
> abstraction.
>
> Here's another abstraction that better captures the (lack of) structure of
> the problem. As before, I believe this runs O(n^2) and n is large. I'd
like
> to try to stick with XSLT 1.0 if possible. Any improvements are most
> welcome. If this is as good as it gets, that would also be useful info.
>
> Here's what I'd like to be able to do: Create a recursive function to
build
> a node list of all the b's, then select from that with an index. I think
> that would need 1.1 or processor-specific extensions, however.
>
> XML source:
>
> <?xml version="1.0"?>
> <list>
> <item>something else</item>
> <item>a a1</item>
> <item>a a2</item>
> <item>something else</item>
> <item>a a3</item>
> <item>b b1</item>
> <item>something else</item>
> <item>b b2</item>
> <item>a a4</item>
> <item>b b3</item>
> <item>a a5</item>
> <item>b b4</item>
> <item>a a6</item>
> <item>b b5</item>
> <item>b b6</item>
> </list>
>
> A recursive solution:
>
> <xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
> version="1.0">
>
> <!-- match first a and make top level call to recursive template -->
> <xsl:template match="item[1]">
>   <xsl:call-template name="do_a">
>     <xsl:with-param name="ix" select="0" />
>   </xsl:call-template>
> </xsl:template>
>
> <!-- recursive template counts a's -->
> <xsl:template name="do_a">
>   <xsl:param name="ix" />
>
>   <xsl:choose>
>     <xsl:when test="starts-with(., 'a')">
>       <!-- Output the a -->
>       <xsl:text>&#xA;</xsl:text>
>       <xsl:value-of select="$ix + 1" />
>       <xsl:text>: </xsl:text>
>       <xsl:value-of select="substring-after(.,' ')" />
>       <xsl:text> </xsl:text>
>
>       <!-- Output the corresponding b -->
>       <xsl:for-each select="//item[1]">
>         <xsl:call-template name="do_b">
>           <xsl:with-param name="ix" select="$ix + 1" />
>         </xsl:call-template>
>       </xsl:for-each>
>
>       <!-- process remaining a's -->
>       <xsl:for-each select="following::item[1]">
>         <xsl:call-template name="do_a">
>              <xsl:with-param name="ix" select="$ix + 1" />
>         </xsl:call-template>
>       </xsl:for-each>
>     </xsl:when>
>     <xsl:otherwise>
>       <!-- Look for next a -->
>       <xsl:for-each select="following::item[1]">
>         <xsl:call-template name="do_a">
>              <xsl:with-param name="ix" select="$ix" />
>         </xsl:call-template>
>       </xsl:for-each>
>     </xsl:otherwise>
>   </xsl:choose>
> </xsl:template>
>
> <!-- recursive template outputs the ix-th b -->
> <xsl:template name="do_b">
>   <xsl:param name="ix" />
>
>   <xsl:choose>
>     <xsl:when test="starts-with(., 'b')">
>       <xsl:choose>
>         <xsl:when test="$ix = 1">
>           <xsl:value-of select="substring-after(.,' ')" />
>         </xsl:when>
>         <xsl:otherwise>
>           <!-- Look for next b -->
>           <xsl:for-each select="following::item[1]">
>             <xsl:call-template name="do_b">
>                  <xsl:with-param name="ix" select="$ix - 1" />
>             </xsl:call-template>
>           </xsl:for-each>
>         </xsl:otherwise>
>       </xsl:choose>
>     </xsl:when>
>     <xsl:otherwise>
>       <!-- Look for next b -->
>       <xsl:for-each select="following::item[1]">
>         <xsl:call-template name="do_b">
>              <xsl:with-param name="ix" select="$ix" />
>         </xsl:call-template>
>       </xsl:for-each>
>     </xsl:otherwise>
>   </xsl:choose>
> </xsl:template>
> <!-- suppress other output -->
> <xsl:template match="text()" />
>
> </xsl:stylesheet>
>
> Output:
>
> <?xml version="1.0" encoding="utf-8"?>
> 1: a1 b1
> 2: a2 b2
> 3: a3 b3
> 4: a4 b4
> 5: a5 b5
> 6: a6 b6
>
> Thanks,
>                 Mat
>
>
>  XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
>
>




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


Current Thread