goの正規表現が遅いとネットの記事があったので似ているもので作ろうと思ったのですか、stringとregexpってどっちの方が早いのですか(適当に似ていたので言いました コードでは比べていない)
1 件の回答
おそらくstring
の方が速いです。
簡単な置換処理ではカフカの「変身」の原文で50倍程度速い例が上がっています。
なぜ冒頭でおそらくと申し上げたのかというと、strings
パッケージとregexp
パッケージは彫刻刀と3Dプリンタくらい機能に違いがあるからです。
前者はIndex関数やReplace関数などで簡単な文字列操作を提供しています。
後者は「遅い」と言われる(?)正規表現を提供しています。
なので前者を利用した場合は正規表現に必要な機能を再発明しなくてはいけません。
自作の正規表現機能は製作者の腕次第で早くも遅くもなります。
極端な例ですが、regexpとまったく同じアルゴリズムで正規表現を実装したならば、速度は「遅い」ものになるでしょう。
では、regexp
パッケージは使い物にならない正規表現なのかと問われるとそんなことはありません。
PerlやPythonなどの正規表現パッケージとは異なるThompson NFA
というアルゴリズムを採用しているため、文字数が少ない時には不利ですが、文字数が多くても指数関数的な速度低下を防ぐことができます。
おおよそ前者はO(2^n)オーダーで後者はO(n^2)オーダーという記事には特徴的なグラフが載っていて、興味深い内容となっています。
その他の注意点として、正規表現をコンパイルしていないとものすごく遅くなりますので、単純にregexp
パッケージを悪者にするのではなく、適切な実装で用いることも重要です。
参考記事: regexpとの付き合い方