はじめに

新卒入社し、現在エンジニアのオンボーディング中です。
同期から誘われてAtCoder Beginner Contestに毎週参加しています。

今回はAtCoderで学んだ内の1つである、StringBuilderについて自分用のメモとしてまとめます。

そもそもAtCoderとは？

プログラミング未経験の同期も読んでくれていると思うので、簡単に紹介します。
AtCoderは、競技プログラミング（競プロ） のプラットフォームです。

与えられた課題（アルゴリズムの問題）に対し、「いかに正確に」「いかに早く処理が終わるか」を競います。問題はA, B, C, D...と難易度が上がっていくのですが、「ただ答えが出るだけ」のプログラムでは TLE（Time Limit Exceeded：実行時間オーバー） というエラーになってしまう問題もあります。

限られた時間（多くは2秒以内）で処理を終えるために、効率の良いプログラムを書く能力が求められます。

「処理の速さ」を測るオーダー記法

効率の良いプログラムを考える際、「 オーダー記法 」という言葉がよく登場します。これは、$O(N)$ や $O(N^2)$ のように書き、「データ量 $N$ が増えたとき、処理回数がどう増えるか」を大まかに表す指標です。

$O(N)$：データが10倍になれば、処理時間も10倍と比例して増えます。
$O(N^2)$：データが10倍になれば、処理時間は 100倍 になります。

具体例：文字を繋げて答えを作る問題

競プロのイメージを掴んでもらうために、実際の簡単な問題を例に出してみます。
（出典：ABC348 A - Penalty Kick）

【問題の要約】
ペナルティキックを $N$ 回蹴ります。
3の倍数回目（3回目、6回目、9回目...）は失敗してしまいますが、それ以外は成功します。
成功を o、失敗を x として、キックの結果を文字列で出力してください。

（例：$N=7$ の場合、結果は ooxooxo となります）

条件（3で割り切れるかどうか）を判定しながら、文字を一つひとつ繋げていくシンプルな問題です。

これをJavaで解こうとした時、最初は直感的に以下のように書いていました。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        String result = ""; // 空の文字列を用意
        
        // N回ループを回して文字を繋げていく
        for (int i = 1; i <= N; i++) {
            if (i % 3 == 0) {
                result += "x"; // 3の倍数なら "x" を追加
            } else {
                result += "o"; // それ以外なら "o" を追加
            }
        }
        System.out.println(result);
    }
}

このA問題は $N$ の制約が最大でも $100$ なので、これでも正解（AC）になります。

しかし、$N$の数が大きくなればなるほど実行時間が増加し続けてしまいます。

本題：なぜ `+=` は遅いのか？

Javaの String は イミュータブル（不変） という性質を持っています。一度作られた文字列は後から変更することができません。

つまり result += "x" や result += "o" を実行するたびに、単に文字を後ろにくっつけているわけではなく、内部では以下のような重い処理が走っています。（参考：JavaのString型は不変(Immutable)であるという話 - Qiita）。

今の文字列をまるごとコピーする
最後に "o" をくっつける
全く新しい文字列としてメモリ上に作り直す

これを $N$ 回繰り返すと、コピーする文字数は $1 + 2 + 3 + ... + N$ となり、計算量は $O(N^2)$ に増加してしまいます。

具体的にどれくらいのコピー処理が発生しているのか、等差数列の和の公式を使って計算してみます。

$$1 + 2 + 3 + \dots + N = \frac{N(N+1)}{2} = \frac{1}{2}N^2 + \frac{1}{2}N$$

オーダー記法（$O$）のルールでは、「最も影響の大きい最高次の項（この場合は $N^2$）」に注目し、それ以外の項や係数（$\frac{1}{2}$ など）は無視して考えます。

そのため、最終的な全体の計算量は $O(N^2)$ になります。

すべての += が遅いわけではありません

「+= 演算子そのものが遅い」のではなく、「複数行（特にループ内）にわたって += で文字列を注ぎ足していく書き方が遅い」 という意味です。

（参考：[Java] Stringの結合について - Qiita）。

StringBuilderの登場

$N$が大きくなっても実行時間を大幅に増加させない方法はないのか？

そこで登場するのが StringBuilder です。

こちらは内部に「文字を入れる箱（バッファ）」を持っており、append メソッドを使うと、その箱の隙間に文字を追加していくだけの処理になります。

毎回新しい文字列を作り直す必要がないため、計算量は $O(N)$ で済みます。先ほどのコードを StringBuilder で書き直すとこうなります。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        // 文字列の代わりに StringBuilder を用意
        StringBuilder sb = new StringBuilder(); 
        
        for (int i = 1; i <= N; i++) {
            if (i % 3 == 0) {
                sb.append("x"); // appendで箱に追加していく
            } else {
                sb.append("o");
            }
        }
        // 最後に一気に文字列に変換して出力
        System.out.println(sb.toString()); 
    }
}

コードの見た目はほとんど変わりませんが、中身の動きは全く別物になります。

本当にそんなに違うの？Javaで計測してみた

理屈は分かりましたが、実際に「$O(N^2)$ の +=」と「$O(N)$ の StringBuilder」でどれくらい実行時間に差が出るのか、検証コードを書いて実験してみました。

AtCoderの制約を意識し、ループ回数 $N$ を 2万回から 20万回まで変化させながら、それぞれの処理にかかった時間をミリ秒（ms）単位で計測します。

1. Javaで実行時間を計測してCSV形式で出力

単発の計測では、Javaの起動直後のオーバーヘッドや、実行中にコードが最適化されるタイミング（JITコンパイル）によって、結果に大きなブレが生じてしまいます。

