[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Bad performance for substring replacement by pattern

From: Eric Blake
Subject: Re: Bad performance for substring replacement by pattern
Date: Tue, 03 Aug 2010 15:23:00 -0600
User-agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv: Gecko/20100720 Fedora/3.1.1-1.fc13 Lightning/1.0b2pre Mnenhy/0.8.3 Thunderbird/3.1.1

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   address@hidden    +1-801-349-2682
Libvirt virtualization library http://libvirt.org

Attachment: signature.asc
Description: OpenPGP digital signature

reply via email to

[Prev in Thread] Current Thread [Next in Thread]