13

更新:为这个问题添加了一个答案,其中包含了几乎所有已给出的建议。下面代码中给出的原始模板需要45605 毫秒才能完成一个真实世界的输入文档(关于脚本编程的英文文本)。社区 wiki 答案中修改后的模板将运行时间降至 605 毫秒

我正在使用以下 XSLT 模板将字符串中的一些特殊字符替换为其转义变体;它使用分而治之的策略递归地调用自己,最终查看给定字符串中的每个字符。然后它决定是否应该按原样打印字符,或者是否需要任何形式的转义:

<xsl:template name="escape-text">
<xsl:param name="s" select="."/>
<xsl:param name="len" select="string-length($s)"/>
<xsl:choose>
    <xsl:when test="$len >= 2">
        <xsl:variable name="halflen" select="round($len div 2)"/>
        <xsl:variable name="left">
            <xsl:call-template name="escape-text">
                <xsl:with-param name="s" select="substring($s, 1, $halflen)"/>
                <xsl:with-param name="len" select="$halflen"/>
            </xsl:call-template>
        </xsl:variable>
        <xsl:variable name="right">
            <xsl:call-template name="escape-text">
                <xsl:with-param name="s" select="substring($s, $halflen + 1)"/>
                <xsl:with-param name="len" select="$halflen"/>
            </xsl:call-template>
        </xsl:variable>
        <xsl:value-of select="concat($left, $right)"/>
    </xsl:when>
    <xsl:otherwise>
        <xsl:choose>
            <xsl:when test="$s = '&quot;'">
                <xsl:text>&quot;\&quot;&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '@'">
                <xsl:text>&quot;@&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '|'">
                <xsl:text>&quot;|&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '#'">
                <xsl:text>&quot;#&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '\'">
                <xsl:text>&quot;\\&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '}'">
                <xsl:text>&quot;}&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '&amp;'">
                <xsl:text>&quot;&amp;&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '^'">
                <xsl:text>&quot;^&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '~'">
                <xsl:text>&quot;~&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '/'">
                <xsl:text>&quot;/&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '{'">
                <xsl:text>&quot;{&quot;</xsl:text>
            </xsl:when>
            <xsl:otherwise>
                <xsl:value-of select="$s"/>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:otherwise>
</xsl:choose>
</xsl:template>

这个模板占了我的 XSLT 脚本所需的大部分运行时间。将上面的escape-text模板替换为just

<xsl:template name="escape-text">
    <xsl:param name="s" select="."/>
    <xsl:value-of select="$s"/>
</xsl:template>

使我的 XSLT 脚本的运行时间在我的一个文档上从 45 秒缩短到不到 1 秒。

因此我的问题是:我怎样才能加快我的escape-text模板?我正在使用xsltproc,我更喜欢纯 XSLT 1.0 解决方案。XSLT 2.0 解决方案也将受到欢迎。但是,外部库可能对这个项目没有用——尽管我仍然对使用它们的任何解决方案感兴趣。

4

8 回答 8

16

translate($s, $vChars, '') = $s如果条件为真,另一种(补充)策略是在字符串长度降至 1 之前提前终止递归。这应该可以更快地处理根本不包含特殊字符的字符串,这可能是其中的大多数。当然,结果将取决于 xsltproc 的执行效率如何translate()

于 2010-08-24T20:38:56.977 回答
7

一个非常小的修正将我的测试速度提高了大约 17 倍

还有其他改进,但我想现在就足够了...... :)

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:my="my:my">
 <xsl:output omit-xml-declaration="yes" indent="yes"/>
 <xsl:strip-space elements="*"/>

 <xsl:variable name="vChars">"@|#\}&amp;^~/{</xsl:variable>

 <xsl:template match="node()|@*">
  <xsl:copy>
   <xsl:apply-templates select="node()|@*"/>
  </xsl:copy>
 </xsl:template>

 <xsl:template match="text()" name="escape-text">
  <xsl:param name="s" select="."/>
  <xsl:param name="len" select="string-length($s)"/>

  <xsl:choose>
    <xsl:when test="$len >= 2">
        <xsl:variable name="halflen" select="round($len div 2)"/>
        <xsl:variable name="left">
            <xsl:call-template name="escape-text">
                <xsl:with-param name="s" select="substring($s, 1, $halflen)"/>
                <xsl:with-param name="len" select="$halflen"/>
            </xsl:call-template>
        </xsl:variable>
        <xsl:variable name="right">
            <xsl:call-template name="escape-text">
                <xsl:with-param name="s" select="substring($s, $halflen + 1)"/>
                <xsl:with-param name="len" select="$halflen"/>
            </xsl:call-template>
        </xsl:variable>
        <xsl:value-of select="concat($left, $right)"/>
    </xsl:when>
    <xsl:otherwise>
        <xsl:choose>
            <xsl:when test="not(contains($vChars, $s))">
             <xsl:value-of select="$s"/>
            </xsl:when>
            <xsl:when test="$s = '&quot;'">
                <xsl:text>&quot;\&quot;&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '@'">
                <xsl:text>&quot;@&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '|'">
                <xsl:text>&quot;|&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '#'">
                <xsl:text>&quot;#&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '\'">
                <xsl:text>&quot;\\&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '}'">
                <xsl:text>&quot;}&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '&amp;'">
                <xsl:text>&quot;&amp;&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '^'">
                <xsl:text>&quot;^&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '~'">
                <xsl:text>&quot;~&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '/'">
                <xsl:text>&quot;/&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '{'">
                <xsl:text>&quot;{&quot;</xsl:text>
            </xsl:when>
        </xsl:choose>
    </xsl:otherwise>
</xsl:choose>
</xsl:template>
</xsl:stylesheet>
于 2010-08-24T16:59:42.243 回答
4

这是一个更改进的版本,基于@Dimitre 的回答:

  <xsl:template match="text()" name="escape-text">
    <xsl:param name="s" select="."/>
    <xsl:param name="len" select="string-length($s)"/>

    <xsl:choose>
      <xsl:when test="$len &gt; 1">
        <xsl:variable name="halflen" select="round($len div 2)"/>
        <!-- no "left" and "right" variables necessary! -->
        <xsl:call-template name="escape-text">
          <xsl:with-param name="s" select="substring($s, 1, $halflen)"/>
        </xsl:call-template>
        <xsl:call-template name="escape-text">
          <xsl:with-param name="s" select="substring($s, $halflen + 1)"/>
        </xsl:call-template>
      </xsl:when>
      <xsl:otherwise>
        <xsl:choose>
          <xsl:when test="not(contains($vChars, $s))">
            <xsl:value-of select="$s"/>
          </xsl:when>
          <xsl:when test="contains('\&quot;', $s)">
            <xsl:value-of select="concat('&quot;\', $s, '&quot;')" />
          </xsl:when>
          <!-- all other cases can be collapsed, this saves some time -->
          <xsl:otherwise>
            <xsl:value-of select="concat('&quot;', $s, '&quot;')" />
          </xsl:otherwise>
        </xsl:choose>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

应该再快一点,但我没有对它进行基准测试。无论如何,它更短。;-)

