内容変更が頻繁に起きる場合は、StringBufferを使ったほうが効率が良いです。それがなぜか？を調べてみたので、備忘のためまとめます。
Stringオブジェクトはイミュータブル
JavaのStringオブジェクトは内容変更ができない。(immutable)
+=演算子を用いた文字結合による内容変更は可能だが、ここではオブジェクトの内容は変えず、新たなオブジェクトを生成して変数の指すオブジェクトを変えているだけである。新たなStringオブジェクトが生成されることは、メモリ的に非効率なことである。
n回のStringの足し算にかかる計算量
具体的に計算量を考える。すべての文字列の長さ同じ長さxとして、文字列の個数をn個と考えると、最初の足し算の処理で、x文字分のコピーを生成するのに、O(n)、ループの二回目の足し算で、2x文字分のコプーが必要になり、3回目は3x文字分...と増え続け、計算量はトータルで、O(x + 2x + 3x + ... + nx)でO(xn^2)の計算量になる。(メモリ的にもこれだけゴミを生み出しているので、非効率。)
以下疑似コード。
.java
String sentence = new String();
for (String w : words) {
sentence = sentence + w; // ここで計算結果が新しいオブジェクトとして生成され、sentenceにセットされる(ix文字分のコピー)。それまでsentenceの指していたオブジェクトは、ゴミとなる。
}
StringBufferはミュータブルで計算効率が良い
StringBufferオブジェクトは、オブジェクト生成後であっても、内容変更することが可能なため、必要に応じて文字列の後ろにコピーしていくことができる。そのため、内容変更が頻繁に起きる場合は、StringBufferを使ったほうが効率が良い。
先ほどと同様に計算量を考えると、n回文字列の後ろx文字コピーするだけなので、O(xn)か。
以下疑似コード。
.java
StringBuffer sentence = new StringBuffer();
for (String w : words) {
sentence.append(w);
}
参考
サイズnの配列のコピーにかかる時間
- サイズnのもう一つの配列を宣言する
- それぞれの要素を1..i..nまでセットしていく => O(n)
なので、サイズnの配列をコピーするのにはO(n)の時間がかかる。
StringはCharの配列なので、Stringのコピーも同様に考えられる。
## よくまとまってるリンク