[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:
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/