Re: [xsl] Re: topological sort

[Jeni Tennison <mail at jenitennison dot com>]

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