在 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. 你可以向我证明在此用例中， 方法明显比 方法更快。

您认为如何降低这个 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 个记录元素需要 80 毫秒。

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

对于 10000 个记录元素，花费的时间为 284 毫秒。

对于 100000 个记录元素，花费的时间为 1667 毫秒。

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

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

Answer 2

如果数据是按组预先排序的（如您的示例），您可以循环记录集并检查该记录的组是否与前面的记录组不同。如果组发生更改，您可以添加组标题。这将以 O(n) 时间复杂度执行。

Answer 3

您当前的算法：

for every [group] record
  for every [data] record
    // actions

我假设如果您对所有元素执行简单迭代并且

 for every [record]
       take [data]
       take [group]
       add [data] to [group]

对于组表示，您可以使用树或地图。

正如你所看到的，该算法的复杂度为 O(n)

Answer 4

推荐的分组方法是 XSLT 2.0 中的 xsl:for-each-group 和 XSLT 1.0 中的 Muenchian 分组。对于任何半像样的处理器，这两者都将具有 (n*log(n)) 性能。

或者您可以简单地将 "/table/record[group = $group]" 替换为对 key() 函数的调用。

如果您准备支付企业级 XSLT 处理器（例如 Saxon-EE）的费用，那么这些优化很可能会自动为您完成，因此您不必担心它们。