Re: [xsl] Efficient XSLT range lookups / questions

Subject: Re: [xsl] Efficient XSLT range lookups / questions
From: Dimitre Novatchev <dnovatchev@xxxxxxxxx>
Date: Tue, 5 Oct 2010 12:58:18 -0700
Have you compared these to using just a single binary search function,
as the one offered by FXSL for at least the last six years?

http://fxsl.cvs.sourceforge.net/viewvc/fxsl/fxsl-xslt2/f/func-binSearch.xsl?r
evision=1.4&view=markup


 <xsl:function name="f:binSearch" as="xs:boolean">
   <xsl:param name="pSeq" as="item()+"/>
   <xsl:param name="pVal" as="item()"/>
   <xsl:param name="pStart" as="item()"/>
   <xsl:param name="pEnd" as="item()"/>

   <xsl:sequence select=
    "if($pStart gt $pEnd) then false()
       else
        for $mid in ($pStart + $pEnd) idiv 2,
             $sVal in $pSeq[$mid]
           return
             if($sVal eq $pVal) then true()
             else
                if($sVal lt $pVal)
                   then f:binSearch($pSeq, $pVal, $mid+1, $pEnd)
                else
                  f:binSearch($pSeq, $pVal, $pStart, $mid - 1)
       "/>
 </xsl:function>


--
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
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play




On Tue, Oct 5, 2010 at 10:58 AM, Hermann Stamm-Wilbrandt
<STAMMW@xxxxxxxxxx> wrote:
>
> Hello,
>
> I got notice of an interesting scenario needing a huge amount of range
> lookups in XSLT (billions per year with more than 20000 different ranges).
>
>
> My web searches prior to this only showed range lookups of complexity
> linear in the number of ranges to be searched. I am sure that my searches
> are not perfect and I just missed relevant postings.
> Are there any relevant postings?
>
>
> Since the ranges change rarely precomputing was a good option.
>
> I compared binary search trees against stylesheets with a binary search
> structure.
>
> Findings based on experiments with saxon9he and DataPower XSLT processor
> [1]:
> - binary outperforms linear
> - binary stylesheets outperform binary XML searchtrees
> - in case the XSLT processor supports document and/or stylesheet caching
> B the lookup performance remains good even for single lookups (logarithmic
> B in depth of search tree; DataPower supports both, and web searches
> indicate
> B that .net framework also supports document/stylesheet caching)
>
> Are there even better alternatives for doing quick range lookups?
>
>
> [1] "Efficient XSLT range lookups"
>
https://www.ibm.com/developerworks/forums/thread.jspa?threadID=348576&tstart=
0
>
>
> Mit besten Gruessen / Best wishes,
>
> Hermann Stamm-Wilbrandt
> Developer, XML Compiler, L3
> Fixpack team lead
> WebSphere DataPower SOA Appliances
> ----------------------------------------------------------------------
> IBM Deutschland Research & Development GmbH
> Vorsitzender des Aufsichtsrats: Martin Jetter
> Geschaeftsfuehrung: Dirk Wittkopp
> Sitz der Gesellschaft: Boeblingen
> Registergericht: Amtsgericht Stuttgart, HRB 243294

Current Thread