Re: Bad performance for substring replacement by pattern

[Chet Ramey]

On 7/12/10 4:27 PM, Yi Yan wrote:
> 
> Hi,
> 
>      I used the following Bash script to test substring replacement operator.
> It is performance get worse very quickly with the increasing of the string
> length.

This is a pathological case.  I don't really see how to optimize it very
well.  The pattern is only a single character, so you have to test and
possibly match each character of the string.  Since the matching semantics
dictate that the longest possible match is returned on every match attempt,
you have to test each substring from the current position to the end of
the string, where the current position goes from the start of the string
to the end, even though the pattern will only ever match the first
character.  I've forgotten much of what I knew about Big O notation, but
I think this is O(n*n) where n is the length of the string.

You can improve things slightly by using a pattern that will match multiple
characters, like the extended glob +([^;]), but that helps only a little at
best and may slow things down because of the more complicated matching.

Chet
-- 
``The lyf so short, the craft so long to lerne.'' - Chaucer
                 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, ITS, CWRU    chet@case.edu    http://cnswww.cns.cwru.edu/~chet/