🍌

Go の文字列結合が遅い理由 ― Count and Say で学ぶ高速化の要点

に公開
Go
string
tech

概要

  • LeetCode の “Count and Say” 問題で、Go 言語における string と []byte の性能差が顕著に生じた。
  • 自前で書いた RLE（Run-Length Encoding 風）実装では 8 ms、公式サンプルでは 0 ms。
  • この差を生んだ原因は、文字列のイミュータビリティとメモリ割り当ての仕組み、数値変換コストだった。

問題の概要

Count and Say は、与えられた文字列（例："11"）を「同じ数字の連続回数」と「その数字」で表現して次の文字列を生成する問題です。

例：

"1" → "11" → "21" → "1211" → "111221" → ...

RLE（Run-Length Encoding）に近い処理ですが、対象が数字列に限られている点が特徴的です。

実装比較

説明に必要箇所のみ抜き出しています。

自前実装（8 ms）

func countAndSay(n int) string {
	if n == 1 {
		return "1"
	}
	if n == 2 {
		return "11"
	}
	count := "11"
	for i := 3; i <= n; i++ {
		count += "*"
		temp := ""
		counter := 1
		for j := 0; j < len(count)-1; j++ {
			if count[j+1] != count[j] {
				temp += strconv.Itoa(counter) + string(count[j])
				counter = 1
			} else {
				counter++
			}
		}
		count = temp
	}
	return count
}

このコードでは、各ループで string を + 演算子で結合しています。

サンプル実装（0 ms）

func RLE(s string) string { // n回分呼び出す
  ans := []byte{}
  i, n := 0, len(s)
  for i < n {
    ch, cnt := s[i], 0
    for i < n && ch == s[i] {
      cnt++
      i++
    }
    ans = append(ans, byte(cnt) + '0', ch)
  }
  return string(ans)
}

こちらは []byte を使って結果を構築し、最後に一度だけ string(ans) に変換しています。

処理時間の差を生む理由

1. string はイミュータブル

Go の string はイミュータブルであり、+ による連結は毎回新しいメモリ確保と全コピーを伴います。

s = s + "abc" // 毎回新しい string が生成され、既存文字列が全コピーされる

そのため、文字列長が増えるたびに O(n²) に近いコストが発生します。
長い文字列を逐次構築する処理では致命的な性能低下を招きます。

2. []byte は可変バッファ

一方、[]byte は可変長配列であり、append は平均的に O(1) です。
内部バッファが満杯になるまではコピーが発生せず、全体で O(n) に抑えられます。

ans := []byte{}
ans = append(ans, ch)

この仕組みにより、サンプル実装では不要な中間文字列を生成せずに済みます。

余談ですが、Go にはもう一つ、同様の用途に適した strings.Builder という構造体があります。
こちらは内部的に []byte を保持しており、可変バッファを安全に扱えるよう抽象化したものです。
次のように使えます。

var b strings.Builder
b.WriteString("abc")
b.WriteByte('d')
result := b.String()

strings.Builder は文字列処理を意図した高レベルなAPIであり、[]byte よりも安全に、かつほぼ同等の性能で文字列を構築できます。
大量連結やテンプレート生成など、より一般的な用途では strings.Builder の使用が推奨されます。

3. 数値変換コスト

サンプル実装では byte(cnt) + '0' により ASCII 値を利用して即座に文字化しています。
これは 1桁（1〜9）限定の高速手法で、strconv.Itoa(cnt) より軽量です。
ただし、cnt が 10 以上になる場合は不正な文字になるため、使い分けが必要です。

4. メモリ割り当ての回数

自前実装：各連結で新規割り当て → 多数発生
サンプル実装：[]byte バッファを再利用 → 1回の string(ans) のみ

最終的な変換は O(n) のコピーを伴いますが、1回だけなので与える影響は小さいです。

まとめ

観点 自前実装 サンプル実装
文字列構築 string + +（毎回新規生成） []byte に逐次 append
計算量 O(n²) に近い O(n)
数値→文字 strconv.Itoa byte(cnt)+'0'
メモリ割り当て 多数 最小限（1回）

学んだこと：

  • Go の string はイミュータブルであり、結合にはコストがかかる。
  • 大量連結が発生する処理は []byte または strings.Builder を使うべき。
  • 数値変換は桁数に応じて byte(cnt)+'0' と strconv.Itoa を使い分ける。
  • 最後に一度だけ string(ans) に変換するのが最適。

補足：より安全な汎用版

もし cnt が 10 以上になる可能性がある場合は、次のように strconv.Itoa を使う方が安全です。

ans = append(ans, []byte(strconv.Itoa(cnt))...)
ans = append(ans, ch)

性能はわずかに落ちますが、汎用性と正確性が保たれます。

結論

今回のケースでは、文字列結合の実装選択が 8 ms と 0 ms の差を生みました。
Go における「イミュータブルな文字列」と「可変なバイト配列」の違いを理解することは、
高速な文字列処理を設計するうえで欠かせません。

Discussion