Re: Very slow pattern substitution in parameter expansion

[Chet Ramey]

On 4/10/13 12:15 AM, Dan Douglas wrote:
> On Tuesday, April 09, 2013 10:23:34 PM Chet Ramey wrote:
>> On 4/9/13 9:56 PM, Dan Douglas wrote:
>>> Erm, here it is in a less unreadable format:
>>
>> It is pretty slow.  You forgot to enable `extglob'.
>  
> D'oh!
> 
> Bad algorithm? I suppose it's lots of backtracking and maybe has to test 
> every 
> substring for every position in the string. In my version it took about .3 of 
> a sec, but combining all that into one string with x=${a[*]}, doing the same 
> on x took about 10 seconds. It's still 0.00 in ksh/zsh.

Yep.  It's not a regexp engine, it's an interpreted-on-the-fly matcher.
There aren't as many opportunities for optimization, though I imagine
there are some.  ksh and zsh translate those patterns into regexps,
compile them, and execute them across the strings.

Chet
> 


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