Subject: RE: [xsl] Word Ladders as an example of a "Find shortest path between two nodes in a graph" problem From: Robby Pelssers <Robby.Pelssers@xxxxxxx> Date: Thu, 6 Dec 2012 18:14:47 +0000 |
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@xxxxxxxxxxxx] Sent: Wednesday, November 28, 2012 8:35 PM To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx 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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Word Ladders as an exampl, Wolfgang Laun | Thread | [xsl] [ANN] Proceedings of Balisage, Tommie Usdin |
Re: [xsl] Word Ladders as an exampl, Dimitre Novatchev | Date | Re: [xsl] Word Ladders as an exampl, Hermann Stamm-Wilbra |
Month |