[インデックス 15291] ファイルの概要

このコミットは、Go言語の標準ライブラリstringsパッケージにおけるCount関数とIndex関数のパフォーマンス改善を目的としています。具体的には、これらの文字列検索・計数処理において、最悪計算量（ワーストケース）の効率を向上させるために、確率的アルゴリズムであるRabin-Karpアルゴリズムを導入しています。これにより、特に特定のパターン（「ハード」および「拷問」ベンチマークで示されるような）において、大幅な速度向上が実現されています。

コミット

commit 23093f86eebbefb0cf11298c45513da360d2b48d
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Sun Feb 17 13:07:17 2013 +0100

    strings: better mean complexity for Count and Index.
    
    The O(n+m) complexity is obtained probabilistically
    by using Rabin-Karp algorithm, which provides the needed complexity
    unless exceptional collisions occur, without memory allocation.
    
    benchmark                 old ns/op    new ns/op    delta
    BenchmarkIndexHard1         6532331      4045886  -38.06%
    BenchmarkIndexHard2         8178173      4038975  -50.61%
    BenchmarkIndexHard3         6973687      4042591  -42.03%
    BenchmarkCountHard1         6270864      4071090  -35.08%
    BenchmarkCountHard2         7838039      4072853  -48.04%
    BenchmarkCountHard3         6697828      4071964  -39.20%
    BenchmarkIndexTorture       2730546        28934  -98.94%
    BenchmarkCountTorture       2729622        29064  -98.94%
    
    Fixes #4600.
    
    R=rsc, donovanhide, remyoudompheng
    CC=golang-dev
    https://golang.org/cl/7314095

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/23093f86eebbefb0cf11298c45513da360d2b48d

元コミット内容

このコミットの元のメッセージは以下の通りです。

strings: better mean complexity for Count and Index.

The O(n+m) complexity is obtained probabilistically
by using Rabin-Karp algorithm, which provides the needed complexity
unless exceptional collisions occur, without memory allocation.

benchmark                 old ns/op    new ns/op    delta
BenchmarkIndexHard1         6532331      4045886  -38.06%
BenchmarkIndexHard2         8178173      4038975  -50.61%
BenchmarkIndexHard3         6973687      4042591  -42.03%
BenchmarkCountHard1         6270864      4071090  -35.08%
BenchmarkCountHard2         7838039      4072853  -48.04%
BenchmarkCountHard3         6697828      4071964  -39.20%
BenchmarkIndexTorture       2730546        28934  -98.94%
BenchmarkCountTorture       2729622        29064  -98.94%

Fixes #4600.

R=rsc, donovanhide, remyoudompheng
CC=golang-dev
https://golang.org/cl/7314095

このメッセージは、strings.Countおよびstrings.Index関数の平均計算量を改善したことを明確に述べています。改善はRabin-Karpアルゴリズムの採用によって達成され、これにより確率的にO(n+m)の計算量（nはテキストの長さ、mはパターンの長さ）が実現され、メモリ割り当てなしで動作すると説明されています。また、具体的なベンチマーク結果が示されており、特に「Torture」ベンチマークでは98%以上の大幅な性能向上が確認できます。これはIssue #4600の修正に関連しています。

変更の背景

この変更の背景には、Go言語のstringsパッケージにおけるCountおよびIndex関数の既存の実装が、特定の入力パターンに対して非効率的であったという問題があります。特に、検索対象の文字列（s）と検索パターン（sep）が長い場合や、パターンが文字列中に頻繁に出現するが完全に一致しないような「最悪ケース」において、線形探索（ナイーブな文字列検索アルゴリズム）ではO(nm)の計算量となり、パフォーマンスが著しく低下する可能性がありました。

Issue #4600（"strings: Index and Count are slow for some inputs"）は、まさにこのパフォーマンス問題を指摘していました。ユーザーは、特定の種類の入力（例えば、非常に長い文字列内で、検索パターンが繰り返し現れるが、最後の文字で常に不一致となるようなケース）において、これらの関数が期待よりもはるかに遅いことを報告していました。

