[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

RE: Omnimark vs. XSL (Saxon) Challenge

Subject: RE: Omnimark vs. XSL (Saxon) Challenge
From: "Michael Kay" <mhk@xxxxxxxxx>
Date: Wed, 17 Mar 2004 16:13:54 -0000
chal michael
# >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

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.