Subject: Re: [xsl] Efficient XSLT range lookups / questions From: Hermann Stamm-Wilbrandt <STAMMW@xxxxxxxxxx> Date: Thu, 7 Oct 2010 13:33:37 +0200 |
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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Efficient XSLT range look, Dimitre Novatchev | Thread | Re: [xsl] Efficient XSLT range look, Dimitre Novatchev |
Re: [xsl] Efficient XSLT range look, Hermann Stamm-Wilbra | Date | [xsl] XSL-FO: Column-specific marke, Matthew Nehrbass |
Month |