オーバーヘッドとは？
「本質的な処理以外にかかってしまう、前後の準備時間や余計なコスト」のことです。Javaが起動した直後は、プログラムを動かすための準備（メモリ確保など）が裏で走るため、どうしても1回目の計測が遅くなってしまうという特徴があります。
JIT（ジット）コンパイルとは？
Javaが「プログラムを動かしながら、何度も繰り返し走る重い処理を見つけて、その場で超高速な機械語に自動で翻訳・書き換えてくれる仕組み」のことです。最初は翻訳しながらゆっくり動きますが、ループを回すうちにこの機能が発動し、途中から急に処理が最適化されて速くなります。

この 「最初の準備で遅い（オーバーヘッド）」 と 「途中から急に強くなる（JITコンパイル）」 というJavaの特性があるため、1回だけの測定では正確なデータが取れません。

そこで今回は、データの信頼性と再現性を高めるために、以下の工夫を取り入れた計測コードを作成しました。

ウォームアップ（準備運動）の導入：本番計測の前に、あらかじめ各処理を10回ずつ空回ししてエンジン（JVM）を十分に温めておきます。
複数回計測と平均化：本番では各ループ回数ごとに100回ずつ処理を実行し、その平均時間を算出します。

実際の計測コードがこちらです。

public class Main {
    public static void main(String[] args) {
        int[] nValues = {20000, 40000, 60000, 80000, 100000, 120000, 140000, 160000, 180000, 200000};
        
        System.out.println("N,StringTime_ms,StringBuilderTime_ms");

        for (int n : nValues) {
            // ウォームアップ（本番前にエンジンを温める）
            // ここでの実行時間は計測せず、捨てる
            for (int w = 0; w < 10; w++) {
                runString(n);
                runStringBuilder(n);
            }

            // 本番計測（100回実行して平均値を出す）
            int trialCount = 100;
            
            double totalStringTime = 0;
            for (int i = 0; i < trialCount; i++) {
                long start = System.nanoTime();
                runString(n);
                totalStringTime += (System.nanoTime() - start) / 1000000.0;
            }
            double avgStringTime = totalStringTime / trialCount;

            double totalBuilderTime = 0;
            for (int i = 0; i < trialCount; i++) {
                long start = System.nanoTime();
                runStringBuilder(n);
                totalBuilderTime += (System.nanoTime() - start) / 1000000.0;
            }
            double avgBuilderTime = totalBuilderTime / trialCount;

            // 平均値を出力
            System.out.println(n + "," + avgStringTime + "," + avgBuilderTime);
        }
    }

    // 各処理をメソッドに分離
    private static void runString(int n) {
        String str = "";
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0) str += "x";
            else str += "o";
        }
    }

    private static void runStringBuilder(int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0) sb.append("x");
            else sb.append("o");
        }
    }
}

この計測用のJavaプログラムを実行すると、以下のような結果が出力されました。

N,StringTime_ms,StringBuilderTime_ms
20000,16.626944000000005,0.04062300000000001
40000,78.676149,0.16340800000000003
60000,180.86870900000002,0.08210300000000002
80000,268.1814589999999,0.12069399999999998
100000,588.1925200000002,0.3926939999999999
120000,643.7204569999999,0.16142100000000006
140000,902.1697889999997,0.21486500000000003
160000,1165.667619,0.29133000000000014
180000,1726.6903869999996,0.25048200000000015
200000,2517.7169320000003,0.275519

2. Pythonでデータの可視化

この計測結果を元にGoogle colabにてPythonの matplotlib を使って可視化してみます。

import pandas as pd
import matplotlib.pyplot as plt
import io
import japanize_matplotlib

# java計測データ
data = """
N,StringTime_ms,StringBuilderTime_ms
20000,16.626944000000005,0.04062300000000001
40000,78.676149,0.16340800000000003
60000,180.86870900000002,0.08210300000000002
80000,268.1814589999999,0.12069399999999998
100000,588.1925200000002,0.3926939999999999
120000,643.7204569999999,0.16142100000000006
140000,902.1697889999997,0.21486500000000003
160000,1165.667619,0.29133000000000014
180000,1726.6903869999996,0.25048200000000015
200000,2517.7169320000003,0.275519
"""

df = pd.read_csv(io.StringIO(data))

# グラフの描画設定
plt.figure(figsize=(10, 6))

# 各データのプロット
plt.plot(df['N'], df['StringTime_ms'], marker='o', color='red', label='通常の文字列結合 (+=)')
plt.plot(df['N'], df['StringBuilderTime_ms'], marker='s', color='blue', label='StringBuilder (.append)')

# グラフの装飾
plt.title('Javaにおける文字列結合の実行時間比較', fontsize=14)
plt.xlabel('ループ回数 (N)', fontsize=12)
plt.ylabel('実行時間 (ミリ秒)', fontsize=12)
plt.legend(fontsize=12)
plt.grid(True)
plt.tight_layout()

plt.show()

出力されたグラフがこちら

この環境では、+=とStringBuilderの差がグラフ上でも確認できました。
ただし、StringBuilder 側は値が小さく、計測誤差の影響を受けやすい点には注意が必要です。

青線（StringBuilder）：データ量が20万回に増えても、わずか数ミリ秒 （今回の条件では StringBuilder の計測値が非常に小さかった）で処理が終わっています。
赤線（String (+=)）：データ量 $N$ が増えるにつれて、二次関数のように実行時間が上昇しています。

この実験環境では、StringBuilder の方が大幅に高速だったという結果が得られました。

さいごに

今回はAtCoderで学んだStringBuilderについてまとめてみました。

実際、AtCoderで同期のコードを見てみるとStringBuilderを使わずとも正解しているので、使わなくてもいけちゃうのかと思っています。

でもそれでTLEになったら悔しいので判断が難しいところですね。

記事を書いていく中でも新しい知識をキャッチアップすることができたので良かったです！