This is fascinating stuff, but the proof of the pudding is in the
eating: have you made any comparative performance measurements, using a
non-trivial input file?
Michael Kay
Software AG
home: Michael(_dot_)H(_dot_)Kay(_at_)ntlworld(_dot_)com
work: Michael(_dot_)Kay(_at_)softwareag(_dot_)com
-----Original Message-----
From: owner-xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com
[mailto:owner-xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com] On Behalf Of
Robbert van Dalen
Sent: 22 March 2003 21:07
To: xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com
Subject: [xsl] How efficient is DVC? - A grouping example
Hello all,
Everyone interested in efficient algorithms might be
interested in this 'article'. Note that I'm not used to write
articles so excuse me if I'm not making a point clearly.
All the code is free - copy it if you like.
Cheers,
RvD
_____________________________________________________________
ABSTRACT
Grouping without using the key() function is not very
difficult in practice. But to implement it efficiently is not
easy task. This article presents a modified Divide And
Conquer (DVC) algorithm to implement grouping. The algorithm
is not only useful for grouping, but may be generalised to
help improve other DVC algorithms.
INTRODUCTION
Muenchian grouping is by far the most efficient method to
group nodes with XSLT. But there are some situations when
Muenchian grouping can't be used, for example if you want to
group tree-fragments Tree-fragments are heavily used when
multiple passes are needed to compute a result with only one
stylesheet. However, you cannot use the key() function on
tree-fragments because XSLT doesn't allow you to (there is no
nodeset parameter)
PREREQUISITES
All examples are tested against XALAN. Make sure you always
include the following stylesheet header:
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
xmlns:xalan="http://xml.apache.org/xalan"; version="1.1"
exclude-result-prefixes="xalan">
GROUPING EXAMPLE
The following example will give you an idea of grouping
tree-fragments without using the key() function.
Input XML (taken from Michael Kay's book)
<cities>
<city name="Barcelona" country="Espana"/>
<city name="Paris" country="France"/>
<city name="Roma" country="Italia"/>
<city name="Madrid" country="Espana"/>
<city name="Milano" country="Italia"/>
<city name="Firenze" country="Italia"/>
<city name="Napoli" country="Italia"/>
<city name="Lyon" country="France"/>
</cities>
Stylesheet (partly copied from Michael Kay's book)
<xsl:template match="cities">
<xsl:variable name="sorted">
<xsl:for-each select="./city">
<xsl:sort select="@country"/>
<xsl:copy-of select="."/>
</xsl:for-each>
</xsl:copy-of>
<xsl:variable name="sorted-tree-fragment"
select="xalan:nodeset($sorted)/*"/>
<!-- Gets the groups -->
<xsl:variable name="groups">
<xsl:apply-templates select="$sorted-tree-fragment"/>
</xsl:variable>
<!-- Iterate through all the groups -->
<xsl:for-each select="xalan:nodeset($groups)/*">
<xsl:variable name="country" select="."/>
<xsl:copy>
<!-- Copy the nodes with the same country -->
<xsl:copy-of select="$sorted-tree-fragment[country =
$country]"/>
<xsl:copy-of select="@*"/>
</xsl:copy>
</xsl:for-each>
</xsl:template>
<xsl:template match="city">
<variable name="preceding" select="./preceding-sibling::*[1]"/>
<xsl:if test="not(./@country = $preceding/@country)">
<group id="{$preceding/@country}"/>
</xsl:if>
</xsl:template>
Output:
<group id="Espana">
<city name="Barcelona" country="Espana"/>
<city name="Madrid" country="Espana"/>
</group>
<group id="France">
<city name="Paris" country="France"/>
<city name="Lyon" country="France"/>
</group>
<group id="Italia">
<city name="Roma" country="Italia"/>
<city name="Milano" country="Italia"/>
<city name="Firenze" country="Italia"/>
<city name="Napoli" country="Italia"/>
</group>
This looks like a OK solution, but let's get a closer look on
what is going on.
1) First the cities are sorted on the @country attribute.
After this, cities that share the same @country value will be
following each other, which is a property we can exploit in step 2.
2) Then the template that matches city nodes will be called N
times if there are N cities to be grouped. For each city node
in the sorted set the 'following-sibling::*[1]' node(s) are
matched. If they're not equal, the city node will mark a new
group. As Michael Kay already pointed out in his book, the
efficiency of this approach depends on the implementation of
'following-sibling::*[1]'. If this expression has time
complexity O(1) then the overall time complexity of getting
all the groups will be O(N) (leaving sorting out of the equation).
3) Strangely enough, the last step is actually the most
problematic. Let's say the second step gave us 3 groups.
Then, for each group, the expression
'$sorted-tree-fragment[country = $country] will be evaluated
with time complexity O(N).
So, does this mean the overall time complexity will be 3*N =
O(N)? The answer is definitely no! It does hold for a small
number of groups, but if we have N/2 groups then time
complexity will be O(N^2). Selecting nodes with XPATH
expressions is usually OK, but in this example we want to
select the K cities that share the same @country value in
O(K) time, not
O(N) time.
So the question we really want to anwer is: 'how can we
efficiently select a subset of nodes without traversing them
all?'. The anwser is: 'this all depends on the selection
criterium.' Still, if the selection criterium isn't too
complex, we can still hope for a better solution. One
solution is that we don't use XPATH expressions to select
nodes, but rather walk through the nodes by using recursive calls.
GROUPING USING RECURSION
One idea to reduce time complexity of the previous example is
by slightly modifying the match='city' template:
<xsl:template match="city">
<variable name="preceding" select="./preceding-sibling::*[1]"/>
<xsl:choose>
<xsl:when test="not(./@country = $preceding/@country)">
<group id="{./@country}">
<xsl:copy-of select="."/>
<xsl:apply-templates name="./following-sibling::*[1]"/>
</group>
</xsl:when>
<xsl:otherwise>
<xsl:copy-of select="."/>
<xsl:apply-templates name="./following-sibling::*[1]"/>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
If we take the same input and use the following 'apply-templates'
<xsl:apply-templates match="xalan:nodeset($sorted)/*[1]"/>
...we get the following result.
<group id="Espana">
<city name="Barcelona" country="Espana"/>
<city name="Madrid" country="Espana"/>
<group id="France">
<city name="Paris" country="France"/>
<city name="Lyon" country="France"/>
<group id="Italia">
<city name="Roma" country="Italia"/>
<city name="Milano" country="Italia"/>
<city name="Firenze" country="Italia"/>
<city name="Napoli" country="Italia"/>
</group>
</group>
</group>
This is almost what we want. The following 'apply-templates'
will flatten the tree structure to return the same result as
the previous example.
<xsl:apply-templates select="xalan:nodeset($groups)"/>
<xsl:template match="group">
<xsl:copy>
<xsl:apply-templates select="./group"/>
<xsl:copy-of select="./city"/>
<xsl:copy-of select="@*"/>
</xsl:copy>
</xsl:template>
The time complexity of the recursive solution can be proven
to be O(N) but with the recursion depth also to be O(N).
Unfortunately, most XSLT implementations have a maximum
recursion depth (~1000) so this is not a general solution.
DVC AND THE BINARY TREE
Dimitre Novatchev was one of the first to mention Divide and
Conquer (DVC) algorithms to reduce recursion depth. Because
most XSLT implementations out there still do not support
tail-recursion elimination, DVC is the way to go if you want
to process a lot of nodes. The idea behind DVC is that to
attack a big problem, you should divide it into a number of
smaller problems. Not surprisingly, dividing a problem into
just 2 subproblems is enough to reduce recursion depth to be
O(log2(N)). The following example will give you an idea of
how this works:
The XML input:
<nodes>
<node v="1"/>
<node v="2"/>
<node v="3"/>
<node v="4"/>
<node v="5"/>
<node v="6"/>
<node v="7"/>
<node v="8"/>
</nodes>
The Stylesheet:
<xsl:template match="/">
<xsl:call-template name="partition">
<xsl:with-param name="nodes" select="//node"/>
</xsl:call-template>
</xsl:template>
<xsl:template name="partition">
<xsl:param name="nodes"/>
<xsl:variable name="half" select="floor(count($nodes) div 2)"/>
<b>
<xsl:choose>
<xsl:when test="count($nodes) <= 1">
<!-- There is only one node left: stop dividing problem -->
<xsl:copy-of select="$nodes"/>
</xsl:when>
<xsl:otherwise>
<!-- divide in first half of nodes (left) -->
<xsl:call-template name="partition">
<xsl:with-param name="nodes"
select="$nodes[position() <= $half]"/>
</xsl:call-template>
<!-- divide in second half of nodes (right) -->
<xsl:call-template name="partition">
<xsl:with-param name="nodes"
select="$nodes[position() > $half]"/>
</xsl:call-template>
</xsl:otherwise>
</xsl:choose>
</b>
</xsl:template>
The output:
<b>
<b>
<b>
<b>
<node v="1"/>
</b>
<b>
<node v="2"/>
</b>
</b>
<b>
<b>
<node v="3"/>
</b>
<b>
<node v="4"/>
</b>
</b>
</b>
<b>
<b>
<b>
<node v="5"/>
</b>
<b>
<node v="6"/>
</b>
</b>
<b>
<b>
<node v="7"/>
</b>
<b>
<node v="8"/>
</b>
</b>
</b>
</b>
The result is what is called a binary tree representation. At
first this representation doesn't seem all that useful. Later
we will see that specialised binary trees can be (re-)used to
implement almost any recursive function without exceeding the
maximum recursion depth.
Let's sum all the @v values with the use of the binary
(fragment) tree:
<xsl:template match="/"/>
<xsl:variable name="btree">
<xsl:call-template name="partition">
<xsl:with-param name="nodes" select="//node"/>
</xsl:call-template>
</xsl:variable>
<xsl:call-template name="sum-binary-tree">
<xsl:with-param name="bnode" select="xalan:nodeset($btree)/*"/>
</xsl:call-template>
</xsl:template>
<xsl:template name="sum-binary-tree">
<xsl:param name="bnode"/>
<xsl:choose>
<xsl:when test="$bnode/node">
<xsl:value-of select="$bnode/node/@v"/>
</xsl:when>
<xsl:otherwise>
<xsl:variable name="first">
<xsl:call-template name="sum-binary-tree">
<xsl:with-param name="bnode" select="$bnode/b[1]"/>
</xsl:call-template>
</xsl:variable>
<xsl:variable name="second">
<xsl:call-template name="sum-binary-tree">
<xsl:with-param name="bnode" select="$bnode/b[2]"/>
</xsl:call-template>
</xsl:variable>
<xsl:value-of select="$first + $second"/>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
This gives the result: 36
Let's analyse the partition template in terms of time
complexity. It's easy to prove that it is equal to the number
nodes being copied. The partition algorithm uses the XPATH
expression '$nodes[count() > $half]' to split the nodes in
half. This construction is almost exclusively used by all DVC
or 'chunk' algorithms including many of Dimitre Novatchev's
examples. But how about the number of nodes being copied? The
following table lists the number of nodes being copied for
each partition.
partition(1)
number of copies 1
partition(2)
number of copies
l: 1 + partition(1)
r: 1 + partition(1)
partition(4)
number of copies
l: 2 + partition(2)
r: 2 + partition(2)
partition(8)
number of copies
l: 4 + partition(4)
r: 4 + partition(4)
etc.
The number of copies when calling partition(4) is:
(2 + (1 + 1) + 2 + (1 + 1)) = 2*4
The number of copies when calling partition(8) is:
4 + (2 + (1 + 1) + 2 + (1 + 1)) + 4 + (2 + (1 + 1) + 2 + (1 +
1)) = 3*8
So the overall 'copy' complexity is O(log2(N)*N).
Although the number of recursive calls is O(N) the XSLT
processor still spends at least O(log2(N)*N) time because it
must copy (and select) half of the nodes for the each
recursive call (twice). Copying nodes should be avoided as
much as possible because it slows down recursion considerably.
MODIFIED DVC ALGORITHM: RANGE PARTITIONING
The following implementation of a binary partition doesn't
copy a list of nodes but just one node at each recursive
call. It uses the so called 'sibling' axis to walk through
the list. Because there are O(N) recursive calls, this means
that O(N) nodes are copied. Does this mean that the overall
time complexity will be O(N) too? The answer is: probably
yes, but at worst it will be O(N^2).
Input XML:
<nodes>
<node v="1"/>
<node v="2"/>
<node v="3"/>
<node v="4"/>
<node v="5"/>
<node v="6"/>
<node v="7"/>
<node v="8"/>
</nodes>
The Stylesheet:
<xsl:template match="/">
<xsl:call-template name="partition-ranges">
<xsl:with-param name="node" select="//node[1]"/>
</xsl:call-template>
</xsl:template>
<xsl:template name="partition-ranges">
<xsl:param name="node"/>
<xsl:param name="s"
select="(count($node/preceding-sibling::*)) + 1"/>
<xsl:param name="e"
select="(count($node/following-sibling::*)) + $s"/>
<xsl:if test="$node">
<xsl:element name="r">
<xsl:attribute name="s">
<xsl:value-of select="$s"/>
</xsl:attribute>
<xsl:attribute name="e">
<xsl:value-of select="$e"/>
</xsl:attribute>
<xsl:choose>
<xsl:when test="$s = $e">
<xsl:copy-of select="$node"/>
</xsl:when>
<xsl:otherwise>
<xsl:variable name="w" select="floor(($e - $s + 1) div 2)"/>
<xsl:variable name="m" select="$s + $w"/>
<xsl:call-template name="partition-ranges">
<xsl:with-param name="node" select="$node"/>
<xsl:with-param name="s" select="$s"/>
<xsl:with-param name="e" select="$m - 1"/>
</xsl:call-template>
<xsl:call-template name="partition-ranges">
<xsl:with-param name="node"
select="$node/following-sibling::*[$w]"/>
<xsl:with-param name="s" select="$m"/>
<xsl:with-param name="e" select="$e"/>
</xsl:call-template>
</xsl:otherwise>
</xsl:choose>
</xsl:element>
</xsl:if>
</xsl:template>
The output:
<r s="1" e="8">
<r s="1" e="4">
<r s="1" e="2">
<r s="1" e="1">
<node v="1"/>
</r>
<r s="2" e="2">
<node v="2"/>
</r>
</r>
<r s="3" e="4">
<r s="3" e="3">
<node v="3"/>
</r>
<r s="4" e="4">
<node v="4"/>
</r>
</r>
</r>
<r s="5" e="8">
<r s="5" e="6">
<r s="5" e="5">
<node v="5"/>
</r>
<r s="6" e="6">
<node v="6"/>
</r>
</r>
<r s="7" e="8">
<r s="7" e="7">
<node v="7"/>
</r>
<r s="8" e="8">
<node v="8"/>
</r>
</r>
</r>
</r>
Note that the output resembles the previous example but
instead of <b> nodes, <r> (Range) nodes are used. This just
makes it more convenient to select ranges of nodes later on.
The actual 'splitting' is done through the following
expression '[$node/following-sibling::*[$w]' with $w being
the lenght of the list divided by 2. Let's compare overall
time complexity with the possible implementations of
'following-sibling::[w]'
following-sibling::*[w] | total time
_____________________________________
O(1) | O(N)
O(w) | O(log2(N)*N)
O(N) | O(N^2)
So at worst it will be quadratic. So the question still
remains if it is theoretically possible to do binary
partitioning without copying to much nodes. Nevertheless,
experiments with XALAN have shown that the implementation is
not quadratic.
GROUPING WITH A BINARY TREE
The new and improved grouping algorithm is more or less the
same as the first one except where using ranges to select
nodes which are in the same group.
Thus:
1) we sort the nodes for a given key
2) then compute the ranges of nodes which have the same key
3) and then select the (sorted) nodes for each range.
To efficiently select a range of nodes we will be using the
binary tree.
Here's the whole solution:
Input XML:
<cities>
<city name="Barcelona" country="Espana"/>
<city name="Paris" country="France"/>
<city name="Roma" country="Italia"/>
<city name="Madrid" country="Espana"/>
<city name="Milano" country="Italia"/>
<city name="Firenze" country="Italia"/>
<city name="Napoli" country="Italia"/>
<city name="Lyon" country="France"/>
</cities>
The stylesheet (WARNING, THIS IS A BIT LENGHTY):
<!-- Group cities on country -->
<xsl:template match="/">
<xsl:call-template name="group-on-key">
<xsl:with-param name="nodes" select="//city"/>
<xsl:with-param name="key" select="'country'"/>
</xsl:call-template>
</xsl:template>
<!--
Template: group-on-key
Use this template to group <nodes> which share a common
attribute <key>
The result will be sub-sets of <nodes> surrounded by <group/> tags
-->
<xsl:template name="group-on-key">
<xsl:param name="nodes"/>
<xsl:param name="key"/>
<xsl:variable name="items">
<xsl:for-each select="$nodes">
<item>
<key>
<xsl:value-of select="./@*[name() = $key]"/>
</key>
<value>
<xsl:copy-of select="."/>
</value>
</item>
</xsl:for-each>
</xsl:variable>
<xsl:variable name="grouped-items">
<xsl:call-template name="group-on-item">
<xsl:with-param name="nodes" select="xalan:nodeset($items)/*"/>
<xsl:with-param name="key" select="$key"/>
</xsl:call-template>
</xsl:variable>
<xsl:for-each select="xalan:nodeset($grouped-items)/*">
<xsl:copy>
<xsl:for-each select="./*">
<xsl:copy-of select="./value/*[1]"/>
</xsl:for-each>
</xsl:copy>
</xsl:for-each>
</xsl:template>
<!--
Template: group-on-item
Use this template to group <nodes> which share a common
structure. You can build this structure yourself if you want
to group on something else
The structure is the <item> structure and has the following
layout <item>
<key>
aKey (can be anything, preferrably a string)
</key>
<value>
aValue (can be anything, probably a node(set))
</value>
</item>
<items> will we grouped on the string value of <key>
The result will be sub-sets of <items> surrounded by <group/> tags
-->
<xsl:template name="group-on-item">
<xsl:param name="nodes"/>
<!-- Step 1 -->
<xsl:variable name="sorted">
<xsl:for-each select="$nodes">
<xsl:sort select="./key[1]/"/>
<xsl:copy-of select="."/>
</xsl:for-each>
</xsl:variable>
<xsl:variable name="sorted-tree" select="xalan:nodeset($sorted)/*"/>
<!-- Step 2.1 -->
<xsl:variable name="pivots">
<xsl:call-template name="pivots">
<xsl:with-param name="nodes" select="$sorted-tree"/>
</xsl:call-template>
</xsl:variable>
<!-- Step 2.2 -->
<xsl:variable name="ranges">
<xsl:call-template name="ranges">
<xsl:with-param name="pivots"
select="xalan:nodeset($pivots)/*"/>
<xsl:with-param name="length" select="count($sorted-tree)"/>
</xsl:call-template>
</xsl:variable>
<!-- Step 3.1 -->
<xsl:variable name="partition-ranges">
<xsl:call-template name="partition-ranges">
<xsl:with-param name="node" select="$sorted-tree[1]"/>
</xsl:call-template>
</xsl:variable>
<xsl:variable name="root-partition"
select="xalan:nodeset($partition-ranges)/*[1]"/>
<!-- Step 3.2 -->
<xsl:for-each select="xalan:nodeset($ranges)/r">
<xsl:variable name="s" select="./@s"/>
<xsl:variable name="e" select="./@e"/>
<group>
<xsl:call-template name="range-in-partition">
<xsl:with-param name="s" select="$s"/>
<xsl:with-param name="e" select="$e"/>
<xsl:with-param name="p" select="$root-partition"/>
</xsl:call-template>
</group>
</xsl:for-each>
</xsl:template>
<xsl:template name="pivots">
<xsl:param name="nodes"/>
<xsl:param name="key"/>
<xsl:for-each select="$nodes">
<xsl:if test="not(string(./key[1]/) =
string(./following-sibling::*[1]/key[1]/))">
<pivot>
<xsl:value-of select="position()"/>
</pivot>
</xsl:if>
</xsl:for-each>
</xsl:template>
<xsl:template name="ranges">
<xsl:param name="pivots" select="../"/>
<xsl:param name="length" select="0"/>
<xsl:choose>
<xsl:when test="count($pivots) >= 1">
<xsl:for-each select="$pivots">
<xsl:variable name="p" select="./preceding-sibling::*[1]"/>
<r>
<xsl:attribute name="s">
<xsl:choose>
<xsl:when test="$p">
<xsl:value-of select="$p + 1"/>
</xsl:when>
<xsl:otherwise>
<xsl:value-of select="1"/>
</xsl:otherwise>
</xsl:choose>
</xsl:attribute>
<xsl:attribute name="e">
<xsl:value-of select="string(.)"/>
</xsl:attribute>
</r>
</xsl:for-each>
</xsl:when>
<xsl:otherwise>
<r>
<xsl:attribute name="s">
<xsl:value-of select="1"/>
</xsl:attribute>
<xsl:attribute name="e">
<xsl:value-of select="$length"/>
</xsl:attribute>
</r>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
<!--
Template: range-in-partition
Selects a RANGE of nodes using a binary tree
XSLT isn't really helping to make things easy but try to do
this in a DVC style directly without the help of a binary tree.
-->
<xsl:template name="range-in-partition">
<xsl:param name="p"/>
<xsl:param name="s" select="$p/@s"/>
<xsl:param name="e" select="$p/@e"/>
<xsl:variable name="ps" select="number($p/@s)"/>
<xsl:variable name="pe" select="number($p/@e)"/>
<xsl:if test="$s <= $pe and $e >= $ps">
<xsl:if test="$ps = $pe">
<xsl:copy-of select="$p/*[1]"/>
</xsl:if>
<xsl:choose>
<xsl:when test="$s > $ps">
<xsl:variable name="s1" select="$s"/>
<xsl:choose>
<xsl:when test="$e < $pe">
<xsl:variable name="e1" select="$e"/>
<xsl:for-each select="$p/*">
<xsl:call-template name="range-in-partition">
<xsl:with-param name="s" select="$s1"/>
<xsl:with-param name="e" select="$e1"/>
<xsl:with-param name="p" select="."/>
</xsl:call-template>
</xsl:for-each>
</xsl:when>
<xsl:otherwise>
<xsl:variable name="e1" select="$pe"/>
<xsl:for-each select="$p/*">
<xsl:call-template name="range-in-partition">
<xsl:with-param name="s" select="$s1"/>
<xsl:with-param name="e" select="$e1"/>
<xsl:with-param name="p" select="."/>
</xsl:call-template>
</xsl:for-each>
</xsl:otherwise>
</xsl:choose>
</xsl:when>
<xsl:otherwise>
<xsl:variable name="s1" select="$ps"/>
<xsl:choose>
<xsl:when test="$e < $pe">
<xsl:variable name="e1" select="$e"/>
<xsl:for-each select="$p/*">
<xsl:call-template name="range-in-partition">
<xsl:with-param name="s" select="$s1"/>
<xsl:with-param name="e" select="$e1"/>
<xsl:with-param name="p" select="."/>
</xsl:call-template>
</xsl:for-each>
</xsl:when>
<xsl:otherwise>
<xsl:variable name="e1" select="$pe"/>
<xsl:for-each select="$p/*">
<xsl:call-template name="range-in-partition">
<xsl:with-param name="s" select="$s1"/>
<xsl:with-param name="e" select="$e1"/>
<xsl:with-param name="p" select="."/>
</xsl:call-template>
</xsl:for-each>
</xsl:otherwise>
</xsl:choose>
</xsl:otherwise>
</xsl:choose>
</xsl:if>
</xsl:template>
Output XML:
<group>
<city name="Barcelona" country="Espana"/>
<city name="Madrid" country="Espana"/>
</group>
<group>
<city name="Paris" country="France"/>
<city name="Lyon" country="France"/>
</group>
<group>
<city name="Roma" country="Italia"/>
<city name="Milano" country="Italia"/>
<city name="Firenze" country="Italia"/>
<city name="Napoli" country="Italia"/>
</group>
CONCLUSION
An efficient DVC algorithm is given for grouping using a
binary tree. That binary trees can be build with time
complexity O(N) and 'copy' complexity O(N) - without relying
to much on implementations - is still an open question.
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list