このコミットは、このような最悪ケースのパフォーマンスを改善し、より堅牢で効率的な文字列検索・計数機能を提供することを目的としています。Rabin-Karpアルゴリズムの導入により、平均的にはO(n+m)という線形時間での処理が可能となり、実用的な多くのシナリオで高速な動作が期待できるようになります。

前提知識の解説

文字列検索アルゴリズム

文字列検索（String Searching）は、あるテキスト（s）の中に特定のパターン（sep）が出現するかどうか、あるいはどこに出現するかを見つける問題です。この問題には様々なアルゴリズムが存在し、それぞれ計算量や特性が異なります。

1. ナイーブ（線形探索）アルゴリズム: 最も単純な方法で、テキストの先頭から順に、パターンと一致するかどうかを比較していきます。一致しない場合は、テキストの次の位置から再度比較を開始します。

   • 最悪計算量: O(nm) (nはテキスト長、mはパターン長)。例えば、テキストが "AAAAAAB" でパターンが "AAB" のような場合、多くの部分的な一致が発生し、比較回数が多くなります。
   • 利点: 実装が簡単。
   • 欠点: 最悪ケースで非常に遅くなる。

2. KMP法 (Knuth-Morris-Pratt Algorithm): ナイーブ法が非効率になる原因は、不一致が発生した際に、既に比較したテキストの部分を再度比較してしまう点にあります。KMP法は、パターンの内部構造（プレフィックスとサフィックスの一致）を利用して、不一致が発生した際に比較をスキップできる量を計算し、無駄な再比較を避けます。

   • 計算量: O(n+m)。
   • 利点: 常に線形時間で動作する。
   • 欠点: アルゴリズムの理解と実装がやや複雑。

3. Boyer-Moore法: KMP法とは異なり、パターンの末尾から先頭に向かって比較を行います。不一致が発生した場合、パターンを大きくスキップできる可能性があります。

   • 平均計算量: O(n/m) (非常に高速)。
   • 最悪計算量: O(nm)。
   • 利点: 多くの実用的なケースで非常に高速。
   • 欠点: 最悪ケースが存在する。

4. Rabin-Karpアルゴリズム: このコミットで採用されたアルゴリズムです。ハッシュ関数を利用して文字列を比較します。テキストの各部分文字列のハッシュ値を計算し、それがパターンのハッシュ値と一致するかどうかを調べます。ハッシュ値が一致した場合のみ、実際の文字列比較を行います（ハッシュ衝突の可能性を排除するため）。

   • 平均計算量: O(n+m)。
   • 最悪計算量: O(nm) (ハッシュ衝突が頻繁に発生する場合)。
   • 利点: 実装が比較的簡単で、複数のパターンを同時に検索するのに適している。ローリングハッシュにより効率的にハッシュ値を更新できる。
   • 欠点: ハッシュ衝突の可能性があり、最悪ケースでは性能が低下する。ただし、適切なハッシュ関数と素数を選択することで、衝突の確率は非常に低く抑えられる。

ローリングハッシュ (Rolling Hash)

Rabin-Karpアルゴリズムの効率を支える重要な技術がローリングハッシュです。これは、テキストの連続する部分文字列のハッシュ値を効率的に計算する方法です。

通常のハッシュ計算では、部分文字列ごとに最初からハッシュ値を計算し直す必要がありますが、ローリングハッシュでは、前の部分文字列のハッシュ値から、次の部分文字列のハッシュ値を定数時間（O(1)）で計算できます。

例えば、文字列 S = "ABCDE" とハッシュ関数 H(str) を考えます。 H("ABC") を計算した後、H("BCD") を計算したい場合、H("ABC") の値から A の寄与を減算し、D の寄与を加算することで、効率的に H("BCD") を得ることができます。

