Re: Re: lookup-table thoughts (was Re: matching multip

> Were the task to perform some data reduction rather than to append
> strings together, no doubt Divid and Conquer would show more favorable
> timing results.

And it will be lightning-fast compared to the other implementations on a
multiprocessor parallel execution environment.

>From my experience, DVC always wins in the long run (typically for lists longer than
1600 - 2000), even when the problem is not too "clean" and requires complicated
sunchronisation/re-combination of the two partial results. 

Therefore, if Jeny continues her benchmarking just for a few more lines down her
table, the DVC will overtake the simple algorithm.

Also, Tom Mayer's DVC implementation should be (obviously) faster than the one I
provided.

Cheers,
Dimitre Novatchev.

--- Mark Nahabedian <naha@xxxxxxxxxx> wrote:
> 
> I don't recall anyone yet comming straight out and saying this yet in
> this thread, so I will.
> 
> It's clear that any performance gained in this problem by decreasing
> the number of template calls is being swamped by a much greater
> increase in storage allocation and copying overhead brought about by
> the restructuring of the stylesheet for a particular recursion
> mechanism.
> 
> Were the task to perform some data reduction rather than to append
> strings together, no doubt Divid and Conquer would show more favorable
> timing results.
> 
> 
> Jeni Tennison writes:
>  > Dimitre,
>  > 
>  > > Is this what you wished? I'm afraid it's performance seems to be no
>  > > better than O(N*N), hope I'm wrong.
>  > 
>  > I altered it slightly to take advantage of Saxon's XSLT 1.1 support
>  > (rather than use msxsl:node-set()). Here's the amended table (the
>  > measurements might be a little off because of a different test
>  > stylesheet, but the pattern is evident):
>  > 
>  > count   Tail Recursive      Not Tail Recursive  Divide And Conquer
>  > 10         388                    393               556
>  > 50         429                    396               631
>  > 100        451                    403               696
>  > 200        611                    418               876
>  > 500       2666                    654              1880
>  > 1000     12726                   2241              5588
>  > 
>  > So the non-tail-recursive template performs best on all counts.
> 


__________________________________________________
Do You Yahoo!?
Find a job, post your resume.
http://careers.yahoo.com

 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list