于 2010-08-24T18:52:23.327 回答
3

对于它的价值,这是我当前版本的escape-text模板,其中包含了人们在回答我的问题时给出的大部分(优秀!)建议。作为记录,我的原始版本在我的示例 DocBook 文档上平均花费了大约 45605 毫秒。之后,运行时间在多个步骤中减少:

  • 与调用一起删除leftand变量将运行时间降低到 13052 毫秒;这种优化取自Tomalak 的回答rightconcat()
  • <xsl:choose>首先在内部元素中移动常见情况(即:给定字符不需要任何特殊转义)使运行时间进一步降低到 5812 毫秒。这种优化首先由 Dimitre 提出
  • 通过首先测试给定字符串是否包含任何特殊字符来提前中止递归,将运行时间降低到 612 毫秒。这种优化是由 Michael 提出的
  • 最后,在阅读了 Dimitre 在Tomalak 的回答中的评论后,我忍不住做了一个微优化:我将<xsl:value-of select="concat('x', $s, 'y')"/>调用替换为<xsl:text>x</xsl:text><xsl:value-of select="$s"/><xsl:text>y</xsl:text>. 这使运行时间达到了大约 606 毫秒(大约提高了 1%)。

最后,这个函数用了 606ms 而不是 45605ms。感人的!

<xsl:variable name="specialLoutChars">"@|#\}&amp;^~/{</xsl:variable>

