文字列バッファについて

Question

言語はJavaにしていますが、Javaに限った話ではありません。

私が勉強している本で次のような記述がありました。
「文字列のリストを連結するときを考えます。すべての文字列の長さはx、文字列はn個あるとします。
連結の度に新しい文字列が生成され、そこに二つの文字列が一文字ずつコピーされます。最初の繰り返し処理でx文字分のコピーが要求されます。二回目の繰り返し処理では2x文字分のコピーが必要になり、三回目では3x文字分、、のように増え、最終的にはO(xn^2)の計算量になります。」

元々あった文字列がaaaだっとした時に、これを二つ連結するときのコードというのは

String newString = new String("aaa" +"aaa");

になるわけですよね？
これは一つの文字列インスタンスが増えるわけではなくて、全く新しい文字列インスタンスが作られ、その参照が左辺に代入されるわけです。
そうすると、上で示した文章の「x文字分のコピーが要求されます」というのが理解できません。
xではなく、2xではないでしょうか？
回答お願いします。

Answer 1

すでにベストアンサーが出ているようですが、気になったので実験してみました。

私も本当かなと思ってやってみたのですが、その通りの結果になりました。

文字列を一文字ずつコピーするためcharの配列を持つMyStringクラスを定義してそれに１文字ずつコピーをしてみました。https://paiza.io/projects/NR8hnbX347ScPJ-aMcVkBQ

public class MyString{
    public char[] str;
    
    public MyString(String str){
        this.str = str.toCharArray();
    }
    
    public MyString(int length){
        this.str = new char[length];
    }
    
    public int length(){
        return this.str.length;
    }
    
    public String toString(){
        return new String(str);
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        //コピー元の文字列のリスト
        List<MyString> list = new ArrayList<MyString>();
        list.add(new MyString("aa"));
        list.add(new MyString("bb"));
        list.add(new MyString("cc"));
        list.add(new MyString("dd"));

        MyString jointedStr = new MyString(0); //連結した文字列
        int count = 0; //  文字をコピーした数
        
        
        for(MyString str: list){
            // コピー先の文字列
            MyString newJointedStr = 
                new MyString(jointedStr.length() + str.length());

            int i = 0; // コピー時のインデックス値
            
            // 元の文字列を新しい文字列に１字ずつコピー
            for(char c: jointedStr.str){
                newJointedStr.str[i++] = c;
            }
            
            // 追加する文字列を新しい文字列に１字ずつコピー
            for(char c: str.str){
                newJointedStr.str[i++] = c;
            }
            
            // 連結した文字列を更新
            jointedStr = newJointedStr;
            
            // 連結結果の表示
            System.out.println(jointedStr);
            // コピーの回数を表示
            System.out.println(i); 
            
            count += i; // コピーの回数を積算 
        }
        
        // 文字をコピーした回数を表示
        System.out.println(count);
    }
}

結果はこうです。

aa
2
aabb
4
aabbcc
6
aabbccdd
8
20

１回めで文字数の２が、２回めで文字数かける２の４が表示されています。

合計のコピー回数は x (n + 1) * n / 2 計算量では、O(xn^2)の計算量といって間違いではないです。

Comments

[退会済みユーザー]

回答ありがとうございます。
文字列を連結する、つまり
String str = new String("aaa" + "bob");
とiwamoto_takaakiさんの
for(char c: jointedStr.str){
newJointedStr.str[i++] = c;
}

// 追加する文字列を新しい文字列に１字ずつコピー
for(char c: str.str){
newJointedStr.str[i++] = c;
}
は本質的に同じなのでしょうか？
char型の配列を用意して、まずもともとの要素を入れて、次に新しく取り出したMyStringのchar型の配列を入れていますね。
結論部分は確かに同じですが、プロセスが違うような気がするのですが、いかがでしょう？

[iwamoto_takaaki]

