Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Go言語の標準ライブラリ strings パッケージにおける Replacer の汎用実装を大幅に高速化し、同時に空文字列のマッチングに関するセマンティクスの問題を修正するものです。特に、文字列置換処理においてトライ（Trie）データ構造を導入することで、パフォーマンスが劇的に改善されています。

コミット

commit 0aad3cdc59c245eb5a09159f43c0bf590893d9ab
Author: Eric Eisner <eric.d.eisner@gmail.com>
Date:   Mon Sep 17 11:50:15 2012 +1000

    strings: implement a faster generic Replacer

    This also fixes the semantics of some corner cases with the empty
    match. TODOs for genericReplacer in the tests are fixed.

    benchmark                  old ns/op    new ns/op    delta
    BenchmarkGenericNoMatch        71395         3132  -95.61%
    BenchmarkGenericMatch1         75610        20280  -73.18%
    BenchmarkGenericMatch2        837995        86725  -89.65%

    R=nigeltao, rsc
    CC=golang-dev
    https://golang.org/cl/6492076

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

https://github.com/golang/go/commit/0aad3cdc59c245eb5a09159f43c0bf590893d9ab

元コミット内容

strings: implement a faster generic Replacer

This also fixes the semantics of some corner cases with the empty
match. TODOs for genericReplacer in the tests are fixed.

benchmark                  old ns/op    new ns/op    delta
BenchmarkGenericNoMatch        71395         3132  -95.61%
BenchmarkGenericMatch1         75610        20280  -73.18%
BenchmarkGenericMatch2        837995        86725  -89.65%

変更の背景

このコミットの主な背景は、Go言語の strings パッケージが提供する Replacer 型の汎用実装 genericReplacer のパフォーマンス改善と、空文字列 ("") の置換に関するセマンティクスの修正です。

strings.Replacer は、複数の文字列置換ルールを効率的に適用するための構造体です。これまでの genericReplacer は、置換対象の文字列 (old) と置換後の文字列 (new) のペアを単純なスライス ([]pair) として保持し、入力文字列を線形に走査しながら各ペアに対して HasPrefix を用いてマッチングを試みるという、比較的ナイーブなアルゴリズムを採用していました。このアプローチは、置換ルールの数が増えるにつれてパフォーマンスが劣化するという問題がありました。特に、多数の置換ルールがある場合や、入力文字列が長い場合に顕著でした。

コミットメッセージに示されているベンチマーク結果は、このパフォーマンス問題の深刻さを示しています。

  • BenchmarkGenericNoMatch: 置換対象が見つからないケースで95%以上の改善。
  • BenchmarkGenericMatch1: 1つの置換対象が見つかるケースで73%以上の改善。
  • BenchmarkGenericMatch2: 複数の置換対象が見つかるケースで89%以上の改善。

これらの数値は、以前の実装がいかに非効率であったか、そして新しい実装がいかに劇的な改善をもたらしたかを物語っています。

また、空文字列のマッチングに関するセマンティクスの問題も修正されています。空文字列は、入力文字列の任意の位置（文字間、文字列の先頭、末尾）でマッチする可能性があるため、その挙動は慎重に定義される必要があります。以前の実装では、空文字列の連続マッチングや、他の置換ルールとの優先順位付けにおいて、意図しない挙動を示すコーナーケースが存在したと考えられます。このコミットは、これらのセマンティクスを修正し、より予測可能で正しい挙動を保証することを目指しています。

前提知識の解説

strings.Replacer

Go言語の strings パッケージには、Replacer という型が定義されています。これは、複数の文字列置換操作を効率的に実行するためのものです。NewReplacer 関数を使って作成され、Replace メソッドや WriteString メソッドを通じて文字列置換を行います。

例えば、NewReplacer("a", "A", "b", "B") のように初期化すると、入力文字列中の "a" を "A" に、"b" を "B" に置換する Replacer オブジェクトが作成されます。このオブジェクトは、内部的に最適な置換アルゴリズムを選択します。置換ルールの特性（例えば、全ての old 文字列が1バイトであるか、共通のプレフィックスを持つかなど）に応じて、より高速な専用アルゴリズム（例: byteReplacer, stringReplacer）が選択されることもありますが、それらが適用できない場合にフォールバックとして genericReplacer が使用されます。このコミットは、その genericReplacer の改善に焦点を当てています。

トライ（Trie / Prefix Tree）