<xsl:template name="escape-text">
    <xsl:param name="s" select="."/>
    <xsl:param name="len" select="string-length($s)"/>
    <xsl:choose>
        <!-- Common case optimization: 
             no need to recurse if there are no special characters -->
        <xsl:when test="translate($s, $specialLoutChars, '') = $s">
            <xsl:value-of select="$s"/>
        </xsl:when>
        <!-- String length greater than 1, use DVC pattern -->
        <xsl:when test="$len > 1">
            <xsl:variable name="halflen" select="round($len div 2)"/>
            <xsl:call-template name="escape-text">
                <xsl:with-param name="s" select="substring($s, 1, $halflen)"/>
                <xsl:with-param name="len" select="$halflen"/>
            </xsl:call-template>
            <xsl:call-template name="escape-text">
                <xsl:with-param name="s" select="substring($s, $halflen + 1)"/>
                <xsl:with-param name="len" select="$len - $halflen"/>
            </xsl:call-template>
        </xsl:when>
        <!-- Special character -->
        <xsl:otherwise>
            <xsl:text>&quot;</xsl:text>
            <!-- Backslash and quot need backslash escape -->
            <xsl:if test="$s = '&quot;' or $s = '\'">
                <xsl:text>\</xsl:text>
            </xsl:if>
            <xsl:value-of select="$s"/>
            <xsl:text>&quot;</xsl:text>
        </xsl:otherwise>
    </xsl:choose>
</xsl:template>
于 2010-08-24T21:19:30.857 回答
1

使用 EXSLT 怎么样?EXSLT中的 String 函数有一个名为replace的函数。我认为很多 XSLT 实现都支持它。

于 2010-08-24T17:56:41.387 回答
1

更新:我将其修复为实际工作;现在,这不是加速!

建立@Wilfred的答案......

在摆弄 EXSLT replace() 函数之后,我认为发布另一个答案很有趣,即使它对 OP 没有用。它可能对其他人有用。

由于算法很有趣:而不是这里工作的主要算法(进行二进制递归搜索,在每次递归时分成两半,每当第 2^n 个子字符串中没有特殊字符时进行修剪,并迭代选择特殊的当长度为 1 的字符串确实包含特殊字符时的字符),Jeni Tennison 的 EXSLT 算法将迭代放在外部循环中的一组搜索字符串上。因此在循环内部,一次只查找一个字符串,可以使用 substring-before()/substring-after() 对字符串进行分割,而不是盲目地对半分割。

[已弃用:我想这足以显着加快速度。我的测试显示,与@Dimitre的最新测试相比,速度提升了 2.94 倍(平均 230 毫秒对 676 毫秒)。] 我在 Oxygen XML 分析器中使用 Saxon 6.5.5 进行测试。作为输入,我使用了一个 7MB 的 XML 文档,该文档主要是一个文本节点,由有关javascript的网页 创建,重复。在我看来,这代表了 OP 试图优化的任务。我很想看看其他人通过他们的测试数据和环境得到什么结果。

依赖项

这使用了依赖于 exsl:node-set() 的替换的 XSLT 实现。看起来 xsltproc 支持这个扩展功能(可能是它的早期版本)。所以这对你来说可能是开箱即用的,@Frerich;对于其他处理器,就像对撒克逊人所做的那样。

但是,如果我们想要 100% 纯 XSLT 1.0,我认为修改此替换模板以在没有 exsl:node-set() 的情况下工作不会太难,只要第二个和第三个参数作为节点集而不是 RTF 传递.

这是我使用的代码,它调用了替换模板。大部分长度都被我创建搜索/替换节点集的冗长方式占用了......这可能会被缩短。(但是您不能进行搜索或替换节点属性,因为当前编写了替换模板。尝试将属性放在文档元素下时会出错。)

