Just wondering if this game is not a perfect match for how database indexes
work using b-trees?
Robby
-----Original Message-----
From: Michael Kay [mailto:mike(_at_)saxonica(_dot_)com]
Sent: Wednesday, November 28, 2012 8:35 PM
To: xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com
Subject: Re: [xsl] Word Ladders as an example of a "Find shortest path between
two nodes in a graph" problem
On 28/11/2012 18:15, Wolfgang Laun wrote:
The fact that one XSLT program runs three times faster on one XSLT
implementation than on another one is strange, *very* strange.
No, it's extremely common. In fact, very much larger factors than this are
possible. Sometimes Saxon-EE runs 1000 times faster than Saxon-HE.
This effect is normal with declarative languages where powerful optimizations
are deployed - SQL users will be very familiar with the effect.
But is Saxon 6.4 the
"dernier cri"?
I'd very much like to hear Michael Kay's opinion on this.
I think the attempt to run it with 6.4 was an error; the figures reported were
on 9.x for some recent x.
There will always be some cases where there's a possible optimization which we
fail to detect. We'll investigate this and see if improvements are possible.
As an aside, I'd like to say that neither DN's nor WL's solution is
something that should be used if this problem (i.e., shortest path)
should ever need a solution. I think that this isn't something that
should be solved in XSLT at all, except as an academic exercise.
(Feel free to disagree - I'll not reply to anything contradicting me.)
I disagree. I think nearly all algorithms are viable in XSLT; its limitations
are that it's specialized towards handling XML as its data structure, so some
data structures don't lend themselves well to XSLT processing.
The only algorithms which I don't know how to tackle in XSLT (and that's a
limitation of the implementations rather than the language) are "simulated
annealing" style optimizations that require a large number of small
transformations to a large tree; the cost of making a small change to a large
tree is typically proportional to the size of the tree rather than the size of
the change.
Michael Kay
Saxonica
--~------------------------------------------------------------------
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>
--~--