トライ（Trie）は、キーが文字列である連想配列（マップ）のようなデータ構造です。プレフィックスツリー（Prefix Tree）とも呼ばれます。文字列の集合を効率的に格納し、プレフィックス検索や文字列のマッチングを高速に行うために使用されます。

トライの各ノードは、文字列の1文字（またはバイト）に対応します。ルートノードから始まり、各ノードの子ノードへのエッジが次の文字を表します。あるノードまでのパスが有効なキーを表す場合、そのノードは「終端ノード」としてマークされます。

トライの主な特徴:

  • 高速な検索: 文字列の長さに比例する時間で検索が可能です。ハッシュテーブルのように衝突の心配がありません。
  • プレフィックス検索: 特定のプレフィックスを持つ全てのキーを効率的に見つけることができます。
  • 空間効率: 共通のプレフィックスを持つ文字列は、トライ内でパスを共有するため、空間効率が良い場合があります。

このコミットでは、strings.Replacer の置換ルール（old 文字列）をトライ構造で管理することで、入力文字列に対するマッチング処理を高速化しています。

空文字列のマッチングセマンティクス

文字列置換において、空文字列 ("") を置換対象として指定する場合、その挙動は特殊です。空文字列は、任意の2つの文字の間、文字列の先頭、および文字列の末尾でマッチすると解釈されます。

例えば、"foo" に対して NewReplacer("", "X") を適用すると、期待される結果は XfXoXoX となります。これは、f の前、f と o の間、o と o の間、o の後（文字列の末尾）に空文字列がマッチするためです。

しかし、空文字列が連続してマッチすると無限ループに陥る可能性があるため、通常は「一度空文字列がマッチしたら、次のマッチは入力文字列を少なくとも1文字進めた後でなければならない」というルールが適用されます。このコミットでは、このような空文字列のマッチングに関するコーナーケースのセマンティクスが修正され、より堅牢な挙動が保証されています。

技術的詳細

このコミットの核となる技術的変更は、genericReplacer が内部で文字列置換ルールを管理するために、従来の単純な []pair スライスからトライ（Trie）データ構造に移行したことです。

新しい genericReplacer は、trieNode という構造体で構成されるトライをルートノード (root trieNode) として持ちます。

trieNode 構造体

type trieNode struct {
	// value is the value of the trie node's key/value pair. It is empty if
	// this node is not a complete key.
	value string
	// priority is the priority (higher is more important) of the trie node's
	// key/value pair; keys are not necessarily matched shortest- or longest-
	// first. Priority is positive if this node is a complete key, and zero
	// otherwise. In the example above, positive/zero priorities are marked
	// with a trailing "+" or "-".
	priority int

	// A trie node may have zero, one or more child nodes:
	//  * if the remaining fields are zero, there are no children.
	//  * if prefix and next are non-zero, there is one child in next.
	//  * if table is non-zero, it defines all the children.
	//
	// Prefixes are preferred over tables when there is one child, but the
	// root node always uses a table for lookup efficiency.

	// prefix is the difference in keys between this trie node and the next.
	// In the example above, node n4 has prefix "cbc" and n4's next node is n5.
	// Node n5 has no children and so has zero prefix, next and table fields.
	prefix string
	next   *trieNode

	// table is a lookup table indexed by the next byte in the key, after
	// remapping that byte through genericReplacer.mapping to create a dense
	// index. In the example above, the keys only use 'a', 'b', 'c', 'x' and
	// 'y', which remap to 0, 1, 2, 3 and 4. All other bytes remap to 5, and
	// genericReplacer.tableSize will be 5. Node n0's table will be
	// []*trieNode{ 0:n1, 1:n4, 3:n6 }, where the 0, 1 and 3 are the remapped
	// 'a', 'b' and 'x'.
	table []*trieNode
}
  • value: このノードが完全なキー（置換対象の文字列）の終端である場合に、そのキーに対応する置換後の文字列を保持します。
  • priority: キーの優先順位を示します。Replacer は、複数のマッチ候補がある場合に、より高い優先順位を持つものを選択します。このコミットでは、NewReplacer に渡された oldnew スライスにおける出現順序の逆順（つまり、スライスの最後の方にあるルールほど優先度が高い）で優先順位が設定されています。
  • prefix: このノードから次のノードへのパスが、単一の文字ではなく、より長い共通のプレフィックス文字列で構成される場合にそのプレフィックスを保持します。これにより、ノード数を削減し、トライを圧縮することができます（パトリシアトライのような最適化）。
  • next: prefix が設定されている場合に、そのプレフィックスの終端に続く次のノードへのポインタです。
  • table: 次の文字（バイト）に基づいて子ノードをルックアップするためのテーブルです。これは、多数の子ノードを持つ場合に効率的です。genericReplacer.mapping を使って、バイト値を密なインデックスにマッピングすることで、テーブルのサイズを最適化しています。

