Drucken Sie Zahlen von einer auf eine Million

Question

Angenommen, Sie haben eine hochsynthetische Aufgabe, um Zahlen von 1 bis 1.000.000 ohne entsprechende XML-Eingabe zu drucken. Natürlich scheitert die direkte Rekursion aufgrund von ironischem Stapelüberlauf.

kam ich mit der Lösung bis unten aufgeführt:

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

Es funktioniert sowohl in libxslt und MSXML. Aber es druckt einige doppelte Zahlen und sieht ziemlich peinlich in Bezug auf die Effizienz aus. Kann das irgendwie verbessert werden?

Answer 1

Hier ist eine generische "iterate" Vorlage, die eine Aktion für eine erste Eingabe und dann für ihr Ergebnis ausführt, bis eine bestimmte Bedingung angegeben wird.

Diese Transformation ist tail-rekursive und arbeitet ohne Stapelüberlauf mit einem intelligenten XSLT-Prozessor:

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

wenn diese Transformation an einem XML-Dokument (nicht verwendet), einen intelligenten XSLT-Prozessor, der optimiert angewandt wird Tail-Rekursion in Iteration erzeugt das gewünschte Ergebnis ohne Stack-Überlauf. Dies ist bei Saxon 6.5.4 der Fall, mit dem ich das Ergebnis erzeugt habe.

Ihr Problem ist, dass nicht alle XSLT-Prozessoren die Tail-Rekursion erkennen und optimieren.

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

diese Transformation erzeugt das richtige Ergebnis mit MSXML4 ohne Absturz: Stil Rekursion -

Für solche Prozessoren kann man DVC verwenden.

Mit dieser Transformation DVC die maximale Rekursion-Tiefe ist nur Log2 (N) - in diesem Fall 19

ich die FXSL library Verwendung empfehlen würde. Es stellt DVC-Varianten von häufig verwendeten Funktionen höherer Ordnung bereit, wie beispielsweise foldl() und map(), was es möglich macht, die DVC-Variante von fast jedem rekursiven Algorithmus zu erzeugen.

Natürlich in XSLT2.0 würde man einfach schreiben:

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