一般的に、多項式ハッシュ（Polynomial Hashing）が用いられます。これは、文字列をある基数（通常は素数）の多項式として解釈し、その値を別の素数で割った余りをハッシュ値とする方法です。

H(c_1 c_2 ... c_k) = (c_1 * p^(k-1) + c_2 * p^(k-2) + ... + c_k * p^0) mod M

ここで、p は基数（primeRK）、M はモジュロ（通常は大きな素数）です。

次の部分文字列 c_2 c_3 ... c_k c_{k+1} のハッシュ値は、以下のように計算できます。

H(c_2 ... c_{k+1}) = ((H(c_1 ... c_k) - c_1 * p^(k-1)) * p + c_{k+1}) mod M

この計算により、O(1)でハッシュ値を更新できます。

ハッシュ衝突 (Hash Collision)

ハッシュ衝突とは、異なる入力データが同じハッシュ値を持つ現象です。Rabin-Karpアルゴリズムでは、ハッシュ値が一致しても、実際の文字列が一致しない可能性があります。このため、ハッシュ値が一致した場合には、必ず元の文字列同士を比較して、真の一致であるかを確認する必要があります。適切なハッシュ関数と大きな素数を選択することで、ハッシュ衝突の確率は非常に低く抑えられ、平均計算量をO(n+m)に保つことができます。

技術的詳細

このコミットでは、Go言語のstringsパッケージ内のCount関数とIndex関数にRabin-Karpアルゴリズムを適用しています。

Rabin-Karpアルゴリズムの適用

1. ハッシュ関数の導入: primeRKという定数（16777619）が導入されています。これはRabin-Karpアルゴリズムで使用される素数基数です。 hashstr(sep string) (uint32, uint32)関数が新しく追加されました。この関数は、検索パターンsepのハッシュ値と、ローリングハッシュの計算に必要なpow（primeRKのlen(sep)乗）を計算します。

   • hash: パターンsepのハッシュ値を計算します。
   • pow: primeRKをlen(sep)回掛け合わせた値（primeRK^(len(sep))）を計算します。これは、ローリングハッシュで最も古い文字の寄与を削除する際に使用されます。

2. Count関数の変更:

   • 以前は、sepの長さが1の場合に特殊な高速パスがありましたが、それ以外の場合はナイーブな線形探索を行っていました。
   • 新しい実装では、len(sep) > len(s)の場合は0を返します。
   • hashsep, pow := hashstr(sep)でパターンのハッシュ値とpowを計算します。
   • 最初のlen(sep)文字のハッシュ値hを計算します。
   • メインのループでは、ローリングハッシュの原理を適用します。
     • h == hashsepの場合、ハッシュ値が一致したと判断し、s[i-len(sep):i] == sepで実際の文字列比較を行います。これはハッシュ衝突の確認です。
     • 一致した場合、nをインクリメントし、lastmatchを更新します。lastmatchは、重複するカウントを避けるために、最後に一致した位置を記録します。
     • ループの各イテレーションで、hを更新します。h = h*primeRK + uint32(s[i])で新しい文字s[i]の寄与を加え、h -= pow * uint32(s[i-len(sep)])で最も古い文字s[i-len(sep)]の寄与を削除します。

3. Index関数の変更:

   • Count関数と同様に、len(sep)が1の場合の特殊な高速パスは残しつつ、それ以外の場合にRabin-Karpアルゴリズムを適用します。
   • nはlen(sep)を指します。
   • hashsep, pow := hashstr(sep)でパターンのハッシュ値とpowを計算します。
   • 最初のn文字のハッシュ値hを計算します。
   • メインのループでは、ローリングハッシュの原理を適用します。
     • h == hashsepの場合、ハッシュ値が一致したと判断し、s[i-n:i] == sepで実際の文字列比較を行います。
     • 一致した場合、i - n（一致した開始インデックス）を返します。
     • ループの各イテレーションで、hを更新します。h = h*primeRK + uint32(s[i])で新しい文字s[i]の寄与を加え、h -= pow * uint32(s[i-n])で最も古い文字s[i-n]の寄与を削除します。

