Subject: Re: [xsl] [XSL] Accessing part of the result tree illustrated with "The Sudoku solver" example. From: Alain <alainb06@xxxxxxx> Date: Wed, 05 Sep 2007 13:43:02 +0200 |
> I think there's a "missing feature" in XSL (or I just haven't found it)[snip]
> when you do recursing programs, but I would appreciate your point of
> view of experts and W3C members.
> Well, don't tell me it is a bad algorithm, I know it ! It is just "brute[snip]
> force". We recurse on the empty elements and try every possible value
> that fits in that element up to the point where all the elements have a
> value matching the Sudoku rules (or no solution if your initial input is
> incorrect).
>
> Abel, you were right, it is so graceful ending a recursion without a bad
> looking xsl:if (prioritized template do the job) :-)
> You had the "fun" part, now comes the question.
>
>
> A naive reader might say this algorithm is cool because it gives a
> solution. Although depending on the initial values you enter and the
> speed of your computer it might run from a few seconds to many minutes.
>
> But experts as you are, you would have noticed that there is a major
> BUG: even when we have found the solution, the recursion continues!..
> So you can get "lucky" and find a solution in the first seconds, then
> run for many minutes uselessly just terminating the recursion.
Have a look at: http://andrewjwelch.com/code/xslt/sudoku/sudoku-solver.html
This is the sudoku solver I wrote in XSLT 2.0. It uses the various techniques humans use to solve the puzzle before resorting to brute force - even on the hardest puzzles there's usually only a choice of two values at that point. On my machine in can solves all puzzles in under a second, which was the long term goal when Dimitre and I started competing [1] (as you probably know basic backtracking solutions can be extremely fast for one puzzle, and unbelievably slow for another)
Anyway, the end of the recursion in my solution is when either the board has no empty cells left (it's solved) or the are no possible values left for a given cell.
[1] http://ajwelch.blogspot.com/2007/06/sukoku-solver-much-improved.html
Let's step down the algorithm to point out the things we have to do to work around the limitation I'm pointing.
When you come to the point where you have to use "brute force", let's say your first emptyCells has (4, 7, 9) as possibleValues.
[...] fn:populateValues => stack params : board => stack params : emptyCell => stack params : (4,7,9) => call fn:tryValues
Now tryValues will try first value (4) and call again populateValues. Let's says that it didn't work and you are in a dead end having tried (4). So populteValues returns with the empty sequence.
You then enter the xsl:choose in your tryValues which calls itself recursively.
[...] fn:populateValues => stack params : board => stack params : emptyCell => stack params : (4,7,9) => call fn:tryValues ====> stack params : board ====> stack params : emptyCell ====> stack params : (7, 9) ====> call fn:tryValues
The first "try" was a dead end, at this point we know it, but it is still stacked, and still taking stack/heap space. The stack space used is useless as, when you will find the solution, you'll just unstack because you have no other instructions after your xsl:choose. [I wonder if any XSL processor would be optimized enough to free the heap at this point, assuming params go to heap and it stack pointers. For the stack you are definitely stuck at least with pointers to {invalid} heap and return address]
Here we don't really care, because we are speaking of stacking 3 sequences of integers, let's say around 1KB of data plus function call overhead. But if we had bigger recursions this bad construct will quickly lead to stack-overflow !
If you could have used a for-each, instead of a recurse 1 by 1, it would have saved stack... and may be time (for your contest) as stack/heaping sequences and calling is certainly longer than a test.
While reading your program, I saw a few instructions I were not familiar with (saxon extensions). Looking at their documentations, I think I found a workaround to the "useless-stacking-syndrom".
saxon:assignable saxon:assign
As the documentation says, these extensions "cheat" XSL. But hey, when there are limitations and the only way is to "cheat", we might just use them (reasonably)!
<!-- global variable to end recursion --> <xsl:variable name="theEnd" select="false()" saxon:assignable="yes"/>
<xsl:function name="tryValues"> [snip params]
<xsl:for-each select="$possibleValues> <xsl:if test="not($theEnd)">
[snip your code] [... and no more need to recurse on tryvalues for possibleValues here, that's what the for-each does properly, with the intial test to stop the unnecessary recursions !]
</xsl:if> </for:each> </xsl:function>
In the function populateValues, when you found the solution, you do a saxon:assign to theEnd and set it to true().
Like that you will save a few... nanoseconds !.. Your program will be a little bit easier to read (that's to my point of view, it might be the contrary for other persons). On the other hand, your program will now be saxon-dependant. At the moment, the only saxon extensions you used are just for optimisations and could be safely removed if you change your XSL processor (although it will then be much slower).
So, Andrew, if the exact rules of your contest were to be XSLT2.0-every-processor compliant you are stuck... but if you were allowed to use whichever XSL processor you like, you might get a try removing the "useless" recursion, although I'm quite sure the time difference won't be noticeable at the precision of your computer's clock !
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
[xsl] Search text and write the cod, Byomokesh Sahoo | Thread | RE: [xsl] [XSL] Accessing part of t, Michael Kay |
Re: [xsl]Putting Mouseover Javascri, Alice Ju-Hsuan Wei | Date | RE: [xsl] [XSL] Accessing part of t, Michael Kay |
Month |