Re: Re: topological sort

Hi Joerg,

> Xalan shows a small but overall insignificant improvment. Some trace
> messages indicate that the transformation time is dominated by other
> processing steps, but even the step processing the structure
> definitions is not much faster.

It might be that Xalan isn't optimising the test. Anyway, I took
another look and it might be that you can make this more efficient:

  <xsl:if test="count(struct)>count($processed)">
    <xsl:variable name="nextnodes"
       select="struct[not($processed/name=name)
                  and not(field/type/ref[not(. = $processed/name)])]"/>
    <xsl:if test="$nextnodes">
      <xsl:call-template name="process">
        <xsl:with-param name="nodes" select="$nextnodes"/>
        <xsl:with-param name="finished" select="$processed"/>
      </xsl:call-template>
    </xsl:if>
  </xsl:if>

The outer xsl:if tests whether the number of struct elements is equal
to the number of processed elements.  Given that there's a one-to-one
correspondence between structs and processed structs, then this will
be false only if all structs are processed.  Note that this expression
is quite processor intensive.  Each iteration, the processor has to
count all the struct nodes in the document, count all the processed
nodes, and compare those two values.  One way that you could make it
more efficient is to store the number of struct nodes in a global
variable:

<xsl:variable name="nStructs" select="count(structs)" />

and refer to that instead:

  <xsl:if test="$nStructs &gt; count($processed)">
    ...
  </xsl:if>

but I don't think that's going far enough.

If you look at the $nextnodes variable definition, if all the structs
are processed, then $nextnodes will be an empty node set.  The inner
xsl:if tests whether $nextnodes is empty before doing anything.  I'm
pretty sure, therefore, that you can get rid of the outer xsl:if
altogether and retain the same logic: $nextnodes will sometimes be
constructed when it doesn't need to be, but that's better than
counting nodes in node sets every single time you recurse.

Does that make it any faster?

Jeni

---
Jeni Tennison
http://www.jenitennison.com/



 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list