[XSL-LIST Mailing List Archive Home]
[By Thread]
[By Date]
Re: [xsl] Re: topological sort
Subject: Re: [xsl] Re: topological sort From: Jeni Tennison <mail@xxxxxxxxxxxxxxxx> Date: Mon, 8 Jan 2001 11:42:33 +0000 |
Hi Joerg, Sorry to batter on at this. Here's a thought. When you're selecting the $nextnodes for processing, you're having to go through all of the 'struct' elements, checking whether they've been processed and whether all their field/type/ref descendents have been processed: struct[not($processed/name=name) and not(field/type/ref[not(. = $processed/name)])] Now, at this point, the only structs that can possibly suddenly be processed now rather than having been processed ages ago are those who have a field/type/ref that refers to a struct that has just been processed. In other words, the $nodes that have just been processed have to be in the set of the field/type/refs of the structs that can now be processed. So, rather than search for 200+ structs each time, you could just focus on those that have field/type/refs with the same value as the names of the $nodes that are being processed during this iteration: struct[field/type/ref = $nodes/name and not($processed/name = name) and not(field/type/ref[not(. = $processed/name)])] Adding it as a predicate like this probably buys you very little, and will probably actually make things worse. But, because you're testing *for* something rather than for *not* something, you can change the test into a call to key(), which may well make it faster. So, you can index the structs based on the field/type/refs that they have: <xsl:key name="structs" match="struct" use="field/type/ref" /> Now, if I do key('structs', 'A') then I'll get all the structs that have a field/type/ref with a value of 'A'. More importantly if I do: key('structs', {'A', 'B', 'C'}) where {'A', 'B', 'C'} is a node set of nodes with values 'A', 'B' and 'C', then I'll get all the structs that have field/type/refs with values of 'A', 'B' or 'C'. So, if I do: key('structs', $nodes/name) then I'll get all those structs who have field/type/refs with that name. What this boils down to is: try adding the key definition to your stylesheet: <xsl:key name="structs" match="struct" use="field/type/ref" /> Then, use the following to define your $nextnodes variable. <xsl:variable name="nextnodes" select="key('structs', $nodes/name) [not($processed/name=name) and not(field/type/ref[not(. = $processed/name)])]" /> Another thought is rather than keeping track of which nodes *have* been processed, you could keep track of which nodes *haven't* been processed. <xsl:template match="structs"> <xsl:call-template name="process"> <xsl:with-param name="nodes" select="struct[not(field/type/ref)]"/> <xsl:with-param name="todo" select="struct[field/type/ref]"/> </xsl:call-template> </xsl:template> <xsl:template name="process"> <xsl:param name="nodes"/> <xsl:param name="todo"/> <xsl:for-each select="$nodes"> <xsl:value-of select="name"/> </xsl:for-each> <xsl:if test="$todo"> <xsl:variable name="nextnodes" select="$todo[not(field/type/ref[. = $todo/name])]"/> <xsl:if test="$nextnodes"> <xsl:call-template name="process"> <xsl:with-param name="nodes" select="$nextnodes"/> <xsl:with-param name="todo" select="$todo[not(name = $nextnodes/name)]"/> </xsl:call-template> </xsl:if> </xsl:if> </xsl:template> With this solution it might just be more efficient to define a key to split the structs into those with field/type/refs and those without: <xsl:key name="referencing-structs" match="struct" use="boolean(field/type/ref)" /> <xsl:template match="structs"> <xsl:call-template name="process"> <xsl:with-param name="nodes" select="key('referencing-structs', false())" /> <xsl:with-param name="todo" select="key('referencing-structs', true())" /> </xsl:call-template> </xsl:template> Anyway, just some ideas. I'd really appreciate it if you let me know their effects - it's really useful to know which supposed optimisations fall flat on their faces. Cheers, Jeni --- Jeni Tennison http://www.jenitennison.com/ XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Re: topological sort, Joerg Pietschmann | Thread | Re: [xsl] Re: topological sort, Joerg Pietschmann |
Re: [xsl] DTD Problem, Richard Light | Date | Possible new key() function (Was: R, Dimitre Novatchev |
Month |