Re: [xsl] To determine the distinct elements in a sequence of 46,656 elements takes 5 hours of XSLT processing

Subject: Re: [xsl] To determine the distinct elements in a sequence of 46,656 elements takes 5 hours of XSLT processing
From: Dimitre Novatchev <dnovatchev@xxxxxxxxx>
Date: Sun, 19 Aug 2012 16:58:18 -0700
On Sun, Aug 19, 2012 at 3:43 PM, Costello, Roger L. <costello@xxxxxxxxx> wrote:
>       <xsl:for-each select="$new-maps/maps/map">
>                 <xsl:if test="not(ct:contained-within(., ./following-sibling::map))"><xsl:sequence select="." /></xsl:if>
>         </xsl:for-each>

Michael Kay has shown a neat and efficient solution using <xsl:for-each-group>.

I am answering the first of the two questions: what isthe reason for
the inefficiency -- by copying the exact code (above) that contains
that inefficiency.

ct:contained-within(., ./following-sibling::map))   takes at least O(N)

As this is executed N times (in the <xsl:for-each>), the time
complexity of this algorithm is at least O(N^2).

For small sequences this algorithm may still perform acceptably -- for
example for ~ 500 maps it may need less than 2 seconds to output the
results.


-- 
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
-------------------------------------
Facts do not cease to exist because they are ignored.
-------------------------------------
I finally figured out the only reason to be alive is to enjoy it.

Current Thread