[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

[xsl] Re: Re: How to filter characters from a string?


Subject: [xsl] Re: Re: How to filter characters from a string?
From: Dimitre Novatchev <dnovatchev@xxxxxxxxx>
Date: Thu, 28 Mar 2002 23:54:45 -0800 (PST)

Hi Greg,

>   I was simply asking how to filter() out non-specified characters 
> from a string, rather than translate() specified characters to 
> nothing.  From Dimitre's post, I adapted the following code which 
> does the requested task, 

I'm glad you could use the code adapted from str-filter().

One point I'd like to make is that you don't need to "adapt" this code.
It is best if functions are just used. This will prevent the user from
introducing errors. It also eliminates any need for the same code to be
re-written every time a new similar problem must be solved. Instead of
having to write the same recursion over and over again every time you
have a similar problem and wasting a lot of time and probably making
some error from time to time, it is much better just to re-use one
single function (str-filter() in this particular case).

Another consequence of "adapting" a function's code for every specific
problem is that this ends up with having a multitude of different
templates that are doing the same thing. Imagine what a nightmare it
would be if you have to introduce an "optimisation" in all of them.
You'll have difficulties even in keeping track of all such redundant
templates.

> but I'm not sure about its efficiency.  It basically checks every 
> character in a source string against a string of known, valid 
> characters.  Any string not found in the valid string doesn't make 
> the cut.  I suppose there's no faster algorithm, unless one is built 
> into the XSLT processor.

The efficiency of the algorithm is O(N) (linear) and probably cannot be
surpassed (unless we could index every individual character of a
string).

What you're actually raising as a potential problem is that a
particular implementation of the ***same*** algorithm could be faster
if coded not in XSLT but in another language (e.g. C or Java).

A more practical problem could arise if a particular XSLT processor
does not implement tail-recursion as iteration. In this case the
supposedly linear algorithm behaves exponentially, eventually crashing
due to insufficient call-stack space.

To prevent this from happening, many FXSL functions have their DVC
(divide and conquer) implementations, which have minimal
O(log2(N))recursion depth.

You can read about DVC at:

http://www.topxml.com/snippetcentral/main.asp?view=viewsnippet&id=v20020107050418

or in the last year's archives of this list (June-August).

I'd be glad to provide to you a DVC implementation of the str-filter()
function, in case you might need it.

Cheers,
Dimitre Novatchev.


__________________________________________________
Do You Yahoo!?
Yahoo! Greetings - send holiday greetings for Easter, Passover
http://greetings.yahoo.com/

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



Current Thread
Keywords