[Top][All Lists]

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

Re: Bad performance for substring replacement by pattern

From: Chet Ramey
Subject: Re: Bad performance for substring replacement by pattern
Date: Tue, 03 Aug 2010 17:12:49 -0400
User-agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; en-US; rv: Gecko/20100111 Lightning/1.0b1 Thunderbird/3.0.1

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.

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

reply via email to

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