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

[Dimitre Novatchev <dnovatchev@xxxxxxxxx>]

I wanted to offer exactly that, but was in the bus to work at that moment :)

While this is an almost obvious solution, it isn't the only possible
way to linearize a graph.

This specific solution roughly corresponds to "depth-first-search", we
can also use "breadth-first-search", and there are probably multitude
of other linearizations.

When we are speaking about efficiency, this isn't only to avoid
stack-overflow. One can use multi-threading (limited) on a single
computer, or Hadoop -like algorithms if there are many computers
available.

One should always try to use memorization, or in simpler terms, caching.

Cheers,
Dimitre

On Wed, Mar 12, 2014 at 6:40 AM, David Rudel <fwqhgads@xxxxxxxxx> wrote:
> 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.
>



-- 
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
To avoid situations in which you might make mistakes may be the
biggest mistake of all
------------------------------------
Quality means doing it right when no one is looking.
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
-------------------------------------
To achieve the impossible dream, try going to sleep.
-------------------------------------
Facts do not cease to exist because they are ignored.
-------------------------------------
Typing monkeys will write all Shakespeare's works in 200yrs.Will they
write all patents, too? :)
-------------------------------------
I finally figured out the only reason to be alive is to enjoy it.