Cの文字列を参考に、文字列のメモリ領域がどのようにとられるかということを考えるとこのようになりました。

調べてみると実際そのようになっていることがわかりました。

まずは、Stringは内部にcharの配列を持っています。
http://tomcky.hatenadiary.jp/entry/2013/08/31/002148
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/lang/String.java#String.%3Cinit%3E%28char%5B%5D%29

そうして、StringBuilderによって結合されるようです。
”Java 言語は、文字列連結演算子 ( + )、およびその他のオブジェクトから文字列への変換に対する特別なサポートを提供します。文字列連結は StringBuilder (または StringBuffer) クラスとその append メソッドを使って実装されています。文字列変換は Object によって定義された toString メソッドを使って実装され、Java のクラスすべてによって継承されます。”https://docs.oracle.com/javase/jp/6/api/java/lang/StringBuilder.html

同様にStringBuilderも内部にcharの配列を保持しています。
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/lang/AbstractStringBuilder.java#AbstractStringBuilder.0value

AppendによってStringのcharの配列をStringBuilderのcharの配列にSystem.arrayCopyによってコピーされています。

残念ながらSystem.arrayCopyはネイティブコードなので実装は不明ですが、char配列からchar配列へのコピーという手段をとるのであれば、内部的には１バイトずつのコピーが行われていると予想して問題ないと思います。

単純に興味からの質問ですが、どのようなプロセスを想像していたか教えてください。

[退会済みユーザー]

その質問をした時はStringがchar配列を保持しているなどとは考えてもいなかったので、一気に足されるのではないだろうかと考えておりました。

Stringクラスやその他のことについて色々調べてみました。
String型は実際にはchar配列として保持されているということですが、
String s = "abc";
とした時、どのようなことが起こっているのでしょうか？
APIリファレンスを見ても、ネットで検索してみても、見つかりませんでした。
ほぼ確実に、
value[0] = a, value[1] = b, value[2] = c
となっていると思うのですが、どの部分でこのようになるのでしょうか？
もしご存知だったら、ご教授ください。

[iwamoto_takaaki]

> その質問をした時はStringがchar配列を保持しているなどとは考えてもいなかったので、一気に足されるのではないだろうかと考えておりました。

なるほど、メモリにはポインタやcharやintなどの基本型で保存されているので、分解していけば基本型になります。特に、Stringは特別基本型に近いふるまいをするように設計されているので、混同するのも無理がありません。

> ほぼ確実に、
value[0] = a, value[1] = b, value[2] = c
となっていると思うのですが、どの部分でこのようになるのでしょうか？
もしご存知だったら、ご教授ください。

オブジェクトの中身は知らないで済むところに価値があるので、なかなか書いてないかもしれません。私もそうだと思います。とはいえ、実際のソースを確認するとわかります。

ざっと確認したところ、getCharsメソッドを見るとわかります。
public void getChars(int srcBegin, int srcEnd, char[] dst, int dstBegin)
Stringの所定の中身をchar[]にコピーするメソッドです。

https://docs.oracle.com/javase/jp/6/api/java/lang/String.html#getChars(int, int, char[], int)

ソースを見るとこのようになっています。

853 public void getChars(int srcBegin, int srcEnd, char dst[], int dstBegin) {
854 if (srcBegin < 0) {
855 throw new StringIndexOutOfBoundsException(srcBegin);
856 }
857 if (srcEnd > count) {
858 throw new StringIndexOutOfBoundsException(srcEnd);
859 }
860 if (srcBegin > srcEnd) {
861 throw new StringIndexOutOfBoundsException(srcEnd - srcBegin);
862 }
863 System.arraycopy(value, offset + srcBegin, dst, dstBegin,
864 srcEnd - srcBegin);
865 }

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/lang/String.java#String.getChars%28int%2Cint%2Cchar%5B%5D%2Cint%29

valueの値を並びを変えずにdstにコピーしています。

これだけでも十分だとは思いますが、もっと確認したいのであればdstの中身をテストしてください。

