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 ebl...@redhat.com +1-801-349-2682 Libvirt virtualization library http://libvirt.org
signature.asc
Description: OpenPGP digital signature
