Re: [xsl] all-XSLT implementation of Minesweeper

Subject: Re: [xsl] all-XSLT implementation of Minesweeper
From: Sean Whalen <seanwhalen@xxxxxxxxxxx>
Date: Fri, 18 Mar 2005 06:28:29 -0500
I'd considered using a key, but the code that is there uses a variable that changes with each recursive iteration. I was concerned that the task of limiting the key values in the same way would wipe out any performance benefit. I'll give it a try though. I wasn't really satisfied with how the algorithm ended up.

below is chunk of the code. The $zeros variable contains the area near the user's click that the algorithm has processed. the $field variable contains the the non-bombs that have not been revealed yet. With every iteration, the set contained in $zeros will get larger and what remains in the $field will get smaller. I didn't see a way, built into the Key feature, to get that ability. The practical benefit of reducing the $field each time is that there's no risk of putting a square into the $alreadyRevealed set again. But, yes, I probably could use a key, and add soemthing like "AND NOT IN ($alreadyRevealed)" (that's psuedo-sql, because its 6am here). Also note that all the exisiting code is working with sets of non-bombs, which is likely to be a big ratio of the whole set. So, I was also concerned that a key that was almost as large as the full data set wouldn't be much faster. But I'll give it a try.

<xsl:variable name = "zeros" select = " $alreadyRevealed[@nbc = 0 and @isRevealed = 0]"/>

<xsl:variable name = "field" select = "SweeperMap/square[(@isBomb != -1 and @isRevealed = 0 and not (@sqID = $alreadyRevealed/@sqID )) ]"/>

<xsl:variable name = "revealing" select = "$field[ (...
or (concat(@h -1 ,'/', @v -1) = $zeros/@sqID)
or (concat(@h -1 ,'/', @v +1) = $zeros/@sqID)

And, while I'm writing, is this really impossible and/or inaccurate:

<xsl:variable name = "revealing" select = "$field[ (...
or (@h -1 = $zeros/@h AND @v + 1 = $zeros/@v)

I'd played with that kind of syntax for a long time before giving up. The code was returning $zeros/@h AND $zeros/@v values from different elements, which caused chaos. Not that this is related to performance, but is there way a to test 2 attributes like that?
The SQL analogy would be
SELECT field.* from field inner join zeros on field.h +1 = zeros.h and field.v -1 = zeros.v...

or instead, and this would get the whole thing with one hard-to-read line...
SELECT field.* from field inner join zeros on abs(field.h - zeros.h) <=1 and abs( field.v - zeros.v ) <=1

and LOL regarding freecell, et al.


From: David Carlisle <davidc@xxxxxxxxx>
Subject: Re: [xsl] all-XSLT implementation of Minesweeper
Message-Id: <200503171212.MAA04822@xxxxxxxxxxxxxxxxx>

regarding speed, the performance seem to benefit when I changed 2 expressions from "//square" to "SweeperMap/square". But the performances varies a lot by how much free space there is on the map.

similarly you have lots of expresions like this

+ count(//bomb[@h=$rowH -1 and @v=$rowV +1 ])

which are likely to be slow. Even if you change // to a more specific
path this cries out to use a key which would probably change the time
complexity of the algorithm completely as basically it tells the system
to use some space to make some kind of lookup table to find these things

something like

<xsl:key name="bomb" match="bomb" use="concat(@h,':',@v)"/>

then replace the above by

+ count(xsl:key('bomb',concat($rowH -1,':',$rowV +1)))

Current Thread