Re: Bad performance for substring replacement by pattern

[Eric Blake]

On 08/03/2010 03:12 PM, Chet Ramey wrote:
> 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,

But why not teach the matcher the difference between a fixed-length
pattern, vs. one that has * or other extended globbing that would cause
a variable length match?  That is, since you know that [^;] can match at
most one character, there is no need to search from the current position
to the end of the string on each iteration - just search the first byte
of the string.

You are correct that your current implementation is O(n*n), but I don't
see any reason why this case can't be made O(n) with some careful
thought about what is going on.

-- 
Eric Blake   eblake@redhat.com    +1-801-349-2682
Libvirt virtualization library http://libvirt.org

signature.asc
Description: OpenPGP digital signature