RE: Word Ladders as an example of a "Find shortest pat

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:  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