David:
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[(_at_)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.
Sean
From: David Carlisle <davidc(_at_)nag(_dot_)co(_dot_)uk>
Subject: Re: [xsl] all-XSLT implementation of Minesweeper
Message-Id:
<200503171212(_dot_)MAA04822(_at_)penguin(_dot_)nag(_dot_)co(_dot_)uk>
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[(_at_)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
quickly.
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)))
--~------------------------------------------------------------------
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>
--~--