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(_at_)de(_dot_)ibm(_dot_)com> 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#14539656
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(_at_)gmail(_dot_)com>
To: xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com
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?revision=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(_at_)de(_dot_)ibm(_dot_)com> 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
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
--
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.
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--