xsl-list
[Top] [All Lists]

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

2012-12-06 12:15:11
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>
--~--