Re: time complexity of string +=

[Koichi Murase]

2021年3月13日(土) 0:17 Peng Yu <pengyu.ut@gmail.com>:
> It seems that the time complexity of string += is super-linear. Is it
> so? Should it be made to be linear instead of super-linear?

The time complexity of a single `+=' is not super-linear but linear
[i.e., O(string-length)]. In your measurement, the entire loop becomes
super-linear because you repeat it N (=10^2,10^4,10^6) times.

I guess you meant that the time complexity of a single ``string +=''
is now linear but could be an amortized constant time. It is in
principle possible by reallocating the strings with a capacity larger
than its actual string length and by exponentially increasing the
capacity on reallocation. But Bash strings are not designed to be a
string builder or a variable-size string buffer but to be a fixed
string, so I don't think the current implementation should be changed.

Instead, you can use arrays as a buffer:

TIMEFORMAT='%R'
for N in 10000{,0,00,000}; do
  time { buff=(); for ((i=0;i<N;++i)); do buff+=(a); done; IFS= eval
'x="${buff[*]}"'; echo ${#x}; }
done

10000 0.042
100000 0.234
1000000 2.405
10000000 23.894

--
Koichi