パフォーマンスの改善

コミットメッセージに示されているベンチマーク結果は、Rabin-Karpアルゴリズムの導入による劇的なパフォーマンス改善を明確に示しています。

• BenchmarkIndexHard1/2/3, BenchmarkCountHard1/2/3: これらのベンチマークは、特定の「ハード」な入力パターンに対する性能を測定しています。ナイーブなアルゴリズムでは多くの部分的な一致が発生し、比較回数が増えるようなケースです。Rabin-Karpの導入により、これらのケースで35%から50%の性能向上が見られます。これは、ハッシュ比較によって不要な文字列比較が大幅に削減されたためです。
• BenchmarkIndexTorture, BenchmarkCountTorture: これらの「拷問」ベンチマークは、Rabin-Karpアルゴリズムが特に効果を発揮する最悪ケースに近いシナリオを想定しています。例えば、非常に長い文字列と、その文字列のほとんどの部分で一致するが、最後の1文字で不一致となるような長いパターンを検索するケースです。このベンチマークでは、なんと98%以上の性能向上が達成されています。これは、ローリングハッシュによってハッシュ値の計算が非常に効率的になり、かつハッシュ衝突がほとんど発生しないため、実際の文字列比較が最小限に抑えられた結果です。

この改善は、Go言語のstringsパッケージが提供する基本的な文字列操作の効率を大幅に向上させ、Goアプリケーション全体のパフォーマンスに良い影響を与えるものです。

コアとなるコードの変更箇所

src/pkg/strings/strings.go

// primeRK is the prime base used in Rabin-Karp algorithm.
const primeRK = 16777619

// hashstr returns the hash and the appropriate multiplicative
// factor for use in Rabin-Karp algorithm.
func hashstr(sep string) (uint32, uint32) {
	hash := uint32(0)
	for i := 0; i < len(sep); i++ {
		hash = hash*primeRK + uint32(sep[i])
	}
	var pow, sq uint32 = 1, primeRK
	for i := len(sep); i > 0; i >>= 1 {
		if i&1 != 0 {
			pow *= sq
		}
		sq *= sq
	}
	return hash, pow
}

// Count counts the number of non-overlapping instances of sep in s.
func Count(s, sep string) int {
	if sep == "" {
		return utf8.RuneCountInString(s) + 1
	}
	c := sep[0]
	if len(sep) == 1 {
		// special case worth making fast
		for i := 0; i < len(s); i++ {
			if s[i] == c {
				n++
			}
		}
		return n
	}
	if len(sep) > len(s) {
		return 0
	}
	hashsep, pow := hashstr(sep)
	h := uint32(0)
	for i := 0; i < len(sep); i++ {
		h = h*primeRK + uint32(s[i])
	}
	lastmatch := 0
	for i := len(sep); ; i++ {
		// Invariant: h = hash(s[i-l : i])
		if h == hashsep && lastmatch <= i-len(sep) && s[i-len(sep):i] == sep {
			n++
			lastmatch = i
		}
		if i >= len(s) {
			break
		}
		h = h*primeRK + uint32(s[i])
		h -= pow * uint32(s[i-len(sep)])
	}
	return n
}

// Index returns the index of the first instance of sep in s, or -1 if sep is not present in s.
func Index(s, sep string) int {
	// ... (既存の短い文字列や空文字列のチェックは省略)
	n := len(sep)
	if n == 0 {
		return 0
	}
	if n > len(s) {
		return -1
	}
	// Hash sep.
	hashsep, pow := hashstr(sep)
	var h uint32
	for i := 0; i < n; i++ {
		h = h*primeRK + uint32(s[i])
	}
	for i := n; ; i++ {
		// Invariant: h = hash(s[i-n : i])
		if h == hashsep && s[i-n:i] == sep {
			return i - n
		}
		if i >= len(s) {
			break
		}
		h = h*primeRK + uint32(s[i])
		h -= pow * uint32(s[i-n])
	}
	return -1
}

