アカウント名:
パスワード:
3、4年くらい前に話題になったやつだね。自分も仕事でウッカリやっちまわないかと思うとワラエナイ。パフォーマンスとしての話題正規表現:悪い表現、いい表現、最良の表現 [postd.cc]脆弱性としての話題StackExchangeが攻撃されたReDoSの効果 [ohgaki.net]
正規表現のバックトラックの落とし穴の話自体は随分前に聞いた気がする。先輩からだったかなあ。その時に、くれぐれも注意して使えと釘を刺された覚えが。
「Mastering Regular Expressions」 https://www.amazon.co.jp/dp/B007I8S1X0/ [amazon.co.jp]とりあえずコレが2006年で、バックトラックは便利だけど効率上の落とし穴があるとは書いてる。(詳しくはチャプター6をヨメってさ。)
初版の方は未確認だけど、その頃から知ってる人は知ってた話なのでは。それこそ正規表現エンジンを作ってる側の人は、その性質も込みだから最初から知ってたろうしね
つーか愚直に探索するとありきたりな表現でもくっそ遅い。単純文字列検索ですら、BM法がアルゴリズムの教科書の定番ネタだったりするくらいだし、実用の正規表現エンジンが愚直な実装であることを前提とするのは素人もいいところかと。正規表現は遅いのが当たり前で、そこから各自高速化されているのも当たり前。
そして最終的には「そのエンジンで」高速に処理できないパターンになってるかどうかの問題になる。特定の構造が遅い速いってのは環境依存のあるTipsかと。
コンパイラーが最適化してくれるからってわざわざ非効率なコードを書く必要はないんですよ。むしろやってくれるかどうかもわからない最適化に期待することこそ素人もいいところだと思うんですが
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
※ただしPHPを除く -- あるAdmin
正規表現のバックトラック (スコア:5, 参考になる)
3、4年くらい前に話題になったやつだね。
自分も仕事でウッカリやっちまわないかと思うとワラエナイ。
パフォーマンスとしての話題
正規表現:悪い表現、いい表現、最良の表現 [postd.cc]
脆弱性としての話題
StackExchangeが攻撃されたReDoSの効果 [ohgaki.net]
Re: (スコア:0)
正規表現のバックトラックの落とし穴の話自体は随分前に聞いた気がする。
先輩からだったかなあ。その時に、くれぐれも注意して使えと釘を刺された覚えが。
「Mastering Regular Expressions」 https://www.amazon.co.jp/dp/B007I8S1X0/ [amazon.co.jp]
とりあえずコレが2006年で、バックトラックは便利だけど効率上の落とし穴があるとは書いてる。
(詳しくはチャプター6をヨメってさ。)
初版の方は未確認だけど、その頃から知ってる人は知ってた話なのでは。
それこそ正規表現エンジンを作ってる側の人は、その性質も込みだから最初から知ってたろうしね
Re: (スコア:0)
つーか愚直に探索するとありきたりな表現でもくっそ遅い。
単純文字列検索ですら、BM法がアルゴリズムの教科書の定番ネタだったりするくらいだし、
実用の正規表現エンジンが愚直な実装であることを前提とするのは素人もいいところかと。
正規表現は遅いのが当たり前で、そこから各自高速化されているのも当たり前。
そして最終的には「そのエンジンで」高速に処理できないパターンになってるかどうかの問題になる。
特定の構造が遅い速いってのは環境依存のあるTipsかと。
Re:正規表現のバックトラック (スコア:0)
コンパイラーが最適化してくれるからってわざわざ非効率なコードを書く必要はないんですよ。
むしろやってくれるかどうかもわからない最適化に期待することこそ素人もいいところだと思うんですが