regcompで^ [az] {0,20000} $ regexコンパイルの恐ろしいパフォーマンス

Question

このような正規表現のコンパイルにはRAMの70％を占めるのはなぜかと思います。 16：

strcpy(regexStr,"^[a-z]{0,20000}$"); 
regcomp(&regex , regexStr , REG_NOSUB | REG_EXTENDED); 

実行時間は分単位です（前にプロセスを終了していなければなりません）。 ^[a-z]{0,2000}$（2,000ではなく2,000）の実行は約100msで、これは私にとって大きな意味を持ちます。

これを使用してパターンをチェックし、同時に長さを確認します。 Ï両方に便利な正規表現を見つけました。私は何か間違っているのですか？

Answer 1

文字列の長さを測定するためにstrlenを使用し、その後にアルファベット以外の文字がないかどうかをテストするために正規表現/[^a-z]/を使用することをお勧めします。キッス。

いいえ、理由はありません。このようなパフォーマンスが得られる理由はありません。

*良い理由が明らかにバグや貧しいデザイン...

編集が含まれていませんが：結局のところ、それは実際にpoor design

EDIT2の場合もある：あなたがやっているチェックがあるので、あなたが実際にプレーンなCで実装することができ非常にシンプル：

int i; 
for (i=0; i<20000 && str[i]!=0; i++) 
    if (str[i] < 'a' || str[i] > 'z') 
    return -1; 
return i; 

それは-1を返した場合、文字列は、範囲外のAZの文字が含まれています。 20000を返した場合、文字列は20000文字より長くなります。それ以外の場合は、文字列の長さを返します。 （注：これはぎこちない文字列でしか動作しません）

Answer 2

コンパイラに何をすべきかを考慮する必要があります。素朴なやり方では、正規表現コンパイルは、正規表現にマッチする文字列だけを受け入れる有限状態マシンの構築であると考えることができます。文字列に含まれる文字の数を把握しなければならないマシンの状態の大きさを考えてみると、現在の正規表現に問題があるはずです。

Answer 3

私の推測では、カーディナリティーの範囲はあなたを殺すものです。 "^[a-z]*$"のような欲張りな非特定のカーディナリティマッチを最大長チェックと組み合わせて試してみてください。はるかに速くなければなりません。

Answer 4

あなたの正規表現エンジンはあなたのパターンを^(|[a-z]|[a-z][a-z]|[a-z][a-z][a-z]|..)$のようなものに変換しています。これはあなたの範囲のカーディナリティで二次的です。