This is the mail archive of the
xsl-list@mulberrytech.com
mailing list .
Re: Re: lookup-table thoughts (was Re: matching multiple times, outputting once?
- To: Mark Nahabedian <naha at ai dot mit dot edu>, xsl-list at lists dot mulberrytech dot com
- Subject: Re: [xsl] Re: lookup-table thoughts (was Re: matching multiple times, outputting once?
- From: Dimitre Novatchev <dnovatchev at yahoo dot com>
- Date: Fri, 9 Nov 2001 13:34:36 -0800 (PST)
- Cc: jeni at jenitennison dot com
- Reply-To: xsl-list at lists dot mulberrytech dot com
> 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@ai.mit.edu> 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