makeGenericReplacer 関数

この関数は、NewReplacer から呼ばれ、oldnew スライス（置換ルール）を受け取って genericReplacer オブジェクトを構築します。

  1. バイトマッピングの構築: まず、全ての置換対象キー (old 文字列) に含まれるユニークなバイトを特定し、それらを0から始まる密なインデックスにマッピングする r.mapping 配列と r.tableSize を構築します。これにより、trieNode.table のサイズを最小限に抑え、効率的なルックアップを可能にします。
  2. トライの構築: 各置換ルール (oldnew[i], oldnew[i+1]) を、r.root.add メソッドを使ってトライに追加していきます。優先順位は len(oldnew)-i で計算され、oldnew スライスの後方にあるルールほど高い優先順位が与えられます。

trieNode.add メソッド

このメソッドは、新しいキーと値のペアをトライに追加します。

  • キーが空文字列の場合、現在のノードが終端ノードとしてマークされ、値と優先順位が設定されます。
  • 現在のノードに prefix がある場合、新しいキーと既存の prefix の共通部分を考慮して、ノードを分割したり、既存の next ノードに再帰的に追加したりします。
  • 現在のノードに table がある場合、新しいキーの最初のバイトに基づいて適切な子ノードを見つけ、そこに再帰的に追加します。
  • 現在のノードに子がない場合、新しいキーを prefix として設定し、新しい next ノードを作成して残りのキーを追加します。

この add メソッドは、トライの構築ロジックの中核であり、キーの挿入時にノードの分割やマージを適切に行うことで、トライ構造を効率的に維持します。

genericReplacer.lookup メソッド

このメソッドは、入力文字列の特定の位置から始まる最長かつ最高優先順位のマッチをトライ内で検索します。

  • 入力文字列を1バイトずつ消費しながら、トライのノードを辿ります。
  • 各ノードで、そのノードが完全なキーの終端である場合、現在のマッチがこれまでの最良のマッチ（最高優先順位）であるかをチェックし、必要であれば更新します。
  • 子ノードへの遷移は、table（バイトルックアップ）または prefix（プレフィックスマッチ）のいずれかを使用して行われます。
  • ignoreRoot パラメータは、空文字列のマッチングセマンティクスを処理するために使用されます。空文字列は、直前のマッチが空文字列であった場合、同じ位置で再度マッチしないように制御されます。

WriteString メソッドの変更

genericReplacer.WriteString メソッドは、実際の文字列置換処理を実行します。

  • io.Writer インターフェースに WriteString メソッドがある場合（例: bytes.Buffer や strings.Builder）、それを利用して文字列のコピーを避けます。
  • ループ内で lookup メソッドを呼び出し、入力文字列からマッチする部分を特定します。
  • マッチが見つかった場合、マッチする前の部分、置換後の文字列、そしてマッチしたキーの長さを考慮して、出力バッファに書き込みます。
  • prevMatchEmpty フラグを導入し、空文字列のマッチが連続しないように制御することで、空文字列のセマンティクスを正しく実装しています。

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

src/pkg/strings/replace.go

  • trieNode 構造体の新規追加。これはトライの各ノードを表現します。
  • trieNode.add メソッドの新規追加。これはトライにキーと値のペアを追加するロジックを実装します。
  • genericReplacer.lookup メソッドの新規追加。これは入力文字列からトライを使ってマッチを検索するロジックを実装します。
  • genericReplacer 構造体の変更。p []pair フィールドが削除され、root trieNode, tableSize int, mapping [256]byte が追加されました。
  • makeGenericReplacer 関数の大幅な変更。従来の単純なスライス構築から、トライを構築するロジックに置き換えられました。
  • appendSliceWriter 型が []byte のエイリアスに変更され、WriteString メソッドが追加されました。
  • stringWriter 構造体とメソッドが追加され、io.Writer が WriteString メソッドをサポートしない場合にラップするために使用されます。
  • genericReplacer.Replace および genericReplacer.WriteString メソッドの大幅な変更。トライを使った新しい置換アルゴリズムと、空文字列のマッチングセマンティクス修正が実装されました。
  • discard 変数と devNull 型が削除されました。

