Subject: Re: [xsl] Efficient XSLT range lookups / questions From: Dimitre Novatchev <dnovatchev@xxxxxxxxx> Date: Thu, 7 Oct 2010 10:25:04 -0700 |
Hermann, Are the regions non overlapping (as in the examples in [1]) ? On Thu, Oct 7, 2010 at 4:33 AM, Hermann Stamm-Wilbrandt <STAMMW@xxxxxxxxxx> wrote: > 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: B B B Dimitre Novatchev <dnovatchev@xxxxxxxxx> > To: B B B B xsl-list@xxxxxxxxxxxxxxxxxxxxxx > Date: B B B 10/05/2010 09:58 PM > Subject: B B 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 > > > > B <xsl:function name="f:binSearch" as="xs:boolean"> > B <xsl:param name="pSeq" as="item()+"/> > B <xsl:param name="pVal" as="item()"/> > B <xsl:param name="pStart" as="item()"/> > B <xsl:param name="pEnd" as="item()"/> > > B <xsl:sequence select= > B B "if($pStart gt $pEnd) then false() > B B B else > B B B B for $mid in ($pStart + $pEnd) idiv 2, > B B B B B B $sVal in $pSeq[$mid] > B B B B B return > B B B B B B if($sVal eq $pVal) then true() > B B B B B B else > B B B B B B B B if($sVal lt $pVal) > B B B B B B B B B then f:binSearch($pSeq, $pVal, $mid+1, $pEnd) > B B B B B B B B else > B B B B B B B B B f:binSearch($pSeq, $pVal, $pStart, $mid - 1) > B B B "/> > B </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 > > -- 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 ------------------------------------- I enjoy the massacre of ads. This sentence will slaughter ads without a messy bloodbath.
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Efficient XSLT range look, Hermann Stamm-Wilbra | Thread | Re: [xsl] Efficient XSLT range look, Hermann Stamm-Wilbra |
[xsl] XSL-FO: Column-specific marke, Matthew Nehrbass | Date | Re: [xsl] XSL-FO: Column-specific m, Tony Graham |
Month |