<xsl:stylesheet version="1.0" xmlns:str="http://exslt.org/strings"
    xmlns:foo="http://www.foo.net/something" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:import href="lars.replace.template.xsl"/>

    <foo:replacements>
        <replacement>
            <search>"</search>
            <replace>"\""</replace>
        </replacement>
        <replacement>
            <search>\</search>
            <replace>"\\"</replace>
        </replacement>
        <replacement>
            <search>@</search>
            <replace>"["</replace>
        </replacement>
        <replacement>
            <search>|</search>
            <replace>"["</replace>
        </replacement>
        <replacement>
            <search>#</search>
            <replace>"["</replace>
        </replacement>
        <replacement>
            <search>}</search>
            <replace>"}"</replace>
        </replacement>
        <replacement>
            <search>&amp;</search>
            <replace>"&amp;"</replace>
        </replacement>
        <replacement>
            <search>^</search>
            <replace>"^"</replace>
        </replacement>
        <replacement>
            <search>~</search>
            <replace>"~"</replace>
        </replacement>
        <replacement>
            <search>/</search>
            <replace>"/"</replace>
        </replacement>
        <replacement>
            <search>{</search>
            <replace>"{"</replace>
        </replacement>
    </foo:replacements>

    <xsl:template name="escape-text" match="text()" priority="2">
        <xsl:call-template name="str:replace">
            <xsl:with-param name="string" select="."/>
            <xsl:with-param name="search"
                select="document('')/*/foo:replacements/replacement/search/text()"/>
            <xsl:with-param name="replace"
                select="document('')/*/foo:replacements/replacement/replace/text()"/>
        </xsl:call-template>
    </xsl:template>

    <xsl:template match="node()|@*">
        <xsl:copy>
            <xsl:apply-templates select="node()|@*"/>
        </xsl:copy>
    </xsl:template>
</xsl:stylesheet>

导入的样式表原本就是这个

但是,正如@Frerich 指出的那样,这从未给出正确的输出!这应该教会我不要在不检查正确性的情况下发布性能数据!

我可以在调试器中看到它出错的地方,但我不知道 EXSLT 模板是否从未工作过,或者它是否在 Saxon 6.5.5 中不起作用......任何一个选项都会令人惊讶。

无论如何,EXSLT 的 str:replace() 被指定做的比我们需要的更多,所以我修改它以便

  • 要求输入参数已经是节点集
  • 因此,不需要 exsl:node-set()
  • 不按长度对搜索字符串进行排序(在此应用程序中,它们都是一个字符)
  • 当相应的搜索字符串为空时,不在每对字符之间插入替换字符串

这是修改后的替换模板:

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
   xmlns:str="http://exslt.org/strings">
   <!-- By Lars Huttar
    based on implementation of EXSL str:replace() by Jenni Tennison.
    http://www.exslt.org/str/functions/replace/str.replace.template.xsl
    Modified by Lars not to need exsl:node-set(), not to bother sorting
    search strings by length (in our application, all the search strings are of
    length 1), and not to put replacements between every other character
    when a search string is length zero.
    Search and replace parameters must both be nodesets.
    -->

   <xsl:template name="str:replace">
      <xsl:param name="string" select="''" />
      <xsl:param name="search" select="/.." />
      <xsl:param name="replace" select="/.." />
      <xsl:choose>
         <xsl:when test="not($string)" />
         <xsl:when test="not($search)">
            <xsl:value-of select="$string" />
         </xsl:when>
         <xsl:otherwise>
            <xsl:variable name="search1" select="$search[1]" />
            <xsl:variable name="replace1" select="$replace[1]" />

            <xsl:choose>
               <xsl:when test="contains($string, $search1)">
                  <xsl:call-template name="str:replace">
                     <xsl:with-param name="string"
                        select="substring-before($string, $search1)" />
                     <xsl:with-param name="search"
                        select="$search[position() > 1]" />
                     <xsl:with-param name="replace"
                        select="$replace[position() > 1]" />
                  </xsl:call-template>
                  <xsl:value-of select="$replace1" />
                  <xsl:call-template name="str:replace">
                     <xsl:with-param name="string"
                        select="substring-after($string, $search)" />
                     <xsl:with-param name="search" select="$search" />
                     <xsl:with-param name="replace" select="$replace" />
                  </xsl:call-template>
               </xsl:when>
               <xsl:otherwise>
                  <xsl:call-template name="str:replace">
                     <xsl:with-param name="string" select="$string" />
                     <xsl:with-param name="search"
                        select="$search[position() > 1]" />
                     <xsl:with-param name="replace"
                        select="$replace[position() > 1]" />
                  </xsl:call-template>
               </xsl:otherwise>
            </xsl:choose>
         </xsl:otherwise>
      </xsl:choose>
   </xsl:template>

</xsl:stylesheet>

这个更简单的模板的附带好处之一是您现在可以将属性用于搜索和替换参数的节点。这将使<foo:replacements>数据更紧凑,更易于阅读 IMO。

性能:使用这个修改后的模板,工作大约在 2.5 秒内完成,而我最近对主要竞争对手 @Dimitre 的 XSLT 1.0 样式表的测试需要 0.68 秒。所以这不是加速。但同样,其他人的测试结果与我有很大不同,所以我想听听其他人使用这个样式表得到了什么。

于 2010-08-26T02:52:21.040 回答
0

在@Frerich-Raabe 发布了一个社区 wiki 答案之后,该答案结合了迄今为止的建议并(在他的数据上)实现了 76 倍的加速——恭喜大家!!!

我忍不住不走得更远:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
 <xsl:variable name="specialLoutChars">"@|#\}&amp;^~/{</xsl:variable>

 <xsl:key name="kTextBySpecChars" match="text()"
  use="string-length(translate(., '&quot;@|#\}&amp;^~/', '') = string-length(.))"/>

 <xsl:template match="node()|@*">
  <xsl:copy>
   <xsl:apply-templates select="node()|@*"/>
  </xsl:copy>
 </xsl:template>

 <xsl:template match="text()[key('kTextBySpecChars', 'true')]" name="escape-text">
  <xsl:param name="s" select="."/>
  <xsl:param name="len" select="string-length($s)"/>

  <xsl:choose>
    <xsl:when test="$len >= 2">
        <xsl:variable name="halflen" select="round($len div 2)"/>
        <xsl:call-template name="escape-text">
            <xsl:with-param name="s" select="substring($s, 1, $halflen)"/>
            <xsl:with-param name="len" select="$halflen"/>
        </xsl:call-template>
        <xsl:call-template name="escape-text">
            <xsl:with-param name="s" select="substring($s, $halflen + 1)"/>
            <xsl:with-param name="len" select="$len - $halflen"/>
        </xsl:call-template>
    </xsl:when>
    <xsl:when test="$len = 1">
        <xsl:choose>
            <!-- Common case: the character at hand needs no escaping at all -->
            <xsl:when test="not(contains($specialLoutChars, $s))">
                <xsl:value-of select="$s"/>
            </xsl:when>
            <xsl:when test="$s = '&quot;' or $s = '\'">
                <xsl:text>&quot;\</xsl:text>
                <xsl:value-of select="$s"/>
                <xsl:text>&quot;</xsl:text>
            </xsl:when>
            <xsl:otherwise>
                <xsl:text>&quot;</xsl:text>
                <xsl:value-of select="$s"/>
                <xsl:text>&quot;</xsl:text>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:when>
  </xsl:choose>
 </xsl:template>
</xsl:stylesheet>

这种转换(根据我的数据)实现了 1.5 倍的进一步加速。所以总加速应该是100倍以上。

于 2010-08-24T21:39:02.767 回答
0

好的,我会加入。虽然没有优化 XSLT 1.0 版本那么有趣,但您确实说 XSLT 2.0 解决方案是受欢迎的,所以这是我的。

<xsl:stylesheet version="2.0"
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

    <xsl:template name="escape-text" match="text()" priority="2">
        <xsl:variable name="regex1">[@|#}&amp;^~/{]</xsl:variable>
        <xsl:variable name="replace1">"$0"</xsl:variable>
        <xsl:variable name="regex2">["\\]</xsl:variable>
        <xsl:variable name="replace2">"\\$0"</xsl:variable>
        <xsl:value-of select='replace(replace(., $regex2, $replace2),
                              $regex1, $replace1)'/>
    </xsl:template>

    <xsl:template match="node()|@*">
        <xsl:copy>
            <xsl:apply-templates select="node()|@*"/>
        </xsl:copy>
    </xsl:template>

</xsl:stylesheet>

这只是使用正则表达式 replace() 将 \ 或 " 分别替换为 "\" 或 "\"";与另一个正则表达式 replace() 组成,用引号将任何其他可转义字符括起来。

在我的测试中,这比 Dimitre 最新的 XSLT 1.0 产品的性能2 倍以上。(但我自己编写了测试数据,其他条件可能是特殊的,所以我想知道其他人的结果如何得到。)

为什么性能变慢?我只能猜测这是因为搜索正则表达式比搜索固定字符串要慢。

更新:使用分析字符串

根据@Alejandro 的建议,这里使用的是分析字符串:

<xsl:template name="escape-text" match="text()" priority="2">
    <xsl:analyze-string select="." regex='([@|#}}&amp;^~/{{])|(["\\])'>
        <xsl:matching-substring>
            <xsl:choose>
                <xsl:when test="regex-group(1)">"<xsl:value-of select="."/>"</xsl:when>
                <xsl:otherwise>"\<xsl:value-of select="."/>"</xsl:otherwise>
            </xsl:choose>
        </xsl:matching-substring>
        <xsl:non-matching-substring><xsl:value-of select="."/></xsl:non-matching-substring>
    </xsl:analyze-string>
</xsl:template>

虽然这似乎是一个好主意,但不幸的是它并没有给我们带来性能上的胜利:在我的设置中,它始终需要大约 14 秒才能完成,而上面的 replace() 模板需要 1 - 1.4 秒。称之为10-14 倍的减速。:-( 这表明在 XSLT 级别断开和连接大量大字符串比在内置函数中遍历大字符串两次要昂贵得多。

于 2010-08-25T19:27:04.393 回答