8

スキャンしなければならないテキストの本文があり、各行には少なくとも 2 つ、場合によっては 4 つの情報部分が含まれています。問題は、各行が 15 ~ 20 の異なるアクションのうちの 1 つになる可能性があることです。

ruby では、現在のコードは次のようになります。

text.split("\n").each do |line| #20回くらい…

…………

      式['actions'].each do |pat, reg| #20回くらい

...................

これは明らかに「問題」です。すべての正規表現を 1 つに結合することで (C++ で 50% のマージンで) 高速化することができましたが、それでもまだ必要な速度ではありません。何千ものこれらのファイルを高速に解析する必要があります。

現在、正規表現と照合していますが、これは耐えられないほど遅いです。私はルビーから始めて、速度が向上することを期待して C++ に飛び乗りましたが、それは実現していません。

PEG と文法ベースの解析について何気なく読んだことがありますが、実装するのはやや難しいようです。これは私が向かうべき方向ですか、それとも別のルートがありますか?

基本的に、私はポーカー ハンドの履歴を解析しています。ハンド履歴の各行には、通常、収集する必要がある 2 ~ 3 ビットの情報が含まれています: プレイヤーが誰で、いくらの金額で、アクションに必要なカードは何かなど..

解析が必要なサンプル テキスト:

Buredtens の投稿 $5
ボタンは4番席にあります
*** ホールカード ***
メイヘム 31337 [8s 広告] に対処
Sherwin7 フォールド
OneMiKee フォールド
syhg99 コール $5
Buredtens が $10 にレイズ

この情報を収集した後、各アクションは xml ノードに変換されます。

今のところ、これの Ruby 実装は私の C++ 実装よりもはるかに高速ですが、それは問題です。私は4〜5年以上Cコードを書いていないからです

更新: ここにすべてのコードを投稿したくはありませんが、これまでのところ、私の手/秒は次のようになっています:

588 ハンド/秒 -- boost::spirit in c++
60 ハンド/秒 -- C++ の非常に長くて複雑な 1 つの正規表現 (すべての正規表現をまとめたもの)
33 ハンド/秒 -- Ruby の通常の正規表現スタイル

私は現在、さらに先に進むことができるかどうかを確認するために antlr をテストしていますが、現時点では、spirit の結果に非常に満足しています。

関連する質問:複数の正規表現に対して 1 つの文字列を効率的にクエリする。

4

10 に答える 10

7

私は提案します

幸運を

于 2008-11-20T00:04:48.047 に答える
4

Boost.Spiritは、詳細なパーサー分析を可能にする素晴らしいライブラリです。パーサーが生成されてコードにコンパイルされるため、動的に計算されるソリューションよりもはるかに高速です。構文は主に式テンプレート (多数のオーバーロードされた演算子を表す派手な用語) を使用して行われます。つまり、実際にそれらをコードに直接記述します。

于 2008-11-20T00:05:44.350 に答える
2

Perl を使用している場合の 1 つの方法を次に示します。
からコピーperldoc perlfaq6

while (<>) {
    chomp;
    PARSER: {
        m/ \G( \d+\b    )/gcx   && do { print "number: $1\n";  redo; };
        m/ \G( \w+      )/gcx   && do { print "word:   $1\n";  redo; };
        m/ \G( \s+      )/gcx   && do { print "space:  $1\n";  redo; };
        m/ \G( [^\w\d]+ )/gcx   && do { print "other:  $1\n";  redo; };
    }
}

各行について、PARSERループは最初に一連の数字を照合し、その後に単語境界を照合しようとします。この一致は、最後の一致が中断された場所 (または最初の一致の文字列の先頭) から開始する必要があります。m/ \G( \d+\b )/gcxフラグを使用しているためc、文字列がその正規表現に一致しない場合、perl はリセットされpos()ず、次の一致は同じ位置から開始され、別のパターンが試行されます。

于 2008-11-20T20:11:40.357 に答える
1

PEG と文法ベースの解析について何気なく読んだことがありますが、実装するのはやや難しいようです。これは私が向かうべき方向ですか、それとも別のルートがありますか?

個人的にはPEGが好きになりました。それらに慣れるまでには少し時間がかかるかもしれませんが、保守性が非常に高いため、明らかに勝っていると思います。入力に新しいエッジケースが見つかると、コードの解析が多くの予期しないバグの原因であることがわかります。これが発生した場合、ループと条件の重い正規表現コードと比較して、非終端記号を使用した宣言型文法は更新が簡単です。ネーミングは強力です。

Ruby には、PEG を使用するパーサー ジェネレーターであるTreetopがあります。私は最近、正規表現の重い手書きのパーサーを短い文法に置き換えるのがとても楽しいと感じました。

