Как избежать сложности O (n ^ 2) при группировке записей в XSLT?

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).Еще хуже, поскольку в каждой записи много полей.Используемые данные могут достигать нескольких десятков МБ, а количество записей - до 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 можно просто использовать известный метод группирования по мюнхенскому принципу - не нужно исследовать отсортированные данные и реализовывать более сложные и медленные алгоритмы:

<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-документ !!!) после исправления его до правильности,

требуется 80 мс для 3 record элементов .

При аналогичном тексте, содержащем 1000 record элементов, преобразование заканчивается за 136 мс .

С элементами 10000 record время составляет 284 мс .

С элементами 100000 record время составляет 1667 мс .

Наблюдаемая сложность явно сублинейна.

Было бы очень трудно (если вообще возможно) найти более эффективное решение, чем группировка Мюнхена в XSLT 1.0.

Answer 2

Если данные предварительно отсортированы по группам (как в вашем примере), вы можете зациклить набор записей и проверить, отличается ли группа записей от предыдущей группы записей.Если группа изменяется, вы можете добавить заголовок группы.Это будет выполнено в O (n) времени сложности.

Answer 3

Рекомендуемые методы группировки: xsl: for-each-group в XSLT 2.0 и мюнхенская группировка в XSLT 1.0. При использовании любого полуприличного процессора у обоих будет (n * log (n)) производительность.

Или вы можете просто заменить "/table/record[group = $group]" вызовом функции key ().

Если вы готовы платить за процессор XSLT корпоративного класса, такой как Saxon-EE, есть большая вероятность, что эти оптимизации будут выполнены автоматически, поэтому вам не придется о них беспокоиться.

Answer 4

Ваш текущий алгоритм:

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

Я предполагаю, что если вы выполняете простую итерацию по всем элементам и

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

Для представления группы вы можете использовать деревья или карты.

Как видите, этот алгоритм имеет сложность O (n)