1

このような非常に大きなファイルがあります (以下を参照)。私はそれに使用する正規表現の2つの基本的な選択肢があります(他にもあるかもしれませんが、GreedyとNegated Char Classを実際に比較しようとしています)メソッド。

ftp: [^\D]{1,}
ftp: (\d)+
ftp: \d+

注: \d の周りの括弧を外したらどうなるでしょうか?

現在、+ はバックトラッキングを強制する貪欲ですが、Negated Char クラスでは文字ごとの比較が必要です。どちらがより効率的ですか? ファイルが非常に大きいと仮定すると、ファイルの長さのためにプロセッサ使用率のわずかな違いが誇張されます。

あなたがそれに答えたので、否定された Char クラスが非常に大きく、たとえば 18 の異なる文字だったらどうしますか? それはあなたの答えを変えるでしょうか?

ありがとう。

ftp: 1117 バイト
ftp: 5696 バイト
ftp: 3207 バイト
ftp: 5696 バイト
ftp: 7200 バイト

4

6 に答える 6

3

[^\D]{1,} と \d+ はまったく同じです。正規表現パーサーは [^\D] と \d を同じ内容の文字クラスにコンパイルします。+ は {1,} の略です。

怠惰な繰り返しが必要な場合は、 ? を追加できます。最後に。

\d+?

文字クラスは通常、ASCII 文字のビットマップにコンパイルされます。Unicode (>=256) の場合、実装に依存します。1 つの方法は、範囲のリストを作成し、それに二分探索を使用することです。

ASCII の場合、ルックアップ時間はサイズ全体で一定です。Unicode の場合、対数または線形です。

于 2008-10-03T19:42:14.090 に答える
2

どちらの表現にも同じ貪欲さがあります。他の人がここで言ったように、キャプチャ グループを除いて、同じ方法で実行されます。

また、この場合、\d* の後に何もないため、貪欲さは実行速度にはあまり影響しません。この場合、式は検索可能なすべての数字を単純に処理し、スペースが検出されると停止します。これらの式でバックトラックが発生することはありません。

より明確にするために、次のような式がある場合、バックトラックが発生する必要があります。

\d*123

この場合、パーサーはすべての数字を飲み込んでから、バックトラックして次の 3 つの数字を照合します。

于 2008-10-03T19:57:05.150 に答える
1

私の最初のテストでは、[^\D{1,} は \d+ よりも少し遅いことがわかりました。184M ファイルでは、前者は 9.6 秒かかり、後者は 8.2 秒かかります。

() をキャプチャしないと、どちらも約 1 秒速くなりますが、両者の違いはほぼ同じです。

また、キャプチャされた値が /dev/null に出力され、3 番目のバージョンがスペースで分割される、より広範なテストも行いました。結果は次のとおりです。

([^\D]{1,}): ~18s
(\d+): ~17s
(split / /)[1]: ~17s

編集:分割バージョンが改善され、時間が(\ d +)と同じかそれ以下になるように短縮されました

これまでで最速のバージョン (改善できる人はいますか?):

while (<>)
{
    if ($foo = (split / /)[1])
    {
        print $foo . "\n";
    }
}
于 2008-10-03T19:44:22.057 に答える
1

(\d)+これは、かっこをキャプチャするオーバーヘッドのために少し時間がかかるため、書かれているようなひっかけ問題です。に変更すると\d+、Perl/システムで同じ時間がかかります。

于 2008-10-03T19:44:25.503 に答える
1

ええ、私は MizardX に同意します... これら 2 つの式は意味的に同等です。グループ化には追加のリソースが必要になる場合があります。それはあなたが尋ねていたものではありません。

于 2008-10-03T19:46:50.023 に答える
0

質問への直接的な答えではありませんが、行の形式は既に知っているので、まったく別のアプローチではないのはなぜですか? たとえば、フィールド間の空白で正規表現を使用するか、正規表現を完全に避けて空白で split() を使用できます。これは、使用している言語に応じて、通常、正規表現よりも高速になります。

于 2008-10-03T19:39:11.007 に答える