在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 文档！！！）并将其更正为格式良好后，

record3个元素需要80ms。

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

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

对于 100000 个record元素，所需时间为 1667ms。

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

在 XSLT 1.0 中找到比 Muenchian 分组更有效的解决方案是非常困难的（如果可能的话）。