当我使用 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)
现在会有很多选择:
- 我可以找到一个涉及映射和嵌套数据结构的 Java 解决方案。但我想提高我的 XSLT 技能,所以这实际上是最后的选择。
- 我可能忘记了 Xerces/Xalan/Exslt 中的一个很好的功能,它可以更好地处理分组
- 我也许可以为
/table/record/group
建立某种索引 - 你可以向我证明
<xsl:apply-templates/>
在此用例中,方法明显比<xsl:for-each/>
更快方法。
你怎么看这个O(n^2)
可以降低复杂性吗?
最佳答案
您可以只使用 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 分组更有效的解决方案。
关于java - 在 XSLT 中对记录进行分组时如何避免 O(n^2) 的复杂性?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8077106/