はじめに 「Goの正規表現は遅い」 そんなふうによく言われていました。(最近はあまり聞かなくなりましたが) たとえば、↓の記事ではPythonの正規表現と比較して1.5倍くらい遅いという結果になっています: この話には「Goの正規表現は最悪時間が短くなるように安定したアルゴリズムを採用しているから」という回答があります: ↑の記事の比較では、GoがPerlに対して約10倍以上高速という結果が出ているので、「Goの正規表現は遅くない!はい、論破ー!」というわけですね。 なんでこうなるのかも↑の記事で説明されているとおりですが、Perl(などのバックトラック型エンジン)が入力長に対して指数関数的に実行時間が伸びていくのに対し、Goの正規表現エンジンは入力長に対して線形時間で実行時間が伸びていくアルゴリズムを採用しているため、入力が長くなると急激にGoのほうが有利になるからです: 一方で、入力が
![Goの正規表現が遅いって言う人がいたから、(速い)正規表現エンジンを作ったよ](https://cdn-ak-scissors.b.st-hatena.com/image/square/4528cee23a5dda414a02d6b2b4efc471ee3c996f/height=288;version=1;width=512/https%3A%2F%2Fres.cloudinary.com%2Fzenn%2Fimage%2Fupload%2Fs--QGUVHic---%2Fc_fit%252Cg_north_west%252Cl_text%3Anotosansjp-medium.otf_55%3AGo%2525E3%252581%2525AE%2525E6%2525AD%2525A3%2525E8%2525A6%25258F%2525E8%2525A1%2525A8%2525E7%25258F%2525BE%2525E3%252581%25258C%2525E9%252581%252585%2525E3%252581%252584%2525E3%252581%2525A3%2525E3%252581%2525A6%2525E8%2525A8%252580%2525E3%252581%252586%2525E4%2525BA%2525BA%2525E3%252581%25258C%2525E3%252581%252584%2525E3%252581%25259F%2525E3%252581%25258B%2525E3%252582%252589%2525E3%252580%252581%2525EF%2525BC%252588%2525E9%252580%25259F%2525E3%252581%252584%2525EF%2525BC%252589%2525E6%2525AD%2525A3%2525E8%2525A6%25258F%2525E8%2525A1%2525A8%2525E7%25258F%2525BE%2525E3%252582%2525A8%2525E3%252583%2525B3%2525E3%252582%2525B8%2525E3%252583%2525B3%2525E3%252582%252592%2525E4%2525BD%25259C%2525E3%252581%2525A3%2525E3%252581%25259F%2525E3%252582%252588%252Cw_1010%252Cx_90%252Cy_100%2Fg_south_west%252Cl_text%3Anotosansjp-medium.otf_37%3Ayanother%252Cx_203%252Cy_121%2Fg_south_west%252Ch_90%252Cl_fetch%3AaHR0cHM6Ly9saDMuZ29vZ2xldXNlcmNvbnRlbnQuY29tL2EtL0FPaDE0R2d2Rmo1UmpVYllxS0Eya29WYkQ4WUNSWEFDUEFFQWZsVlA0eTZvVTJnPXMyNTAtYw%3D%3D%252Cr_max%252Cw_90%252Cx_87%252Cy_95%2Fv1627283836%2Fdefault%2Fog-base-w1200-v2.png)