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:
Description:
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.
Chet
--
``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/