正規表現がどれぐらい遅くなるか(計算量？)を調べてみた - 唯物是真 @Scaled_Wurm
最近あんまりパフォーマンス的によくない正規表現を見かけたので、いくつかのパターンについて正規表現をいろんな言語で試してみて実行時間を測ってみた(ついでに最悪計算量についてゆるふわに考えてみた) 実際には正規表現エンジンの実装(NFAやDFAとか？)やバージョン、オプション(？)によると思いますしなんとなくの傾向という感じです やること 以下の正規表現についてパターンマッチされる対象の文字列の長さ\(L\)が増えたときに、1回マッチするか調べる時間がどれぐらい伸びるかを調べます .*a a.*b a.*b.*c a(a|aa)*b 計測方法 以下の言語についてIdeoneで実行してみて実際に測ってみた時間を載せます(括弧内はIdeoneに書かれていたバージョン) Ruby (ruby-2.1) Python (python 2.7.10) PHP (php 5.6.4) Java (sun-
Javaの正規表現における下位サロゲートの問題ある挙動 - 映画は中劇
Javaの正規表現で下位サロゲートコードにマッチするパターンを書くと、完全なサロゲートペアの後半16ビットにマッチしてしまうことがあります。少なくとも、次のバージョンはそのような挙動を示します。 Oracle Hotspot 1.8.0_72 OpenJDK 1.8.0_66 詳細 次のパターンは、問題を起こす正規表現をJavaの文字列リテラルで表したものです。それぞれ、単一の下位サロゲートU+DC00あるいは下位サロゲート全体の文字クラス (U+DC00-U+DFFF) を表しています。 "\\udc00" "\\x{dc00}" "[\\udc00-\\udfff]" "[\\x{dc00}-\\x{dfff}]" "[\\p{blk=Low Surrogates}]" この挙動は、最後のパターンを使って、孤立した下位サロゲートを検出するプログラムを書いている時に発見しました。孤立した
後方参照によるパターン内での参照
正規表現パターン内で括弧を記述することで、括弧内のパターンにマッチする部分文字列が記憶されます。このパターンにマッチした部分文字列をパターン内で参照し利用することができます。このようにマッチした部分文字列をパターン内で参照することを後方参照と呼びます。ここでは Perl の正規表現で後方参照を使ったパターン内での参照方法を解説します。 後方参照の使い方 正規表現のパターン内で括弧を記述すると、括弧内のパターンにマッチした部分の文字列が記憶されます。記憶された文字列はパターンマッチが完了すると変数 $1 などに格納されプログラムの中で利用することができます。 このパターンにマッチし記憶された文字列をパターン内でも参照することができます。このように記憶された文字列をパターン内で参照することを後方参照と呼んでいます。記憶された文字列は最初に記憶された内容は \1 、次に記憶された内容は \2 の
遅いッ！遅すぎるッ！Java の正規表現のお話。 - Cybozu Inside Out | サイボウズエンジニアのブログ
こんにちは、ミドルウェア開発チームの青木です。 先日、アプリケーションサーバーが応答を返さなくなるトラブルに遭遇しました。 今回はその時のトラブルの原因と対策の顛末についてお話しようと思います。 現象 アプリケーションサーバーが突如応答を返さなくなりました。 現象が発生したアプリケーションサーバーのスタックトレースを見ると、あるスレッドの先頭が上記のようになっていました。 "qtp258153142-514386" prio=10 tid=0x00007f40b8dbf000 nid=0x7b4e runnable [0x00007f415ccb0000] java.lang.Thread.State: RUNNABLE at java.util.regex.Pattern$Loop.match(Pattern.java:4692) at java.util.regex.Pattern$G
正規表現を解析して可視化してくれるサイトが凄すぎる件
ある正規表現に対して、特定の文字列がマッチするかどうかをチェックするツールやサイトは沢山ありますが、正規表現そのものが何を意味しているのか、どんな文字列を期待しているのかを解析・解読・説明してくれるツールやサイトってなかなか見ない気がします。 他人の書いた正規表現を見て、「ん？」ってなったことはありませんか？ 例えばこれ。 1 ^[a-zA-Z0-9-_.]@([a-zA-Z0-9_-]+\.)+[a-zA-Z]{2,4}$ これくらいなら分かりますが、複雑になってくるとつらい… いつかはマスターしたいけど…今は楽したい。 そう思ってググってみると…ありました！ それがこちら。 Regexper http://www.regexper.com/ 正規表現を入力して Display をクリックすると、その正規表現が表す内容を図にして表示してくれます。 例えば先程の正規表現は、当記事の一番上の
正規表現によるバリデーションでは ^ と $ ではなく \A と \z を使おう
正規表現によるバリデーション等で、完全一致を示す目的で ^ と $ を用いる方法が一般的ですが、正しくは \A と \z を用いる必要があります。Rubyの場合 ^ と $ を使って完全一致のバリデーションを行うと脆弱性が入りやすいワナとなります。PerlやPHPの場合は、Ruby程ではありませんが不具合が生じるので \A と \z を使うようにしましょう。 はじめに 大垣さんのブログエントリ「PHPer向け、Ruby/Railsの落とし穴」には、Rubyの落とし穴として、完全一致検索の指定として、正規表現の ^ と $ を指定する例が、Ruby on Rails Security Guideからの引用として紹介されています。以下の正規表現は、XSS対策として、httpスキームあるいはhttpsスキームのURLのみを許可する正規表現のつもりです。 /^https?:\/\/[^\n]+$/
Scalaの正規表現 - xuwei-k's blog
togetter 正規表現が構文として必要かどうかという話から プログラミング言語における正規表現リテラルの必要性について こういう収集がつかなそうな話題にあまり首突っ込むの好きじゃないんですが、blogに書いておけば、まぁそれはそれでScalaをあまり知らない人にとっては役に立つだろうから、丁寧に説明しておきましょう。 togetter(と、その他関連するtweet)はあまり読んでません。 とりあえずkazuhoさんがわかりやすくblogに要点まとめているので、まずそれに対応するかたちで説明しましょう。 また、大前提としてScalaに構文としての正規表現リテラルはありません。なので、以下の説明を読んで 「いや、それは単に苦しい言い訳だし、やはり正規表現リテラルは存在したほうがいいでしょ」 と思う人もいれば 「なるほど、このくらいの機能があれば、たしかにそれほど正規表現リテラル必要ないな」
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Methods of the Matcher Class (The Java™ Tutorials > Essential Java Classes > Regular Expressions)