[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] RE: Omnimark vs. XSL (Saxon) Challenge
Thank you very much for your ideas. I fear they are not easily applicable, because I have to keep the width of some cells, so I cannot easily discard processed rows. But I'll keep this in mind for other table related tasks. What I am going for is to stop processing as soon as I have a valid column width for every column. In this case the processing time depends mainly on the structure of any given table, but especially with long tables it may shorten the processing time dramatically. - Michael Müller-Hillebrand On 17.03.2004 (16:13 Uhr +0000), Michael Kay wrote: >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 -- _____________________________________________________________ Dipl.-Ing. Michael Müller-Hillebrand ???????????????????????????????????? "Mehr Effizienz für Wissensarbeiter" --> http://cap-studio.de XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|