5

改善策を考えていました。現在、ログ ファイルのテキスト処理を多数行っています。

PCREが遅い/速い、または他の実装であると言っているわけではありません。

私が書いている言語は主に Perl です。強力な正規表現エンジンがあり、PCRE よりも表現力が高いことはわかっています。

正規表現を生の nasm にコンパイルする C++ で小さな正規表現エンジンを作成することについて、私はこの考えを持っています。

私は、PCRE が非常に複雑であることを認識しており、不要な処理に関して PCRE によって行われる多くのことをスキップできると想定しています。Perl は vm のようなオペコードと、オーバーヘッドと見なされる可能性のあるあらゆる種類のもので動作するため、Perl よりも確実に高速にすることができます。

少し前にすでに実装を開始しました。問題がないので、ここに投稿するつもりはありません。最後まで実行して、キャプチャを実行でき+ * ^ $、文字クラスを解釈できる正規表現エンジンを取得できました（ただし、正規表現をアセンブリ言語に変換する部分を実行しました)

これは良い考えでしょうか、それとも悪い考えでしょうか? これで良いパフォーマンスを達成するという点で、何が問題になる可能性がありますか?

tl;dr => ネイティブ アセンブリを生成する C++ ミニ正規表現エンジンは、確立された正規表現の実装よりも高速でしょうか?

4

4 に答える 4

6

これに対する答えはかなり明白だと思います。理想的には、そうかもしれません。しかし、あなたがこの種のことに非常に優れていたとしても、ほとんどの場合、利用可能なライブラリよりもわずかに優れているだけであり、すべてのライブラリを動作させるにはさらに時間がかかるという点に到達するには、非常に大きな開発努力が必要です。バグアウト。ですからあまり意味はありません。

于 2013-03-25T05:00:46.713 に答える
6

Perl の正規表現は高速ですが、非常に高速というわけではありません。Russ Cox による Perl と Thompson スタイルの正規表現エンジンの分析を参照してください。パフォーマンスの違いに関する目を見張るようなデモンストレーションと、それを正しく行う方法に関する理論が示されています。

Thompson/Cox のスキームを実装したくない場合は、非常に高速な正規表現プロセッサであるRagelを検討する必要があります。Ragel は、効率的なオートマトンを構築するという大変な作業を行ってから、ターゲット コンパイラ言語用のコードを生成します。これにより、コンパイラは「マシンコードに」変換するという大変な作業を行うことができます。

これは、構築を検討しているエンジンである可能性があります。

これらが十分でない場合は、非常に高速なストリーム マッチャーに関する IBM の最近の作業を追跡する必要があります。Davide Pasettoの論文はおそらく関連があると思います。

于 2013-03-25T05:10:01.083 に答える
3

ベンチマークを行うだけです。非常に単純ですが、一般的に使用する正規表現を使用します。次に、その正規表現のハードコーディングされたバージョンを作成します。現実的な量のデータを使用して比較すると、高速化が問題になるほど操作に時間がかかります。

優れた正規表現エンジンの内部ループは、最先端のテキスト マッチング アルゴリズムの両方を使用してすでにかなり最適化されており、それらを高速に実行するように最適化されていると思います。式が些細なものではない場合 (たとえば、char クラス)、独自のコードで高速化することをお勧めします。

明らかにオーバーヘッドがあります。他のすべてが等しい場合、ハードコーディングして独自の方法で実行し、線形の高速化を実現できます。しかし、それは優れたアルゴリズムを持つことの二次的なものです。アルゴリズムの複雑さの概念に慣れていない場合は、まずそれを読んでください。

しかし、1 つ重要なことがあります。正規表現エンジンが正しい必要があります。偽陽性ゼロで、想定されているものを見つけなければなりません。誤った一致を取得したり、一致を逃したりすると、データの破損などの悪いことが起こる可能性があります。エンジンをあえて使用するのに十分な信頼を得るにはどうすればよいでしょうか?

楽しみのために作成してください。実際の本番環境で使用するには...うーん...

深刻な可能性がある場合は、最初から自動テストが必要です。正規表現のようなものでは、テストのコード カバレッジ分析も必要です。確定的な入力と出力があり、ユーザー入力も何もないため、最終的には、エンジンとテスト正規表現の生成コードの両方で、コードの関連部分を 100% カバーすることを目指す必要があります。ああ、目標が速度であるときは、自動ベンチマークも忘れないでください! もちろん、コーディングを取得したいので、最初はこのようなことは気にしません。それで問題ありませんが、最初からインフラストラクチャをセットアップし、コードをテストするときは自動テストとして記述し、アドホック テストを手動で行う衝動に抵抗します。 (自動化されたテスト ケースを作成する手順を除く)。正しいことを行えば、プロジェクトが成功する可能性ははるかに高くなります。

生成されたコードの場合、特定の CPU のアセンブラーではなく、おそらくLLVMを使用することをお勧めします。

于 2013-03-25T05:26:41.013 に答える
2

おそらく、マシン命令にコンパイルされた正規表現から大幅にパフォーマンスを絞り出すことができます。そうすることが理にかなっているかどうかは、コストをどのように償却するかに完全に依存します。

ログ ファイルを解析するという特定の目標を達成しようとしていて、期限がある場合は、既存のライブラリ ( Google の RE2を含む) が遅すぎることが証明されるまで、これを検討することさえ意味がないかもしれません。RE パフォーマンスがボトルネックであると判断する前に心配することは、時期尚早の最適化の典型的なケースです。

ただし、これを挑戦と学習の演習として行いたい場合、および締め切りが迫っていない場合は、ぜひ試してみてください. 多くの作業に備えて、バグが発生する可能性があるため、多くのテスト ケースを作成することを忘れないでください。正規表現エンジンは、作業成果物全体の重要な基盤となり、本番環境で誤動作することは許されません。

幸運を！

于 2013-03-25T05:19:22.517 に答える