[Top][All Lists]

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

Re: [PATCH] fix super-linear complexity of ${v^} and ${v//A}

From: Chet Ramey
Subject: Re: [PATCH] fix super-linear complexity of ${v^} and ${v//A}
Date: Mon, 28 Jun 2021 16:00:41 -0400
User-agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) Gecko/20100101 Thunderbird/78.11.0

On 6/27/21 2:13 AM, Koichi Murase wrote:

   The time complexities of ${v/...} and ${v^...} are expected to be
   linear with respect to the length of the variable contents.
   However, the time complexity of ${v/...} is quadratic if there is no
   replacement when the length is larger than about 10000.  Also, the
   time complexity of ${v^} becomes quadratic if the variable contains
   many newlines.

Thanks for the report and fixes.


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

reply via email to

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