All said is correct.
I also think that the recursive function should qualify for guaranteed
streamable.
Is this correct?
As for Saxon not dealing in the best way with tail-recursion, I still
expect this issue to be fixed in the future -- would be very useful
and makes perfect sense.
Cheers,
Dimitre
On Fri, Mar 27, 2015 at 4:05 AM, Michael Kay mike(_at_)saxonica(_dot_)com
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> wrote:
What we're seeing here is that the best solution is radically influenced by
the optimization strategies within the processor.
Dimitre's recursive approach is only worth doing if the processor has
non-constant performance for an expression of the form sequence[$N] where $N
is an integer; that is, if sequences are implemented as linked lists rather
than arrays. Saxon will generally use an adaptive implementation where the
sequence is held as an array as soon as you start indexing into it, so the
non-recursive solution will work just fine. Other systems may differ.
Then, if you do use the recursive approach, you run into problems if the
processor doesn't do tail-call optimization. And if that's the case, you
need to consider a divide-and-conquer approach instead.
Michael Kay
Saxonica
mike(_at_)saxonica(_dot_)com
+44 (0) 118 946 5893
On 27 Mar 2015, at 09:36, Leo Studer leo(_dot_)studer(_at_)varioweb(_dot_)ch
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> wrote:
Dimitre
thanks, this is amazing. With Saxon EE in Oxygen 16.1 I get stack overflow
with 10000 ;-).
Can you compare the time with this solution?
declare namespace my = "my:my";
declare function my:increasing2($seq as xs:double*)as xs:boolean
{every $v in 1 to (count($seq)-1) satisfies ($seq[$v] lt $seq[$v+1])};
let $v:=(1 to 1000000) return (my:increasing2($v))
Cheers
Leo
On 27.03.2015, at 05:24, Dimitre Novatchev dnovatchev(_at_)gmail(_dot_)com
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> wrote:
Hi Leo,
I ran this with BaseX 7.8.2:
declare namespace my = "my:my";
declare function my:increasing($seq as xs:double*) as xs:boolean
{empty($seq[2])
or
$seq[1] lt $seq[2] and my:increasing(subsequence($seq, 2))
};
let $v:=(1 to 10000)
return my:increasing($v)
And here is the result (do note this below: - marking as ***tail
call***: my:increasing(fn:subsequence($seq_0, 2)) )
Total Time: 3.74ms (for 100 000 - long sequence the time was 17.77ms,
for 1 000 000 - long sequence the time was 207.56ms)
XSL-List info and archive
EasyUnsubscribe (by email)
XSL-List info and archive
EasyUnsubscribe (by email)
--~----------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
EasyUnsubscribe: http://lists.mulberrytech.com/unsub/xsl-list/1167547
or by email: xsl-list-unsub(_at_)lists(_dot_)mulberrytech(_dot_)com
--~--