打印數字從一百萬到一百萬

Question

假設您有一個高度綜合的任務，在沒有適當的輸入XML的情況下打印1到1.000.000的數字。 當然，由於具有足夠的諷刺意味，堆棧溢出，直接遞歸將失敗。

我想出了下面列出的解決方案：

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

它在和的libxslt MSXML是雙向。但是它會打印一些重複的數字，在效率方面看起來很尷尬。這可以改進嗎？

Answer 1

這是一個通用的「迭代」模板，對初始輸入執行一個操作，然後對其結果執行操作，直到指定給定條件爲止。

這種轉化是尾遞歸和沒有堆棧溢出時用一個智能XSLT處理器：

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

當這種轉化是在任何XML文檔（未使用），智能XSLT處理器優化施加尾部遞歸迭代產生想要的結果而沒有堆棧溢出。撒克遜6.5.4就是這種情況，我用它來產生結果。

問題是，並非所有的XSLT處理器都能識別和優化尾遞歸。

對於這樣的處理器，可以使用DVC - 風格遞歸：

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

這種轉變產生正確的結果，而無需使用任何MSXML4崩潰。

利用這種DVC轉換的最大遞歸深度僅爲LOG2（N） - 在這種情況下19.

我建議使用FXSL library。它提供了常用高階函數的DVC變體，如foldl()和map()，使得幾乎任何遞歸算法都可以生成DVC變體。

當然，在XSLT2.0一個只會寫：

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