5

XSLで大量のデータをHTMLに変換すると、パフォーマンスの問題が頻繁に発生します。このデータは通常、おおよそこの形式の非常に大きなテーブルのほんの2、3です。

<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

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は、変換は 136ms で終了します。

10000record要素の場合、所要時間は 284msです。

100000record要素の場合、所要時間は 1667msです。

観察された複雑さは明らかにサブリニアです。

XSLT 1.0 で Muenchian グループ化よりも効率的なソリューションを見つけることは (可能であれば) 非常に困難です。

于 2011-11-10T13:56:29.447 に答える
4

データがグループごとに事前に並べ替えられている場合 (例のように)、レコード セットをループして、レコードのグループが前のレコード グループと異なるかどうかを確認できます。グループが変更された場合は、グループ ヘッダーを追加できます。これは O(n) 時間の複雑さで実行されます。

于 2011-11-10T09:28:28.893 に答える
2

推奨されるグループ化方法は、XSLT 2.0のxsl：for-each-group、およびXSLT1.0のMuenchianグループ化です。中途半端なプロセッサでは、どちらも（n * log（n））のパフォーマンスを発揮します。

"/table/record[group = $group]"または、単にkey（）関数の呼び出しに置き換えることもできます。

Saxon-EEなどのエンタープライズクラスのXSLTプロセッサを購入する準備ができている場合は、これらの最適化が自動的に行われる可能性が高いため、心配する必要はありません。

于 2011-11-10T12:17:48.537 に答える
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 に答える