src/pkg/strings/strings_test.go

func makeBenchInputHard() string {
	tokens := [...]string{
		"<a>", "<p>", "<b>", "<strong>",
		"</a>", "</p>", "</b>", "</strong>",
		"hello", "world",
	}
	x := make([]byte, 0, 1<<20)
	for len(x) < 1<<20 {
		i := rand.Intn(len(tokens))
		x = append(x, tokens[i]...)
	}
	return string(x)
}

var benchInputHard = makeBenchInputHard()

func benchmarkIndexHard(b *testing.B, sep string) {
	for i := 0; i < b.N; i++ {
		Index(benchInputHard, sep)
	}
}

func benchmarkCountHard(b *testing.B, sep string) {
	for i := 0; i < b.N; i++ {
		Count(benchInputHard, sep)
	}
}

func BenchmarkIndexHard1(b *testing.B) { benchmarkIndexHard(b, "<>") }
func BenchmarkIndexHard2(b *testing.B) { benchmarkIndexHard(b, "</pre>") }
func BenchmarkIndexHard3(b *testing.B) { benchmarkIndexHard(b, "<b>hello world</b>") }

func BenchmarkCountHard1(b *testing.B) { benchmarkCountHard(b, "<>") }
func BenchmarkCountHard2(b *testing.B) { benchmarkCountHard(b, "</pre>") }
func BenchmarkCountHard3(b *testing.B) { benchmarkCountHard(b, "<b>hello world</b>") }

var benchInputTorture = Repeat("ABC", 1<<10) + "123" + Repeat("ABC", 1<<10)
var benchNeedleTorture = Repeat("ABC", 1<<10+1)

func BenchmarkIndexTorture(b *testing.B) {
	for i := 0; i < b.N; i++ {
		Index(benchInputTorture, benchNeedleTorture)
	}
}

func BenchmarkCountTorture(b *testing.B) {
	for i := 0; i < b.N; i++ {
		Count(benchInputTorture, benchNeedleTorture)
	}
}

コアとなるコードの解説

src/pkg/strings/strings.go

• const primeRK = 16777619: Rabin-Karpアルゴリズムで使用される素数基数です。この値は、ハッシュ衝突を最小限に抑えるために慎重に選ばれた大きな素数です。

• func hashstr(sep string) (uint32, uint32): この関数は、検索パターンsepのハッシュ値と、ローリングハッシュ計算に必要なpow（primeRKのlen(sep)乗）を計算します。

  • 最初のループで、パターンsepの各文字をprimeRKを基数とする多項式ハッシュとして計算し、hashに格納します。
  • 2番目のループは、pow = primeRK^(len(sep))を効率的に計算するためのものです。これは、バイナリ法（Exponentiation by squaring）を用いて、primeRKをlen(sep)乗しています。このpowの値は、ローリングハッシュの際に、ウィンドウから外れる文字の寄与を正確に減算するために必要です。

