5

当我通过 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)降低这种复杂性？

4

4 回答 4

4

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

于 2011-11-10T09:28:28.893 回答
4

您可以只使用 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 个元素需要 80 毫秒。

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

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

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

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

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

于 2011-11-10T13:56:29.447 回答
2

您当前的算法：

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

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

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

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

如您所见，该算法的复杂度为 O(n)

于 2011-11-10T09:15:41.070 回答
2

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

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

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

于 2011-11-10T12:17:48.537 回答