- - PR -
e-mailアドレスの正規表現
投稿者 | 投稿内容 | ||||
---|---|---|---|---|---|
|
投稿日時: 2003-03-02 13:01
正規表現は、結局最後は決定性オートマトンに展開されますから、元の正規表現が長いことと、マッチングに実際に時間がかかるかどうかの関連性は、薄いと思います。 もちろん、長ければオートマトンに展開する処理に時間がかかりますから、毎回正規表現をコンパイルするようなロジックでは遅くなりますけど。 気になるようでしたら、常に測定してみた方がいいですよ。結構自分の予想とは、全く異なる結果が出たりして驚くことが多いです。 | ||||
|
投稿日時: 2003-03-02 13:56
Patternクラスでコンパイル(展開)さえ一度してしまえば早いと
言う事ですね?あとはMatchクラスのロジックでは処理時間に大差が 出ないということですね。findやmatchメソッドのロジックが見えな いのですが、10byteと300byteの違い程度であればマッチンクロジッ クの差は確かに1ミリ秒もなさそうなので、やっぱり意識する必要は ないのかな・・とだんだん思えてきました。 でも測定するのが一番ですね。 ちなみにオートマトンというのは何でしょう?勉強不足で・・ | ||||
|
投稿日時: 2003-03-02 16:34
簡単に言うと、状態というのを複数定義して、調べる文字一つ入力するごとに、この状態を適宜移動していって「受理状態」というのになれば正規表現に「マッチした」と判定出来るような形に持っていくのです(これを決定性オートマトンといいます)。これなら、状態別に入力文字コードをインデックスとする配列(入っている値は、次に移動する状態)があれば、高速に判定が可能になるわけです。 って、文章だけだと難しいですね。ちょっと読み応えありますけど、以下の書籍が参考になると思います。正規表現の処理のところだけ、かじってみてはいかがでしょう。私はこの二つの本で理解しました。 サイエンス社:コンパイラ(通称ドラゴンブック) 岩波講座ソフトウェア科学 #5:プログラミング言語処理系 | ||||
|
投稿日時: 2003-03-02 18:04
ありがとうございます。
ですが10回くらい読みなおしても理解できません。。 ベルトコンベアによるFactoryAutomationみたいなイメージで しょうか。車の生産の流れ作業みたいな・・ オートマトン= { ・ベルトコンベア=Matchクラス ・車体=調べる対象文字列1文字 ・Automation機械=Matchクラスのメソッド(matchesなど) } 流れ作業で車体(文字列1文字)を機械(コンパイルされた状態)が 溶接(判定)していく様なイメージ・・? 無理やりな解釈ですね。 | ||||
|
投稿日時: 2003-03-02 23:02
オートマトンというのは「からくり人形」という意味で、オートメーションとは違います。文字が入力されるごとに、内部の状態が動いていく様を指しているのでしょう。
さすがに、このスペースで説明するのは無理なので、紹介した書籍を、頑張って読んでみてください。図書館にも置いてあると思いますよ。 昔は、こういうのってCマガジンなんかで分かりやすく説明していたもんですけど、最近は流行らないようですね。 |