• Count関数とIndex関数のRabin-Karp実装: 両関数とも、len(sep) == 1の特殊ケース（単一文字の検索）は既存の高速パスを維持しています。これは、単一文字の検索ではRabin-Karpのオーバーヘッドが大きいため、よりシンプルな線形探索が効率的だからです。

  • 初期ハッシュ計算: hashsep, pow := hashstr(sep)でパターンのハッシュ値とpowを計算します。次に、検索対象文字列sの最初のlen(sep)文字（またはn文字）のハッシュ値hを計算します。
  • ローリングハッシュループ:
    • for i := len(sep); ; i++ (または for i := n; ; i++) のループが、文字列sを走査します。iは現在のウィンドウの終端インデックスを示します。
    • if h == hashsep && ... && s[i-len(sep):i] == sep (または s[i-n:i] == sep) の条件がRabin-Karpの核心です。
      • h == hashsep: 現在のウィンドウのハッシュ値がパターンのハッシュ値と一致するかどうかをチェックします。
      • s[i-len(sep):i] == sep: ハッシュ値が一致した場合、ハッシュ衝突の可能性を排除するために、実際の文字列比較を行います。これが真の一致であるかを確認するステップです。
      • lastmatch <= i-len(sep) (Count関数のみ): Count関数では重複するカウントを避けるため、最後に一致した位置よりも後でなければカウントしないようにします。
    • h = h*primeRK + uint32(s[i]): 現在のウィンドウに新しい文字s[i]を追加し、ハッシュ値を更新します。
    • h -= pow * uint32(s[i-len(sep)]): ウィンドウから外れる最も古い文字s[i-len(sep)]（またはs[i-n]）の寄与をハッシュ値から減算します。これにより、ハッシュ値が効率的に「スライド」します。
    • if i >= len(s) { break }: 文字列の終端に達したらループを終了します。

src/pkg/strings/strings_test.go

• makeBenchInputHard(): この関数は、Rabin-Karpアルゴリズムが効果を発揮するような「ハード」な入力文字列を生成します。HTMLタグや一般的な単語のトークンをランダムに連結して、約1MBの文字列を作成します。これにより、部分的な一致が多く発生し、ナイーブなアルゴリズムでは非効率になるようなシナリオをシミュレートします。

• benchmarkIndexHard / benchmarkCountHard: makeBenchInputHardで生成された文字列と、特定の検索パターン（例: "<>", "</pre>", "<b>hello world</b>"）を使用して、IndexおよびCount関数のベンチマークを実行します。

• benchInputTorture / benchNeedleTorture: これらの変数は、Rabin-Karpアルゴリズムの「拷問」ベンチマークのために特別に設計された入力です。

  • benchInputTorture = Repeat("ABC", 1<<10) + "123" + Repeat("ABC", 1<<10): 非常に長い文字列で、"ABC"が繰り返し出現し、中央に異なるパターン"123"が挿入されています。
  • benchNeedleTorture = Repeat("ABC", 1<<10+1): 検索パターンも非常に長く、benchInputTortureの大部分と一致しますが、最後の部分で不一致となるように設計されています。 このような入力は、ナイーブなアルゴリズムでは最悪ケースとなり、非常に多くの比較が必要になります。Rabin-Karpは、ハッシュ比較によってこれらの無駄な比較を回避できるため、劇的な性能向上が期待できます。

これらのテストコードは、Rabin-Karpアルゴリズムが導入されたCountおよびIndex関数が、以前のナイーブな実装と比較して、特定の困難な入力に対してどれだけ効率的になったかを定量的に示すために不可欠です。

関連リンク

• Go言語のstringsパッケージのドキュメント: https://pkg.go.dev/strings
• Go言語のIssue #4600: https://github.com/golang/go/issues/4600 (このコミットが修正した問題)
• Go言語のCode Review: https://golang.org/cl/7314095 (このコミットのコードレビューページ)

参考にした情報源リンク

• Rabin-Karp Algorithm - Wikipedia: https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm
• Rolling hash - Wikipedia: https://en.wikipedia.org/wiki/Rolling_hash
• 多項式ハッシュ - Wikipedia: https://ja.wikipedia.org/wiki/%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5
• 文字列検索アルゴリズム - Wikipedia: https://ja.wikipedia.org/wiki/%E6%96%87%E5%AD%97%E5%88%97%E6%A4%9C%E7%B4%A2%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
• Exponentiation by squaring - Wikipedia: https://en.wikipedia.org/wiki/Exponentiation_by_squaring