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

Re: [xsl] Increasing sequence ?


Subject: Re: [xsl] Increasing sequence ?
From: "Dimitre Novatchev dnovatchev@xxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>
Date: Sat, 28 Mar 2015 03:35:50 -0000

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.laun@xxxxxxxxx
<xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> 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.studer@xxxxxxxxxxx
> <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> 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@xxxxxxxxx
>> <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> 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.


Current Thread
Keywords