Subject: RE: [xsl] Omnimark vs. XSL (Saxon) Challenge From: "Michael Kay" <mhk@xxxxxxxxx> Date: Wed, 17 Mar 2004 16:13:54 -0000 |
# >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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
[xsl] Omnimark vs. XSL (Saxon) Chal, Michael Müller-Hille | Thread | RE: [xsl] Omnimark vs. XSL (Saxon) , David Tolpin |
[xsl] Omnimark vs. XSL (Saxon) Chal, Michael Müller-Hille | Date | RE: [xsl] xsl checkbox, Michael Kay |
Month |