java - 在 XSLT 中对记录进行分组时如何避免 O(n^2) 的复杂性？

Question

当我使用 XSL 将大量数据转换为 HTML 时，我经常遇到性能问题。这些数据通常只是几个大致为这种形式的非常大的表:

<table>
  <record>
    <group>1</group>
    <data>abc</abc>
  </record>
  <record>
    <group>1</group>
    <data>def</abc>
  </record>
  <record>
    <group>2</group>
    <data>ghi</abc>
  </record>
</table>

在转换过程中，我想像这样直观地对记录进行分组

+--------------+
| Group 1      |
+--------------+
|   abc        |
|   def        |
+--------------+
| Group 2      |
+--------------+
|   ghi        |
+--------------+

一个愚蠢的实现是这个(设置来自 http://exslt.org 。实际实现有点不同，这只是一个例子):

<xsl:for-each select="set:distinct(/table/record/group)">
  <xsl:variable name="group" select="."/>

  <!-- This access needs to be made faster : -->
  <xsl:for-each select="/table/record[group = $group]">
    <!-- Do the table stuff -->
  </xsl:for-each>
</xsl:for-each>

很容易看出这往往有 O(n^2)复杂。更糟糕的是，每条记录中都有很多字段。操作的数据可以达到几十MB，记录数可以达到5000条。最坏的情况下，每条记录都有自己的组和50个字段。更糟糕的是，还有另一个级别的分组，这使得 O(n^3)

现在会有很多选择:

1. 我可以找到一个涉及映射和嵌套数据结构的 Java 解决方案。但我想提高我的 XSLT 技能，所以这实际上是最后的选择。
2. 我可能忘记了 Xerces/Xalan/Exslt 中的一个很好的功能，它可以更好地处理分组
3. 我也许可以为 /table/record/group 建立某种索引
4. 你可以向我证明 <xsl:apply-templates/>在此用例中，方法明显比 <xsl:for-each/> 更快方法。

你怎么看这个O(n^2)可以降低复杂性吗？

Answer 1

您可以只使用 XSLT 1.0 中众所周知的 Muenchian 分组方法——无需探索已排序的数据和实现更复杂和更慢的算法:

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

 <xsl:key name="kGroupByVal" match="group" use="."/>

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

 <xsl:template match=
  "group
      [generate-id()
      =
       generate-id(key('kGroupByVal', .)[1])
      ]">
  <group gid="{.}">
   <xsl:apply-templates select="key('kGroupByVal', .)/node()"/>
  </group>
 </xsl:template>
 <xsl:template match="group/text()"/>
</xsl:stylesheet>

当此转换应用于您提供的文本(这甚至不是格式正确的 XML 文档!!!)在将其更正为格式正确后，

3 个record 元素需要 80 毫秒。

对于具有 1000 个 record 元素的相似文本，转换在 136 毫秒内完成。

对于 10000 个 record 元素，所用时间为 284 毫秒。

有 100000 个 record 元素，所用时间为 1667 毫秒。

观察到的复杂性显然是次线性的。

很难(如果可能的话)找到比 XSLT 1.0 中的 Muenchian 分组更有效的解决方案。