次のように、1行に20文字を含むテキストファイルがあるとします。
wertzuiopasdfghjkl<
asdfghjkl<yxcvbnm,.-
<yxcvbnm,.-123456789
1234567890QWERTZUIOP
QWERTZUIOPASDFGHJKL<
など...
行に同じ文字が複数あることを望みますgrep
。
grep '\(.\).*\1' n20x1M
逆参照を含む。マイコンピュータでは、一致がない100万行を処理するのに15.7秒かかります。
行数を2倍にすると、使用されたCPU時間も予想どおり2倍の31.4に増えます。
また、20個ではなく28個の列があると、時間が2倍になると予想されます(20文字はテスト可能な190個の組み合わせを提供し、28文字は378個の可能な組み合わせを提供します)。しかし、私のコンピュータでは28.2秒しかありません。
それでは、逆参照速度低下が純粋に組合せ水路だけテストされるのではないでしょうか?私はこれを試しました:
grep '^\(.\).*\1' n20x1M
これにより、組み合わせの数が190個からわずか19個に大幅に減少します。最初の文字を読み、残りの文字と一致することを確認してください。 1.6秒しかかかりませんが、実際には2.8秒かかります!
行をメモリに読み込んでキャッシュするのにいくつかのオーバーヘッドがありますか?いいえ、もし私がそうするなら
grep '.*_' n20x1M
処理時間はわずか0.004秒!デフォルトでは、同じ操作(20文字の行から文字を検索)を実行しますが、単に固定文字を指定せずに残りの19文字のうち、その行の最初の文字を検索すると、引数以上の結果が得られます。 1000です!
私の理解に問題がありますか?
逆参照によって隠されたオーバーヘッドが多すぎますか?
それとも、GNU正規表現で逆参照が正しく実装されていませんか?
ここで何が起こっているのかを説明できる人はいますか?
パフォーマンスを向上させるにはどうすればよいですか?
修正する @Sundeepは、遅い逆参照に関する免責事項について言及しました。しかし、これは可能な解決策が多すぎて計算されたものです。私はこれを期待しましたが、複雑さを追加しなくても、それを使用すると追加のペナルティがあります。
これは実装の問題のようです。オプションを使用した他のヒントと同様に、-P
スピードアップが15.4秒から2.0秒に増加しました!
アンカーのある単純なケースの^
速度は2.8秒から0.25秒に向上しますが、まだ固定文字検索の要件(0.004秒)を満たしていません。興味深いことに、optionを使用すると、-P
固定文字の大文字と小文字が0.13秒に遅くなるため、逆参照ペナルティは小さくなりますが、全体的なペナルティに近いです。
残念ながら、私は主にMacOSや逆参照を使用するバージョンを使用-P
しません。grep
sed