Распечатайте числа от одного до миллиона

Question

Предположим, у вас сложная задача - печатать числа от 1 до 1.000.000 без соответствующего входного XML.Конечно, прямая рекурсия потерпит неудачу из-за, по иронии судьбы, переполнения стека.

Я предложил решение, перечисленное ниже:

<?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, который оптимизирует хвостовую рекурсию в итерацию, дает желаемый результат без переполнения стека. Это случай с Saxon 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 . Он предоставляет варианты DVC часто используемых функций высшего порядка, таких как foldl() и map(), что позволяет создавать вариант DVC практически любого рекурсивного алгоритма.

Конечно, в XSLT2.0 можно было бы просто написать :

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