Ooopsss...
This is DVC (Divide and Conquer) -- and not binary search. The
complexity is still linear!
The only advantage of this solution is that it will not cause stack
overflow for any practical uses (for example the maximum depth of the
call stack when comparing two 1MB strings is just 19).
The same could probably be achieved with a clever tail-recursive
solution, but not all processors support tail-recursion-optimization,
and those that do, don't have the same definition for
"tail-recursive".
DVC, on the other side, is not dependent on the implementation of any
XSLT processor.
About efficiency: I suspect that if the strings are converted to
codepoints first, then the similar solution for integer sequences
could potentially be faster -- would our dear implementors of XSLT
processors comment on this, please?
--
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.
On Fri, Sep 11, 2009 at 1:46 PM, Dimitre Novatchev
<dnovatchev(_at_)gmail(_dot_)com> wrote:
On Thu, Sep 10, 2009 at 7:10 AM, <mlcook(_at_)wabtec(_dot_)com> wrote:
The XSLT function "compare" will compare 2 strings and indicate which is
alphabetically first.
Here is a binary search solution in XPath 2.0 :)
The transformation below:
<xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
xmlns:xs="http://www.w3.org/2001/XMLSchema";
xmlns:f="http://fxsl.sf.net";
>
<xsl:output method="text"/>
<xsl:template match="/">
<xsl:sequence select="f:fstDiff('abcde', 'abceefg')"/>
</xsl:template>
<xsl:function name="f:fstDiff" as="xs:double">
<xsl:param name="pS1" as="xs:string"/>
<xsl:param name="pS2" as="xs:string"/>
<xsl:sequence select=
"for $len in min((string-length($pS1), string-length($pS2))),
$comleteMatchResult in $len +1,
$leftResult in f:auxFstDiff(substring($pS1, 1, $len),
substring($pS2, 1, $len)
)
return
min(($leftResult, $comleteMatchResult))
"/>
</xsl:function>
<xsl:function name="f:auxFstDiff" as="xs:double">
<xsl:param name="pS1" as="xs:string"/>
<xsl:param name="pS2" as="xs:string"/>
<xsl:sequence select=
"for $len in string-length($pS1)
return
if($len eq 1)
then 1 + number($pS1 eq $pS2)
else
for $halfLen in $len idiv 2,
$leftDiffPos in f:auxFstDiff(substring($pS1,1,$halfLen),
substring($pS2,1,$halfLen)
)
return
if($leftDiffPos le $halfLen)
then $leftDiffPos
else $leftDiffPos +
f:auxFstDiff(substring($pS1,$halfLen+1),
substring($pS2,$halfLen+1)
)
- 1
"/>
</xsl:function>
</xsl:stylesheet>
when applied on any XML source document (not used), returns the correct
answer:
4
Because this is theoretically O(log2(N)), expect this transformation
to perform (hopefully) dramatically faster than the linear search,
given long enough strings.
--
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.
Is there any function, or simple transformation, that will tell me the
position of the first character where the two strings differ?
"compare" might determine this, but it isn't telling. I suppose strings
can be compared in various ways internally, so the position of the first
difference might not be a side-effect of "compare".
Comparing strings can also be time consuming for long strings, so I'd
like an "inexpensive" solution, if there is one.
Any suggestions for finding the first difference in 2 strings (besides a
linear march through the strings in my XSL transformation)?
Thanks, Mike
This email and any attachments are only for use by the intended recipient(s)
and may contain legally privileged, confidential, proprietary or otherwise
private information. Any unauthorized use, reproduction, dissemination,
distribution or other disclosure of the contents of this e-mail or its
attachments is strictly prohibited. If you have received this email in
error, please notify the sender immediately and delete the original.
--~------------------------------------------------------------------
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>
--~--