Subject: [xsl] Re: Re: String parsing in XSLT/XPath? From: Dimitre Novatchev <dnovatchev@xxxxxxxxx> Date: Sat, 8 Sep 2001 04:35:47 -0700 (PDT) |
> I doubt this is relevant, since you're dealing with addresses, which > tend to be fairly short, but if you're dealing with long strings with > lots of line breaks in them, then you may find it more efficient to > use a divide-and-conquer approach whereby you split the remaining > string. This has the advantage of limiting the depth of the recursion, > and therefore the call stack, but the disadvantage of not being tail > recursive and therefore not amenable to optimisation: > [nice divide and conquer code snipped] > With this, you will have to add the <br /> to the end of the string > yourself. > > If performance is an issue, I suggest that you try both of the > templates on your particular data and processor to see which is best > for you; if neither is significantly faster than the other, then use > the one you feel most comfortable with maintaining. Wow... I've been waiting for this moment to see someone on this list describe and recommend divide and conquer recursive algorithms -- thank you, Jeni! To the above description I can only add the following: DvQ algorithms will be naturally the fastest on a parallel execution multiprocessor environment. Virtually nothing has to be changed in them in order to execute each "half processing" on an available processor. I wish I would live long enough to see an XSLT processor that takes advantage in this way of an available multi-processor configuration. Not long ago I raised the question whether a special new XSLT instruction will be necessary in order to specify that a contained sequence of XSLT instructions can be performed in parallel. As there was no answer, I'm asking this question again. Reading the working draft (3) of XSLT 2.0 it seems to me that such an explicit XSLT instruction will not be necessary -- is this understanding right or wrong? Another comment is on the fact that it is easy to write a DvQ algorithm for replacing every occurrence of a ***single character*** within a string with another string. However, it is very difficult and not at all trivial to produce a DvQ algorithm for the solution of the general replace problem. I went through this excersice a month ago and the resulting DvQ algorithm is outperforming the simple sequential one-at-a time recursive algorithm only when considerably big number of replacements have to be made. This is because quite complex synchronisation is necessary. Even in this case it would be possible to have very efficient parallel execution implementation of this algorithm. The same is not true for any tail-recursive algorithm, as it is synonimous with sequential execution and having more than one processor cannot help speeding up such sequential algorithm. Apart from this extreme case, I've implemented DvQ algorithms for solving a number of well-known problems (e.g. min/max, tokenisation, summation of calculated values, reversing a string, pow(). ... etc.) In most of this cases with the increase of length of the input the performance of the DvQ algorithms becomes much better even than that of a corresponding tail recursive implementation. Tail recursion is extremely efficient only in cases when not many string parameters have to be passed and when the algorithm is very simple, e.g. just write a number to the output tree. Cheers, Dimitre Novatchev. __________________________________________________ Do You Yahoo!? Get email alerts & NEW webcam video instant messaging with Yahoo! Messenger http://im.yahoo.com XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
RE: [xsl] Pass xml values to a java, Chen Wang | Thread | RE: [xsl] Re: Re: String parsing in, Michael Kay |
Re: [xsl] String parsing in XSLT/XP, Jeni Tennison | Date | RE: [xsl] String parsing in XSLT/XP, Sullivan, Dan |
Month |