はじめに
不変オブジェクトのStringと可変オブジェクトのStringBuilderについてまとめました。そして、Stringオブジェクトに対して文字列操作を行う際の注意点について、時間計算量とともに考察しました。
Stringの基本
Stringは文字列を扱うクラスです。Javaの文字列は全てStringクラス（java.lang.String）のインスタンスとなります。
String str = "abc"
また、Stringは文字配列を用いて定義することもできます。
char[] data = {'a', 'b', 'c'};
String str = new String(data);
不変オブジェクトのString
Stringは不変オブジェクトであるため、一度文字列が作成されると、変更することができません。
例えば、str1に格納されている文字列"abc"を"bc"に変更するケースを考えます。
public class Main {
public static void main(String[] args) {
String str1 = "abc";
str1.substring(1); // "bc"
System.out.println(str1); // "abc"
// 元の文字列が変更されているわけではなく、substring()で作成された新しい文字列への参照をstr1に代入した。
str1 = str1.substring(1);
System.out.println(str1); // "bc"
}
}
str1は不変オブジェクトであるため、str1に対してsubstringメソッドを使用しても元の文字列である"abc"は変更されません。substringメソッドによって作成された新たな文字列をstr1に代入し直しただけで、元の文字列が変更されているわけではありません。
Stringクラスのデメリット
Stringは不変オブジェクトであるため意図しない副作用の発生を防ぐなど、安全性を提供します。しかし、注意点もあります。
// 文字列wはすべて同じ長さ: x
// 文字列の個数: n
public String joinWords(String[] words){
String sentence = "";
for (String w: words){
sentence = sentence + w;
}
return sentence;
}
計算量がO(xn^2)
文字列の連結のたびに新しい文字列が作成され、そこに２つの文字列が1文字ずつコピーされていきます。この操作は、文字列の長さに比例して時間計算量が増加します。時間計算量はO(xn^2)になるだけでなく、ループのたびに新たな文字列を作成することで多くのメモリを消費します。
** 時間計算量の導出は、一つ目の参考文献のp.106をご覧ください。
可変オブジェクトのStringBuilder
このような計算量の増加を避けるために、可変であるStringBuilderクラスを使用することができます。
// 文字列wはすべて同じ長さ: x
// 文字列の個数: n
public String joinWords(String[] words){
StringBuilder sb = new StringBuilder();
for(String w: words) {
sb.append(w); // 1回の文字列の追加はO(1)
}
return sb.toString(); // toStringメソッドでStringBuilderオブジェクトをStringオブジェクトに変更
}
計算量がO(xn)
StringBuilderは可変オブジェクトであるため、文字列の連結の際に新しい文字列を作成するのではなく、StringBuilderオブジェクトが内部で管理しているchar配列（バッファ）に文字を追加していきます。そして、最後にtoStringメソッドを使用してStringオブジェクトに変更します。上記の例では、時間計算量はO(xn)となり、O(xn^2)から大幅に効率が上がりました。
** mを最終的な文字列の長さとするとき、m = xnであるため、O(xn) = O(m)と書くことができます。
まとめ
今回の例のようにループを使用して何度もStringの変更を行う場合は、StringBuilderクラスを使うことが推奨されます。一方で、Stringに対して多くの変更を行わない場合には、Stringクラスの使用で十分でしょう。