[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Re: Increasing sequence ?
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.
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|