[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

Re: [xsl] Word Ladders as an example of a "Find shortest path between two nodes in a graph" problem

Subject: Re: [xsl] Word Ladders as an example of a "Find shortest path between two nodes in a graph" problem
From: Michael Kay <mike@xxxxxxxxxxxx>
Date: Wed, 28 Nov 2012 19:35:26 +0000

On 28/11/2012 18:15, Wolfgang Laun wrote:
The fact that one XSLT program runs three times faster on one XSLT
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

Current Thread