I encountered this recently, when I had to retool a str:rtrim template to use
bisection because the previous step-through-the-whitespace method was bombing
out on large data sets.
Out of curiosity, has anyone thought about a bisection approach for str:replace
(XSLT 1.0)? I was able to use bisection for my str:rtrim template, but only
because the character I was looking for (' ') was only one character long. Is
it possible to use bisection when searching for a dynamic-length string in the
subject string? The basic problem theoretically is that you don't want to
bisect the subject string at a point that's in the middle of an occurrence of
the search string.
I suppose it's possible if you tweak the basic bisection algorithm - one idea I
had was to check for contains(substring($subject, string-length($subject) / 2 -
string-length($search), string-length($subject) / 2 - string-length($search)))
before splitting the string at string-length($subject) / 2; my assumption is
that you'll never split an occurrence of the search string if you check a
sufficiently wide string surrounding the search area. I also suppose that you'd
be able to optimize the conditions for where you'd stop searching, based on the
length of the search string.
Basically, it sounds like there are some potential improvements to be made, but
I wouldn't want to do them myself if someone else has already done them. :) I'm
also guessing that the fundamental pattern in str:replace is one that would be
optimized for tail recursion pretty quickly, so I don't know if there's even
any potential gain to be had here.
Any thoughts?
~ Scott
-----Original Message-----
From: Dimitre Novatchev [mailto:dnovatchev(_at_)gmail(_dot_)com]
Sent: Thursday, March 01, 2012 3:23 PM
To: xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com
Subject: Re: [xsl] What is the Maximum number of recurssions
On Thu, Mar 1, 2012 at 12:36 PM, Karl Stubsjoen <kstubs(_at_)gmail(_dot_)com>
wrote:
I'm just curious, what is the maximum number of times a template can
recurse?
I guess you men the number of nested recursive calls (nestedness).
There is no fixed maximum and in some cases a correctly written
template/function can have nestedness measured in the millions.
Such are the cases with tail-recursive functions/templates -- and this requires
that the XSLT processor can recognize and optimize tail recursion.
For example, this transformation run with Saxon 6.5.4 successfully prints all
numbers from 1 to one million:
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform";>
<xsl:output omit-xml-declaration="yes" indent="yes"/>
<xsl:template match="/">
<xsl:call-template name="printToN"/>
</xsl:template>
<xsl:template name="printToN">
<xsl:param name="pUpTo" select="1000000"/>
<xsl:param name="pDoneWith" select="0"/>
<xsl:if test="$pUpTo > $pDoneWith">
<xsl:value-of select="$pDoneWith+1"/>
<xsl:text>
</xsl:text>
<xsl:call-template name="printToN">
<xsl:with-param name="pUpTo" select="$pUpTo"/>
<xsl:with-param name="pDoneWith" select="$pDoneWith+1"/>
</xsl:call-template>
</xsl:if>
</xsl:template>
</xsl:stylesheet>
However, other XSLT processors (AltovaXML) produce this error: "XSLT
instruction stack overflow"
A DVC (Divide and Conquer) style recursion is also a practical solution and
processing a sequence of N items requires a maximum nestedness of only log(N).
This recursive style is remarkable in that it doesn't require (as required in
the case of tail recursion) any special abilities from the XSLT processor and
works correctly with any XSLT processor. Thus the maximum callstack depth when
processing a sequence of one million items with DVC-style recursion, is only 19.
I would imagine it would be different from engine to engine.
Is there any other engine intelligence at play here, for example the
engine has decided that you've written and endless looping recursion,
instead of one that knows you'll eventually reach the end of your
source xml?
This is generally impossible to do, because whether or not an algorithm
finishes often depends on the specific data that is fed to it -- typical
examples are many numerical methods that converge only if the data is limited
in a specific interval or by any other condition.
Cheers,
Dimitre.
Thanks,
Karl..
--
Karl Stubsjoen
MeetScoresOnline.com
(602) 845-0006
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
--
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
-------------------------------------
Facts do not cease to exist because they are ignored.
-------------------------------------
I finally figured out the only reason to be alive is to enjoy it.
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--