Imprime les nombres de un à un million

Question

Supposons que vous ayez une tâche hautement synthétique pour imprimer des nombres de 1 à 1.000.000 sans XML d'entrée approprié. Bien sûr, la récursivité directe échouera en raison d'un débordement de pile, assez ironique.

je suis venu avec la solution ci-dessous:

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

Il fonctionne aussi bien dans libxslt et MSXML. Mais il imprime des numéros en double et semble assez gênant en termes d'efficacité. Cela peut-il être amélioré d'une manière ou d'une autre?

Answer 1

Voici un modèle générique "itérer" qui effectue une action sur une entrée initiale et ensuite sur son résultat, jusqu'à ce qu'une condition donnée soit spécifiée.

Cette transformation est récursive et fonctionne sans débordement de pile avec un processeur XSLT intelligente:

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

lorsque cette transformation est appliquée sur un document XML (non utilisé), un processeur XSLT intelligent qui optimise La récursion de queue dans l'itération produit le résultat voulu sans débordement de pile. C'est le cas de Saxon 6.5.4, que j'ai utilisé pour produire le résultat.

Votre problème est que tous les processeurs XSLT ne reconnaissent pas et n'optimisent pas la récursion de queue.

Pour ces processeurs, on peut utiliser DVC - récursion style:

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

cette transformation produit le résultat correct sans accident en utilisant MSXML4.

Avec cette transformation DVC la récursion profondeur maximale est seulement log2 (N) - dans ce cas 19.

Je vous conseille d'utiliser la FXSL library. Il fournit des variantes DVC de fonctions d'ordre supérieur couramment utilisées, telles que foldl() et map() permettant de produire la variante DVC de presque n'importe quel algorithme récursif.

Bien sûr, dans XSLT2.0 on simplement écrire:

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