src/pkg/strings/export_test.go

  • Replacer の内部トライ構造をテストからアクセスできるようにするためのエクスポート関数 PrintTrie が追加されました。これにより、構築されたトライの構造を視覚的に確認し、テストで検証することが可能になります。

src/pkg/strings/replace_test.go

  • 既存の TestReplacer のテストケースが更新され、空文字列の置換に関する期待される挙動が修正されました。特に、TODO コメントが削除され、新しいセマンティクスに合わせたテスト結果が記述されています。
  • TestGenericTrieBuilding という新しいテスト関数が追加されました。これは、PrintTrie を使用して、様々な入力に対して構築されるトライの構造が正しいことを検証します。
  • ベンチマークテスト (BenchmarkGenericNoMatch, BenchmarkGenericMatch1, BenchmarkGenericMatch2) が更新され、新しい genericReplacer のパフォーマンスを測定しています。

コアとなるコードの解説

trieNode とそのメソッド

trieNode は、トライの各ノードを表す中心的なデータ構造です。

  • value と priority は、このノードが置換対象のキーの終端である場合に、そのキーに対応する置換後の文字列と優先順位を保持します。
  • prefix と next は、ノード間の共通プレフィックスを圧縮するために使用されます。例えば、"apple" と "apricot" というキーがある場合、"ap" を prefix として持つノードを作成し、その next ノードから "ple" と "ricot" に分岐させることができます。
  • table は、次の文字に基づいて子ノードを効率的にルックアップするための配列です。genericReplacer.mapping を介してバイト値を密なインデックスに変換することで、テーブルのサイズを最適化しています。

trieNode.add メソッドは、新しいキーをトライに挿入する際の複雑なロジックを処理します。既存のパスとの共通プレフィックスを検出し、必要に応じてノードを分割したり、新しいノードを挿入したりします。このロジックは、トライの効率的な構築と維持に不可欠です。

genericReplacer.lookup

このメソッドは、入力文字列の現在の位置から、トライ内で最も優先順位の高いマッチを効率的に見つけ出します。

  • bestPriority を追跡することで、複数のマッチ候補がある場合に、最も優先順位の高いもの（NewReplacer に渡された順序で後方にあるもの）が選択されることを保証します。
  • ignoreRoot フラグは、空文字列の連続マッチを防ぐための重要なメカニズムです。これにより、"" が一度マッチした場合、次の "" のマッチは入力文字列が少なくとも1文字進んだ後でなければならないというセマンティクスが強制されます。

makeGenericReplacer

この関数は、Replacer の初期化時に一度だけ実行され、置換ルールからトライを構築します。

  • r.mapping と r.tableSize の計算は、トライの table フィールドを効率的に利用するための重要なステップです。これにより、256バイト全ての可能性に対して配列を確保するのではなく、実際にキーに含まれるバイトの種類数に応じた最小限のサイズのテーブルを作成できます。
  • r.root.table = make([]*trieNode, r.tableSize) は、ルートノードが常にルックアップテーブルを使用するように強制することで、最初の文字のマッチングを高速化します。

genericReplacer.WriteString

このメソッドは、実際の文字列置換を実行するメインループを含んでいます。

  • sw, ok := w.(interface { WriteString(string) (int, error) }) の部分は、io.Writer が WriteString メソッドを実装しているかどうかをチェックし、もし実装していればそれを利用することで、string から []byte への変換と、その逆の変換による余分なメモリ割り当てとコピーを避けます。これはパフォーマンス最適化の一般的なパターンです。
  • ループ内で r.lookup を呼び出し、現在の位置からマッチする最長かつ最高優先順位のキーを見つけます。
  • prevMatchEmpty フラグは、空文字列のセマンティクスを正しく処理するために使用されます。これにより、"" が連続してマッチすることを防ぎ、無限ループを回避します。

これらの変更により、genericReplacer は、従来の線形探索に比べて、置換ルールの数や入力文字列の長さに応じてパフォーマンスが大幅に向上しました。トライ構造は、特に多数の置換ルールや共通のプレフィックスを持つルールがある場合に、マッチング処理を劇的に高速化します。

関連リンク

参考にした情報源リンク