打印从一到一百万的数字 [英] Print numbers from one to one million
问题描述
假设您有一项高度综合的任务，需要在没有适当输入 XML 的情况下打印 1 到 1.000.000 之间的数字.当然，具有讽刺意味的是，由于堆栈溢出，直接递归将失败.
我想出了下面列出的解决方案:
<xsl:when test="$stop = 0"><xsl:value-of select="$start"/>:<xsl:value-of select="$ololo"/><xsl:text>
</xsl:text></xsl:when><xsl:否则><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:否则></xsl:选择></xsl:if></xsl:模板></xsl:stylesheet>它适用于 libxslt 和 MSXML.但它打印了一些重复的数字，在效率方面看起来很尴尬.这可以以某种方式改进吗?
这是一个通用的迭代"模板，它对初始输入执行操作，然后对其结果执行操作，直到指定给定条件
强>.
这种转换是尾递归，并且在使用智能 XSLT 处理器时不会出现堆栈溢出:
<xsl:output method="text"/><我的:动作><end>1000000</end></my:action><xsl:变量名="vAction"select="document('')/*/my:action"/><xsl:template match="/"><xsl:call-template name="迭代"><xsl:with-param name="pAction" select="$vAction"/><xsl:with-param name="pInput" select="0"/></xsl:call-template></xsl:模板><xsl:模板名称=迭代"><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:变量><xsl:copy-of select="$vResult"/><xsl:call-template name="迭代"><xsl:with-param name="pAction"选择 =$pAction"/><xsl:with-param name="pInput" select="$vResult"/></xsl:call-template></xsl:if></xsl:模板><xsl:template match="my:action"><xsl:param name="pInput" select="0"/><xsl:if test="not($pInput >= end)"><xsl:value-of select="concat($pInput+1,'
')"/></xsl:if></xsl:模板></xsl:stylesheet> 当此转换应用于任何 XML 文档(未使用)时，将尾递归优化为迭代的智能 XSLT 处理器会产生所需的结果，而不会出现堆栈溢出.Saxon 6.5.4 就是这种情况，我用它来生成结果.
您的问题是并非所有 XSLT 处理器都能识别并优化尾递归.
对于这样的处理器，可以使用 DVC 风格的递归:
<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:模板><xsl:template name="displayNumbers"><xsl:param name="pStart"/><xsl:param name="pEnd"/><xsl:if test="not($pStart > $pEnd)"><xsl:when test="$pStart = $pEnd"><xsl:value-of select="$pStart"/><xsl:text>
</xsl:text></xsl:when><xsl:否则><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:否则></xsl:选择></xsl:if></xsl:模板></xsl:stylesheet> 这个转换使用 MSXML4 产生正确的结果，没有任何崩溃.
使用此 DVC 转换，最大递归深度仅为 Log2(N) -- 在本例中为 19.
我建议使用 FXSL 库.它提供了常用高阶函数的 DVC 变体，例如 foldl() 和 map()，使得生成几乎所有递归算法的 DVC 变体成为可能.
当然，在 XSLT2.0 中可以简单地写:
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 <= ($end)">
<xsl:choose>
<xsl:when test="$stop = 0">
<xsl:value-of select="$start"/>:<xsl:value-of select="$ololo"/>
<xsl:text>
</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?
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,'
')"/>
</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>
</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"/>
这篇关于打印从一到一百万的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
