正規表現がどれぐらい遅くなるか(計算量？)を調べてみた - 唯物是真 @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}]" この挙動は、最後のパターンを使って、孤立した下位サロゲートを検出するプログラムを書いている時に発見しました。孤立した
遅いッ！遅すぎるッ！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
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Methods of the Matcher Class (The Java™ Tutorials > Essential Java Classes > Regular Expressions)
