Re: [xsl] Efficient XSLT range lookups / questions

[Hermann Stamm-Wilbrandt <STAMMW@xxxxxxxxxx>]

Dimitre,

> 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?

because I wanted to compare optimal performance I did the minimal
binary search implementation for the problem myself.

In [1] I describe a simple input format and provide a stylesheet for
generating the optimal binary decision stylesheet from that (by
the measurements done that outperforms binary search on a XML tree).

Remember that the investigation was for XSLT 1 and XSLT 2 processors.

May you please point out on how to setup a test with f:binSearch()
on the simple range lookup input format in [1]?

Since it works on XSLT 2.0 sequences probably that will get better
results than my binary search based on nodesets.


[1]
https://www.ibm.com/developerworks/forums/thread.jspa?threadID=348576#1453965
6


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



From:       Dimitre Novatchev <dnovatchev@xxxxxxxxx>
To:         xsl-list@xxxxxxxxxxxxxxxxxxxxxx
Date:       10/05/2010 09:58 PM
Subject:    Re: [xsl] Efficient XSLT range lookups / questions



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
>  the lookup performance remains good even for single lookups (logarithmic
>  in depth of search tree; DataPower supports both, and web searches
> indicate
>  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