java - Javaの文字列に対する+操作のコストはいくらですか？

Question

このforループの場合、実行時間はO（n）またはO（n ^ 2）です。

char[] ar = new char[1000];
String s = "";
Arrays.fill(ar, 'a');
for(Character c: ar){
    s += c;
}

それで、基本的に、文字列での+の実行時間はどれくらいですか？Javaの舞台裏ではどのように機能しますか？

Answer 1

Java 文字列は不変です。あなたがするたびに：

s+=c;

あなたは本当に言っています：

s = 新しい文字列 (s + c);

new String(s + c) は、長さ s + 1 の文字列を割り当てる必要があります。または:

1 2 3 4 5 6 7 8 9 ...など

Sum(1..N) == (n + 1) (n / 2) なので、これは O(n^2) です。

StringBuilder が明確な利点となるケースの 1 つです。

Answer 2

Josh Bloch 著「Effective Java」より。本の項目 33:

文字列連結演算子を繰り返し使用して n 個の文字列を連結すると時間がかかります。

StringBuilder を使用します。その性能はO(n)だと思います。