Goで正規表現を扱うとき、先にCompileしておいて、それを対象にMatchしたりFindしたりが一般的だと思う。
package main
import (
"fmt"
"regexp"
)
func main() {
// Compile the expression once, usually at init time.
// Use raw strings to avoid having to quote the backslashes.
var validID = regexp.MustCompile(`^[a-z]+\[[0-9]+\]$`)
fmt.Println(validID.MatchString("adam[23]"))
fmt.Println(validID.MatchString("eve[7]"))
fmt.Println(validID.MatchString("Job[48]"))
fmt.Println(validID.MatchString("snakey"))
}
で、このとき何らかの最適化がされているんだろうな〜とふと思って、内部で何をやっているか追ってみたら、regexp/syntaxのSimplify()というのを呼び出してた。
このあたり。 https://github.com/golang/go/blob/go1.24.4/src/regexp/regexp.go#L175
ドキュメントによると、簡略化してくれる、とだけある。
https://pkg.go.dev/regexp/syntax#Regexp.Simplify
Simplify returns a regexp equivalent to re but without counted repetitions and with various other simplifications, such as rewriting /(?:a+)+/ to /a+/. The resulting regexp will execute correctly but its string representation will not produce the same parse tree, because capturing parentheses may have been duplicated or removed. For example, the simplified form for /(x){1,2}/ is /(x)(x)?/ but both parentheses capture as $1. The returned regexp may share structure with or be the original.
で、syntax.Regexp には String() があって、その正規表現を返してくれる。つまりこういうことができる。
s, _ := syntax.Parse(`/(x){1,2}/`, syntax.Perl)
s.Simplify().String() // => /(x)(x)?/
ところで、Regexp::Assemble というのがあって。
404 Blog Not Found : perl - Regexp::Assembleのススメ
要は、qr/(?:ab+c|ab+-|a\w\d+|a\d+)/と書くよりも、qr/(?:\w?\d+|b+[-c])/と書いた方が高速な正規表現になるので、それを自動化しようというものです。
これブログ本文がタイポしてて a(?:\w?\d+|b+[-c]) が正しいと思う（すぐ上の出力にそうでてる）
というので、Goで試すと結果が違う。
s, _ := syntax.Parse(`/(?:ab+c|ab+-|a\w\d+|a\d+)/`, syntax.Perl)
s.Simplify().String() // => /a(?:b+c|b+-|[0-9A-Z_a-z][0-9]+|[0-9]+)/
s, _ = syntax.Parse(`/a(?:\w?\d+|b+[-c])/`, syntax.Perl)
s.Simplify().String() // => a(?:[0-9A-Z_a-z]?[0-9]+|b+[\-c])
簡単にベンチマークをしてみる。あえてJavascriptでやってみるとこうなる。
const NUM_LOOPS = 5 * 1000 * 1000;
function bench(name, s) {
const start = performance.now();
const test = () => {
return (
"abc".match(s) !== null &&
"abbbbc".match(s) !== null &&
"abbbbc".match(s) !== null &&
"abbb-".match(s) !== null &&
"a0123456789".match(s) !== null &&
"a0A1a2abet34531DSxxaAGSAaxcRh56asd7ay81asfhuaaSD999876543".match(s) !== null &&
"a1234543456789098765432456788765".match(s) !== null
);
};
for (let i = 0; i < NUM_LOOPS; i++) {
if (!test()) {
console.log(`${name}: fail`);
return;
}
}
console.log(`${name}: success. ${performance.now() - start}`);
}
bench("Original", /(?:ab+c|ab+-|a\w\d+|a\d+)/);
bench("Regexp::Assemble", /a(?:\w?\d+|b+[-c])/);
bench("Simplify(Original)", /a(?:b+c|b+-|[0-9A-Z_a-z][0-9]+|[0-9]+)/);
bench("Simplify(Regexp::Assemble)", /a(?:[0-9A-Z_a-z]?[0-9]+|b+[\-c])/);
"Original: success. 919.8000001907349"
"Regexp::Assemble: success. 931.8000001907349"
"Simplify(Original): success. 951.4000000953674"
"Simplify(Regexp::Assemble): success. 934.5999999046326"
Goだと例えば毎回コンパイルするとこう。
func BenchmarkRegexp1(b *testing.B) {
test := func(s string) bool {
return regexp.MustCompile(s).MatchString("abc") &&
regexp.MustCompile(s).MatchString("abbbbc") &&
regexp.MustCompile(s).MatchString("abbbbc") &&
regexp.MustCompile(s).MatchString("abbb-") &&
regexp.MustCompile(s).MatchString("a0123456789") &&
regexp.MustCompile(s).MatchString("a0A1a2abet34531DSxxaAGSAaxcRh56asd7ay81asfhuaaSD999876543") &&
regexp.MustCompile(s).MatchString("a1234543456789098765432456788765")
}
b.Run("Original", func(b *testing.B) {
for range b.N {
if !test(`(?:ab+c|ab+-|a\w\d+|a\d+)`) {
b.Fail()
}
}
})
b.Run("Regexp::Assemble", func(b *testing.B) {
for range b.N {
if !test(`a(?:\w?\d+|b+[-c])`) {
b.Fail()
}
}
})
b.Run("Simplify(Original)", func(b *testing.B) {
for range b.N {
if !test(`a(?:b+c|b+-|[0-9A-Z_a-z][0-9]+|[0-9]+)`) {
b.Fail()
}
}
})
b.Run("Simplify(Regexp::Assemble)", func(b *testing.B) {
for range b.N {
if !test(`a(?:[0-9A-Z_a-z]?[0-9]+|b+[\-c])`) {
b.Fail()
}
}
})
}
BenchmarkRegexp1
BenchmarkRegexp1/Original
BenchmarkRegexp1/Original-10 55278 22182 ns/op
BenchmarkRegexp1/Regexp::Assemble
BenchmarkRegexp1/Regexp::Assemble-10 82652 14493 ns/op
BenchmarkRegexp1/Simplify(Original)
BenchmarkRegexp1/Simplify(Original)-10 65221 19316 ns/op
BenchmarkRegexp1/Simplify(Regexp::Assemble)
BenchmarkRegexp1/Simplify(Regexp::Assemble)-10 82207 14639 ns/op
PASS
Compileはやっぱり先にやってほしいよね。と先にやってからMatchStringするようにもしてみる。
func BenchmarkRegexp2(b *testing.B) {
test := func(r *regexp.Regexp) bool {
return r.MatchString("abc") &&
r.MatchString("abbbbc") &&
r.MatchString("abbbbc") &&
r.MatchString("abbb-") &&
r.MatchString("a0123456789") &&
r.MatchString("a0A1a2abet34531DSxxaAGSAaxcRh56asd7ay81asfhuaaSD999876543") &&
r.MatchString("a1234543456789098765432456788765")
}
b.Run("Original", func(b *testing.B) {
r := regexp.MustCompile(`(?:ab+c|ab+-|a\w\d+|a\d+)`)
for range b.N {
if !test(r) {
b.Fail()
}
}
})
b.Run("Regexp::Assemble", func(b *testing.B) {
r := regexp.MustCompile(`a(?:\w?\d+|b+[-c])`)
for range b.N {
if !test(r) {
b.Fail()
}
}
})
b.Run("Simplify(Original)", func(b *testing.B) {
r := regexp.MustCompile(`a(?:b+c|b+-|[0-9A-Z_a-z][0-9]+|[0-9]+)`)
for range b.N {
if !test(r) {
b.Fail()
}
}
})
b.Run("Simplify(Regexp::Assemble)", func(b *testing.B) {
r := regexp.MustCompile(`a(?:[0-9A-Z_a-z]?[0-9]+|b+[\-c])`)
for range b.N {
if !test(r) {
b.Fail()
}
}
})
}
BenchmarkRegexp2
BenchmarkRegexp2/Original
BenchmarkRegexp2/Original-10 1226598 893.7 ns/op
BenchmarkRegexp2/Regexp::Assemble
BenchmarkRegexp2/Regexp::Assemble-10 1288764 921.0 ns/op
BenchmarkRegexp2/Simplify(Original)
BenchmarkRegexp2/Simplify(Original)-10 1346878 911.8 ns/op
BenchmarkRegexp2/Simplify(Regexp::Assemble)
BenchmarkRegexp2/Simplify(Regexp::Assemble)-10 1305112 918.2 ns/op
PASS
うーん….
じゃあどんな書き方をするのが一番いいだろうか？？という気持ちになるが、それはある程度最適化する手段はあるものの、究極的には正規表現を処理するエンジンの実装によるだろうな〜と思った。
少なくとも、Goのコードの中では、Compileしたら自動的にSimplify()してくれるので、わざわざSimplify()したパターンを事前に準備する必要はないだろうし、Regexp::Assemble的なこともいらないと思う。素直で愚直な正規表現を書いて、Simplify()してもらうのがGo的には一番パフォーマンスがでるんじゃないだろうか。