8

で作業していて、で定義されているさまざまstd::regexな定数について読んでいるときに、それについて読んでいると、アプリケーションで役立つように思えます（最初に初期化された正規表現のインスタンスが1つだけ必要ですが、ロードプロセス全体で複数回使用されます）。std::regex_constantsstd::optimize

ワーキングペーパーn3126（pg。1077）によると、 std::regex_constants::optimize：

正規表現エンジンが、正規表現が一致する速度に注意を払い、正規表現オブジェクトが作成される速度には注意を払わないように指定します。それ以外の場合は、プログラム出力に検出可能な影響はありません。

どのタイプの最適化が実行されるかについて興味がありましたが、それに関する文献はあまりないようです（実際、未定義のようです）。私が見つけた唯一のものの1つは、cppreference.comにありました。述べたstd::regex_constants::optimize：

正規表現エンジンに、構築を遅くする潜在的なコストを使用して、マッチングを高速化するように指示します。たとえば、これは非決定論的FSAを決定論的FSAに変換することを意味する場合があります。

ただし、私はコンピュータサイエンスの正式なバックグラウンドを持っていません。また、FSAとは何かの基本を理解し、決定論的FSA（各州には次の州が1つしかない）と非決定論的FSA（複数の潜在的な次の状態を伴う）; これによりマッチング時間がどのように改善されるのかわかりません。また、さまざまなC++標準ライブラリの実装に他の最適化があるかどうかを知りたいと思います。

4

2 に答える 2

3

JeffreyFriedlによるMasteringRegularExpressionsには、正規表現エンジンとパフォーマンスのトレードオフ（スタックオーバーフローの回答に収まるよりもはるかに多い）のトピックに関するいくつかの有用な情報があります。

N3126のソースであるBoost.Regexが、optimize「これは現在Boost.Regexには影響しません」と文書化していることは注目に値します。

PS

確かに、それは実装定義のようです

いいえ、指定されていません。実装定義とは、動作の選択を定義するために実装が必要であることを意味します。optimize実装は、正規表現エンジンがどのように実装されているか、またはフラグがどのような違いをもたらすか（ある場合）を文書化する必要はありません。

PS 2

さまざまなSTL実装で

std::regexはSTLの一部ではなく、C++標準ライブラリはSTLと同じものではありません。

于 2012-07-21T13:53:09.767 に答える
2

NFAベースの正規表現の実装が特定の状況でDFAマッチャーで発生する指数関数的なバックトラックを回避する方法の詳細については、http：//swtch.com/~rsc/regexp/regexp1.htmlを参照してください。

于 2012-07-21T13:54:09.437 に答える