Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
396 views
in Technique[技术] by (71.8m points)

xslt - Print numbers from one to one million

Assume you have a highly synthetic task to print numbers from 1 to 1.000.000 without appropriate input XML. Of course, straight-forward recursion will fail due to, ironic enough, stack overflow.

I came up with the solution listed below:

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="text"/>

<xsl:variable name="end" select="number(1000000)"/>

<xsl:template match="/">    
    <xsl:call-template name="batches"/>
</xsl:template>

<xsl:template name="batches">
    <xsl:param name="start" select="number(1)"/>
    <xsl:param name="stop" select="$end"/>
    <xsl:param name="ololo"/>

    <xsl:if test="$start &lt;= ($end)">
        <xsl:choose>
            <xsl:when test="$stop = 0">
                <xsl:value-of select="$start"/>:<xsl:value-of select="$ololo"/>
                <xsl:text>&#xa;</xsl:text>
            </xsl:when>
            <xsl:otherwise>
                <xsl:call-template name="batches">
                    <xsl:with-param name="start" select="$start"/> 
                    <xsl:with-param name="stop" select="floor($stop div 2)"/>
                    <xsl:with-param name="ololo" select=" 'A' "/>
                </xsl:call-template>
                <xsl:call-template name="batches">
                    <xsl:with-param name="start" select="floor($stop div 2) + $start + 1"/>
                    <xsl:with-param name="stop" select="floor($stop div 2)"/>
                    <xsl:with-param name="ololo" select=" 'B' "/>
                </xsl:call-template>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:if>
</xsl:template>

</xsl:stylesheet>

It works both in libxslt and MSXML. But it prints some duplicate numbers and looks quite awkward in terms of efficiency. Can this be improved somehow?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Here is a generic "iterate" template that performs an action on an initial input and then on its result, until a given condition is specified.

This transformation is tail-recursive and works without stack overflow with an intelligent XSLT processor:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:my="my:my">
 <xsl:output method="text"/>

 <my:action>
   <end>1000000</end>
 </my:action>

 <xsl:variable name="vAction"
      select="document('')/*/my:action"/>

 <xsl:template match="/">
  <xsl:call-template name="iterate">
   <xsl:with-param name="pAction" select="$vAction"/>
   <xsl:with-param name="pInput" select="0"/>
  </xsl:call-template>
 </xsl:template>

 <xsl:template name="iterate">
   <xsl:param name="pAction"/>
   <xsl:param name="pInput"/>

   <xsl:if test="string-length($pInput)">
       <xsl:variable name="vResult">
         <xsl:apply-templates select="$pAction">
           <xsl:with-param name="pInput" select="$pInput"/>
         </xsl:apply-templates>
       </xsl:variable>

       <xsl:copy-of select="$vResult"/>

       <xsl:call-template name="iterate">
         <xsl:with-param name="pAction"
              select="$pAction"/>
         <xsl:with-param name="pInput" select="$vResult"/>
       </xsl:call-template>
   </xsl:if>
 </xsl:template>

 <xsl:template match="my:action">
  <xsl:param name="pInput" select="0"/>

  <xsl:if test="not($pInput >= end)">
   <xsl:value-of select="concat($pInput+1,'&#xA;')"/>
  </xsl:if>
 </xsl:template>
</xsl:stylesheet>

when this transformation is applied on any XML document (not used), an intelligent XSLT processor that optimizes tail recursion into iteration produces the wanted result without stack overflow. This is the case with Saxon 6.5.4, which I used to produce the result.

Your problem is that not all XSLT processors recognize and optimize tail-recursion.

For such processors, one can use DVC - style recursion:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
 <xsl:output method="text"/>

 <xsl:template match="/">
  <xsl:call-template name="displayNumbers">
    <xsl:with-param name="pStart" select="1"/>
    <xsl:with-param name="pEnd" select="1000000"/>
  </xsl:call-template>
 </xsl:template>

 <xsl:template name="displayNumbers">
  <xsl:param name="pStart"/>
  <xsl:param name="pEnd"/>

  <xsl:if test="not($pStart > $pEnd)">
   <xsl:choose>
    <xsl:when test="$pStart = $pEnd">
      <xsl:value-of select="$pStart"/>
      <xsl:text>&#xA;</xsl:text>
    </xsl:when>
    <xsl:otherwise>
      <xsl:variable name="vMid" select=
       "floor(($pStart + $pEnd) div 2)"/>
      <xsl:call-template name="displayNumbers">
       <xsl:with-param name="pStart" select="$pStart"/>
       <xsl:with-param name="pEnd" select="$vMid"/>
      </xsl:call-template>
      <xsl:call-template name="displayNumbers">
       <xsl:with-param name="pStart" select="$vMid+1"/>
       <xsl:with-param name="pEnd" select="$pEnd"/>
      </xsl:call-template>
    </xsl:otherwise>
   </xsl:choose>
  </xsl:if>
 </xsl:template>
</xsl:stylesheet>

this transformation produces the correct result without any crash using MSXML4.

With this DVC transformation the maximum recursion-depth is only Log2(N) -- in this case 19.

I would recommend using the FXSL library. It provides DVC variants of commonly used higher-order functions, such as foldl() and map() making it possible to produce the DVC variant of almost any recursive algorithm.

Of course, in XSLT2.0 one would simply write:

<xsl:sequence select="1 to 1000000"/>

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...