于 2008-11-30T09:50:50.487 に答える
1

正規表現マッチングはシンプルかつ高速である (ただし、Java、Perl、PHP、Python、Ruby などでは遅い)を参照してください。データの量と正規表現の複雑さによっては、独自の解析ロジックを記述した方が高速な場合があります。

于 2008-11-20T00:12:11.153 に答える
0

このような問題については、目を閉じて Lexer+Parser ジェネレーターを使用します。おそらく手作業による最適化でそれを打ち負かすことができますが、ジェネレーターを使用する方がはるかに簡単です。また、入力が突然変化した場合にも柔軟に対応できます。

于 2008-11-30T10:15:34.960 に答える
0

Perl で簡単なテストを試してください。「勉強」機能についてお読みください。私が試すかもしれないのは:

  • これらのファイルが非常に大きい場合は、ファイル全体または多数の行を単一の文字列に読み取ります
  • 進むにつれて、各行の先頭に行番号を追加します。
  • 文字列を「勉強」します。これにより、文字ごとにルックアップ テーブルが作成され、サイズが大きくなる可能性があります。
  • 改行で区切られた文字列に対して正規表現の一致を実行します (正規表現修飾子 m および s を使用します)。式は、データとともに行番号を抽出する必要があります。
  • 行番号でインデックス付けされた配列項目をその行で見つかったデータに設定するか、さらにスマートなことを行います。
  • 最後に、配列に格納されたデータを処理できます。

試したことはありませんが、面白いかもしれません。

于 2008-11-21T23:19:40.883 に答える
0

これに使用する気の利いたクアッドまたはオクトコアサーバーがある場合の別のアイデア。

作業を分割する処理パイプラインを構築します。ステージ 1 では、ファイルを 1 つのゲームまたはハンドごとに分割し、それぞれをステージ 2 の 8 つのパイプの 1 つに書き込みます。これらのパイプは、データを読み取り、処理して、おそらく別のマシンのデータベースに何らかの方法で出力を生成します。

私の経験では、これらのパイプ ベースのマルチプロセス設計は、マルチスレッド設計とほぼ同じくらい高速で、デバッグがはるかに簡単です。また、パイプの代わりにネットワーク ソケットを使用して、マシンのクラスターをセットアップするのも簡単です。

于 2008-11-21T23:28:01.367 に答える
0

正規表現の一致が重複することはありますか? つまり、2 つ以上の正規表現が同じ行に一致する場合、それらは常に行の異なる部分に一致しますか (重複はありません)?

一致が重複しない場合は、現在ある 15 の正規表現を組み合わせた 1 つの正規表現を使用して検索を実行します。

regex1|regex2|regex3|...|regex15

15 の正規表現のどれが一致したかを判断できるようにする必要がある場合は、キャプチャ グループを使用します。

長い正規表現でデータを 1 回検索すると、15 回検索するよりも高速になります。どれだけ速くなるかは、使用している正規表現エンジンと正規表現の複雑さによって異なります。

于 2008-11-20T07:12:29.883 に答える
0

OK、これで物事がより明確になります (ポーカーハンドの履歴)。あなたは統計ツールを作成していると思います(攻撃要因、ショーダウンに行き、自発的にポットに$を入れるなど)。そのために過度の速度が必要な理由がわかりません。16 台のテーブルでマルチテーブルをしている場合でも、手は適度な速度でしかくすぐらないはずです。

Ruby はわかりませんが、Perl では重要な部分を $1、$2 などに変換すると同時に、少し switch ステートメントを実行します。私の経験では、これは文字列比較を行ってから分割するよりも遅くはありません。他の手段との境界線。

HAND_LINE: for ($Line)
    { /^\*\*\* ([A-Z ]+)/ and do 
        { # parse the string that is captured in $1
          last HAND_LINE; };
      /^Dealt to (.+) \[(.. ..)\]$/ and do
        { # $1 contains the name, $2 contains the cards as string
          last HAND_LINE; };
      /(.+) folds$/ and do
        { # you get the drift
          last HAND_LINE; }; };

本当に速くできるとは思えません。最初の位置で最も多く発生する行 (折り畳みステートメントの可能性が高い) と、最後にまばらにしか発生しない行 (新しいハンドの開始、"*** NEXT PHASE ***") のチェックを配置します。

実際のファイルの読み取りがボトルネックであることがわかった場合は、大きなファイルに対処するために使用できるモジュールを調べることができます。Perlの場合、Tie::File思い浮かびます。

各ハンドを一度だけ読むようにしてください。各ハンドの後にすべてのデータを再度読み取るのではなく、たとえば、既に解析されたハンド ID のハッシュ テーブルを保持します。

于 2008-11-22T00:34:48.690 に答える