RE: [xsl] Omnimark vs. XSL (Saxon) Challenge

["Michael Kay" <mhk@xxxxxxxxx>]

# >How long does it take, and how does the elapsed time vary as 
# the table 
# >size increases? Plotting that can often deepen your understanding of 
# >what you are asking the XSLT processor to do.
# 
# 64 rows: 2 secs
# 96 rows: 5 secs
# 128 rows: 10 secs
# 160 rows: 17 secs
# 192 rows: 30 secs
# 224 rows: 62 secs
# 
# That is exponential... 

It looks quadratic to me, or perhaps just a little worse than quadratic. If
it was exponential, you really would have problems.

(Quadratic goes 1,4,9,16,27,64,49,64,81,100. Exponential goes
2,4,8,16,32,64,128,256,512)

I think it's quite hard to come up with an algorithm here that isn't
quadratic. The best I can come up with as that you process the cells by row
and then column in a single recursive sequence, passing as a parameter a map
of which positions in the final table are already occupied. Expressing this
map as an RTF will require copying it at each stage, which will give you
quadratic performance; so try expressing it as a character string, which can
be copied at close to constant cost. (The fastest implementation of my
knight's tour turned out to be the one that represented the board as a
character string). I think the map can be as simple as a zero for a vacant
position, a one for an occupied position, and a delimiter for the end of
each row (you can discard rows once they have been processed). The algorithm
for processing each cell is then to find the map for the current row (which
is the first row in the map if you drop rows as you go) and look for the
first sequence of n vacant positions where n is the colspan; then create a
new map in which you mark these positions and any previous positions in the
row as occupied, together with corresponding positions in subsequent rows
within the range of the cell's rowspan, and then move on to the next cell. I
think this algorithm will be very close to linear.

Michael Kay


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list