This is the mail archive of the
xsl-list@mulberrytech.com
mailing list .
Re: Ordering of Blocks based on Input/Output
- To: xsl-list at lists dot mulberrytech dot com
- Subject: Re: [xsl] Ordering of Blocks based on Input/Output
- From: Francis Norton <francis at redrice dot com>
- Date: Wed, 09 May 2001 10:38:14 +0100
- References: <20010508202705.31534.qmail@web12605.mail.yahoo.com>
- Reply-To: xsl-list at lists dot mulberrytech dot com
If it's performance we may need some input from Mr. Kay...
Dan Diebolt wrote:
>
> Thanks Francis. I will have to study this and compare it.
I'm afraid the comparison with my old one won't help much - I basically
re-wrote it in a slightly more polished style. (I thought it was
suspicious that I could write 32 lines of code that ran correctly first
time!)
> but I now have to start looking for the best implementation
> (fastest) as I have thousand upon thousand of nodes.
Here's what should be a slightly faster version, in that it minimises
the number of passes and node-set operations, and uses a key to speed up
the selection of relevent links. It goes about the same speed in saxon
but faster in msxsl - I think you need to do timings on a larger data
set to make these choices.
> The suggestion from Ingo to process in two passes is something
> I am strongly considering.
You could try something like
<block name="b3">
<depends-on>b1</depends-on>
<depends-on>b2</depends-on>
</block>
to avoid one node-set operation.
> I am still looking for more input (from Jeni?) so please feel
> free to comment on various approaches.
>
I can't see any way of improving the gross structure of *this* approach,
but you might well get mileage by tuning the node-set operations against
a large data set. Alternatively some smart person may have a totally
different approach?
Francis.
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"/>
<xsl:key name="into" match="/root/system/connect" use="input/@block"
/>
<xsl:template match="/">
<order>
<!-- call the order function with the parameters -->
<xsl:call-template name="order">
<xsl:with-param name="todo" select="/root/system/block/name"/>
</xsl:call-template>
</order>
</xsl:template>
<!-- recurse through this printing out one block at a time -->
<xsl:template name="order">
<xsl:param name="todo"/>
<!-- always need a terminate condition in recursive functions -->
<xsl:if test="count($todo) > 0">
<!-- links into todo -->
<xsl:variable name="into" select="key('into', $todo)"/>
<!-- find all blocks in $todo that have no inputs from the outputs
of any (other) block in $todo -->
<xsl:variable name="next" select="$todo[. !=
$into/output/@block]"/>
<!-- now copy them out -->
<xsl:copy-of select="$next"/>
<!-- now recurse with $next removed from $todo -->
<xsl:call-template name="order">
<xsl:with-param name="todo" select="$todo[count(. | $next) >
count($next)]"/>
</xsl:call-template>
</xsl:if>
</xsl:template>
</xsl:stylesheet>
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list