Wolfgang,
I haven't the sleight-of-hand with writing this lingo, but wouldn't it be
worthwhile to try and check the ascending
property by halving the sequence and looking at each part separately? When
splitting, the last item of the first half must be less than the first of
the second, and then call recursively for each of the halves. I don't know
whether it would be faster, but it should reduce the risk of stack overflow.
You are describing the classic form of Divide and Conquer recursion
(DVC). Yes, it reduces the maximum depth of the call stack from N to
log2(N).
The time complexity is O(N) only if count() is O(1), which isn't
generally true for any XSLT implementation.
If count() itself is O(N), then, I believe, the time complexity of the
DVC algorithm is O(N^2).
Also, as per my related message, DVC isn't applicable in its classic
form to sequences that have indefinite (unknown) or infinite length
(lazily generated). It is possible to adapt DVC to something called
chunking, which allows streaming -- and for this to work, it is
necessary that the XSLT processor handles correctly tail recursion.
Cheers,
Dimitre
On Fri, Mar 27, 2015 at 2:56 AM, Wolfgang Laun
wolfgang(_dot_)laun(_at_)gmail(_dot_)com
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> wrote:
Dimitre,
I haven't the sleight-of-hand with writing this lingo, but wouldn't it be
worthwhile to try and check the ascending
property by halving the sequence and looking at each part separately? When
splitting, the last item of the first half must be less than the first of
the second, and then call recursively for each of the halves. I don't know
whether it would be faster, but it should reduce the risk of stack overflow.
Cheers
Wolfgang
On 27 March 2015 at 10:37, 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)
--
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.
--~----------------------------------------------------------------
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
--~--