[退会済みユーザー]

回答ありがとうございます。
getCharsメソッドをもちいれば、文字列の任意の部分をchar配列にコピーすることができますね。
そうすると、インスタンス生成の流れは以下のような流れでしょうか？
String s = "abc";
は
char[] datas = {'a', 'b', 'c'}
String s = new String(datas);
と同じのようです。
そして、
文字列"abc"からchar型配列への変換の際にgetCharsメソッドが使われるということでしょうか？

[iwamoto_takaaki]

コードに示してある通り、Stringのchar[] valueに文字列が保存されます。
getCharsで行われていることは、valueからdstへのコピーなので、valueの値を確認できるというわけです。

思っている順序と違っていたら、コンストラクタで確認する必要があるとおもいます。

下記のコードなどいかがでしょうか？
public class Main {
public static void main(String[] args) throws Exception {
char[] chars = new char[3];
"abc".getChars(0, 3, chars, 0);
System.out.println(chars); // -> abc
}
}

[退会済みユーザー]

iwamoto_takaakiさんの意図がようやく理解できました。
iwamoto_takaakiさんは「実験的に」文字列がchar配列で表されているということを示す方法として、getCharメソッドを用いることを提案されたのだと思います。
この実験から、String型がchar配列の形で保持されているということはわかるのですが、その裏にはどのような仕組みがあるのでしょうか？
つまり、
"abc"
とした時にどのような仕組みでそれがchar配列へと保存されるのでしょうか？
お時間がある時に返信をいただければと思います。

[iwamoto_takaaki]

確かに、少し回答に時間がかかりそうです。

JVMやマシン語レベルの話になり、少し思い出したり調べたりに時間がかかります。

簡単に言うとメモリのあるアドレスからあるアドレスにコピーするときは、レジスタのサイズが限度になるので、３２bitのCPUだと１文字が限度になるというところでしょうか。

[iwamoto_takaaki]

時間がかかると書いてしまったので気にしていました。すっかり忘れている質問かもしれませんが・・・

偶然他の質問（https://teratail.com/questions/75460）を観ていた時に、データの転送の仕組みにあたりました。

http://www5d.biglobe.ne.jp/~noocyte/Programming/Alignment.html
こちらの”２．アラインメントは何か？”のところです。

CPUとメモリはバス幅を限度に通信をしています。コピー元の配列のアドレスからコピー先のアドレスに書き込む際は、３２bitのCPUの場合アスキー文字を一度に４文字までコピーすることが出来ます。（文字のエンコードにサイズは異なる。）

文字列の連結はコピー元その１とコピー元その２をコビー先のアドレスに向かって32bitずつコピーすることになります。

また、プログラムから”abc”を読み込む際は、メモリ上に読み込んだ中間コードの”abc”が格納されたchar[]をクラス変数なりメソッドの変数なりの先頭アドレスからデータバスの幅でコピーすることになります。その正確な回数はCPUやエンコードに左右されるので一概にはいえないと思いますが、計算量の計算はオーダーで考えるので、１文字１回と計算しても問題ないと考えての記述のように思いえます。

Answer 2

「文字列のリストを連結する～」とあるので、以下のようなコードになると思います。

import java.lang.String;
import java.util.Arrays;
import java.util.List;

public class Hoge {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("aaa", "bbb", "ccc");

        String result = "";
        for (String s : list) {
            result += s;
            System.out.println(result);
        }
    }
}

結果は以下の通りで、説明の通りになるかと。

aaa
aaabbb
aaabbbccc

Comments

[退会済みユーザー]

回答ありがとうございました。

Answer 3

よく分からない文章なので、推測するしか無いですが、「最初の繰り返し」というのは、

String newString = new String("" +"aaa");

なのでしょう。繰り返しをn回すると言うことなのでしょう。

Comments

[退会済みユーザー]

回答ありがとうございました。