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