[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

[xsl] Re: Self-Recursive Templates that split, Performance tips?


Subject: [xsl] Re: Self-Recursive Templates that split, Performance tips?
From: David Rudel <fwqhgads@xxxxxxxxx>
Date: Wed, 12 Mar 2014 14:40:13 +0100

On the way back from the dentist, I figured that there is a rather
obvious solution to this sort of thing.

You can create a "queue" variable that stores "new instances to be done later".

In case it is not clear what I mean, using the AMOEBA example we would have:

<xsl:template name="AMOEBA">
<xsl:param name="queue" as="item()*"/>
<xsl:param name="location" as="xs:double+"/>
<xsl:param name="terrain" as="map(*)"/>

And then whenever you hit a situation where you need to split the
process, you add the new parameters to the $queue variable so that
they get processed whenever the current thread completes:

In the AMOEBA case, that might mean making the following call:
<xsl:call-template name="AMOEBA">
<xsl:with-param name="queue" select="(alternate_location,
alternate_terrain, $queue)"/>
<xsl:with-param name="location" select="new.location"/>
<xsl:with-param name="terrain" select="new.terrain"/>
</xsl:call-template>

where "alternate_location" and "alternate_terrain" are the inputs that
would be split off in the original example.

Then, when the current recursive process ends, you make a call with
starting info coming from the queue:

<xsl:call-template name="AMOEBA">
<xsl:with-param name="queue" select="tail(tail($queue))"/>
<xsl:with-param name="location" select="head($queue)"/>
<xsl:with-param name="terrain" select="head(tail($queue))"/>
</xsl:call-template>

-David


On Wed, Mar 12, 2014 at 12:43 PM, David Rudel <fwqhgads@xxxxxxxxx> wrote:
> I'm looking for any pointers on speeding up an algorithm that uses
> self-recursion, but the self-recursion can spawn multiple new
> instances.
>
> For example, imagine that the template AMOEBA is meant to model an
> amoeba walking around on a surface.
>
> AMOEBA is called with two parameters: a location indicating where the
> amoeba is and a map indicating the terrain:
>
> <xsl:template name="AMOEBA">
> <xsl:param name="location" as "xs:double+"/>
> <xsl:param name="Terrain" as "map(*)"/>
>
> And based on the location and terrain, the amoeba takes a new step,
> calling itself with the new location and a new terrain map. NOTE: the
> new terrain map is a slight modification of the old terrain map.
>
> But sometimes the Amoeba needs to split into two amoeba, so in some
> cases the AMOEBA template will actually need to call two separate
> versions of itself (with different locations and terrains).
>
> Any tips for how to accomplish this with as good performance as
> possible, given that it is impossible for both calls to be in tail
> position?
> -David
>
>
> --
>
> "A false conclusion, once arrived at and widely accepted is not
> dislodged easily, and the less it is understood, the more tenaciously
> it is held." - Cantor's Law of Preservation of Ignorance.



-- 

"A false conclusion, once arrived at and widely accepted is not
dislodged easily, and the less it is understood, the more tenaciously
it is held." - Cantor's Law of Preservation of Ignorance.


Current Thread