はじめに
不変オブジェクトの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.substring(1)を実行して、str1に対して文字列操作を行ってみます。
public class Main {
public static void main(String[] args) {
String str1 = "abc";
str1.substring(1); // "bc"
System.out.println(str1); // "abc"
}
}
"abc"
str1は不変オブジェクトであるため、str1に対してsubstringメソッドを使用しても元の文字列である"abc"は変更されません。
下の例でも、str1.substring(1)で作成された新しい文字列への参照をstr1に代入しただけで、元の文字列が変更されているわけではありません。
public class Main {
public static void main(String[] args) {
// 元の文字列が変更されているわけではなく、substring()で作成された新しい文字列への参照をstr1に代入した。
String str1 = "abc";
str1 = str1.substring(1);
System.out.println(str1); // "bc"
}
}
"bc"
Stringクラスのデメリット
Stringは不変オブジェクトであるため意図しない副作用の発生を防ぎ、安全性を提供します。しかし、注意点もあります。
計算量がO(xn^2)
文字列の連結のたびに新しい文字列が作成され、そこに２つの文字列が1文字ずつコピーされていきます。この操作は、文字列の長さに比例して時間計算量が増加します。時間計算量はO(xn^2)になるだけでなく、ループのたびに新たな文字列を作成することで多くのメモリを消費します。
文字列wの長さ: x
文字列の個数: n
public String joinWords(String[] words){
String sentence = "";
for (String w: words){
sentence = sentence + w;
}
return sentence;
}
時間計算量の導出は、1つ目の参考文献のp.106をご覧ください。
可変オブジェクトのStringBuilder
このような計算量の増加を避けるために、可変のStringBuilderクラスを使用することができます。
計算量がO(xn)
StringBuilderは可変オブジェクトであるため、文字列の連結の際に新しい文字列を作成するのではなく、StringBuilderオブジェクトが内部で管理しているchar配列（バッファ）に文字を追加していきます。そして、最後にtoStringメソッドを使用してStringオブジェクトに変更します。下の例では、時間計算量はO(xn)となり、O(xn^2)から大幅に改善しました。
文字列wの長さ: x
文字列の個数: n
public String joinWords(String[] words){
StringBuilder sb = new StringBuilder();
for(String w: words) {
sb.append(w);
}
return sb.toString(); // toStringメソッドでStringBuilderオブジェクトをStringオブジェクトに変更
}
mを最終的な文字列の長さとするとき、m = xnであるため、O(xn) = O(m)と書くことができます。
まとめ
今回の例のようにループを使用して何度も文字列操作を行う場合は、StringBuilderクラスの使用が推奨されます。