アカウント名:
パスワード:
3、4年くらい前に話題になったやつだね。自分も仕事でウッカリやっちまわないかと思うとワラエナイ。パフォーマンスとしての話題正規表現:悪い表現、いい表現、最良の表現 [postd.cc]脆弱性としての話題StackExchangeが攻撃されたReDoSの効果 [ohgaki.net]
正規表現のバックトラックの落とし穴の話自体は随分前に聞いた気がする。先輩からだったかなあ。その時に、くれぐれも注意して使えと釘を刺された覚えが。
「Mastering Regular Expressions」 https://www.amazon.co.jp/dp/B007I8S1X0/ [amazon.co.jp]とりあえずコレが2006年で、バックトラックは便利だけど効率上の落とし穴があるとは書いてる。(詳しくはチャプター6をヨメってさ。)
初版の方は未確認だけど、その頃から知ってる人は知ってた話なのでは。それこそ正規表現エンジンを作ってる側の人は、その性質も込みだから最初から知ってたろうしね
この正規表現の件とか、TCP/IPやプロセッサ関連の話題なんかで当時ありきたりの話がいま伝承じみた扱いになってるのをみると何というか少しゾクリとすることがある
なあに、7payみたいにあれだけ盛大にやらかしても、責任者は責任取らなくていいんですよ。雲の上の人は気楽なもんです。
現場の危機感については、まるで聞く耳持たないんだもの。
責任を取るためだけにいるやつがその責任すら取らないんだったらマジで存在価値ないな
>とりあえずコレ
レビュー(書評)本文が英文だったのが新鮮だった。amazon.co.jp のレビューは取り扱い商品同様相互に各国amazonから自由にやりとりできてうらやましい。
つーか愚直に探索するとありきたりな表現でもくっそ遅い。単純文字列検索ですら、BM法がアルゴリズムの教科書の定番ネタだったりするくらいだし、実用の正規表現エンジンが愚直な実装であることを前提とするのは素人もいいところかと。正規表現は遅いのが当たり前で、そこから各自高速化されているのも当たり前。
そして最終的には「そのエンジンで」高速に処理できないパターンになってるかどうかの問題になる。特定の構造が遅い速いってのは環境依存のあるTipsかと。
コンパイラーが最適化してくれるからってわざわざ非効率なコードを書く必要はないんですよ。むしろやってくれるかどうかもわからない最適化に期待することこそ素人もいいところだと思うんですが
>単純文字列検索ですら、BM法がアルゴリズムの教科書の定番ネタだったりするくらいだし、単純文字列検索「だから」そういう原始的な高速化技法があるんでしょ。不特定多数の複雑なパターンマッチにおいては、一般的な最適化技法はないと思う。
仮にあっても、その正規表現を数回しか使用しないのであれば、最適化にかかる時間の方が、最適化によって短縮される時間より長くなって本末転倒。正規表現部分を何万回も何十万回も使ってボトルネックになる場合は、一流のプログラマなら正規表現なんて使わない形に書き直す。
なので不特定多数の正規表現の汎用的な最適化なんて不可能だし実装してないんじゃないだろうか。
JavaのHotSpotVMによって高度な動的最適化が日常的に利用可能になったから、そこで行われている最適化がどれほど無茶なことか分からない初心者も増えてしまったのかもしれない。HotSpotVMは、もはや初心者の理解を超えてるもんね。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
UNIXはただ死んだだけでなく、本当にひどい臭いを放ち始めている -- あるソフトウェアエンジニア
正規表現のバックトラック (スコア: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:正規表現のバックトラック (スコア:2, 興味深い)
この正規表現の件とか、TCP/IPやプロセッサ関連の話題なんかで
当時ありきたりの話がいま伝承じみた扱いになってるのをみると
何というか少しゾクリとすることがある
Re: (スコア:0)
なあに、7payみたいにあれだけ盛大にやらかしても、責任者は責任取らなくていいんですよ。
雲の上の人は気楽なもんです。
現場の危機感については、まるで聞く耳持たないんだもの。
Re: (スコア:0)
責任を取るためだけにいるやつがその責任すら取らないんだったらマジで存在価値ないな
オフトピ, -1 (Was: Re:正規表現のバックトラック) (スコア:1)
>とりあえずコレ
レビュー(書評)本文が英文だったのが新鮮だった。
amazon.co.jp のレビューは取り扱い商品同様相互に
各国amazonから自由にやりとりできてうらやましい。
Re: (スコア:0)
つーか愚直に探索するとありきたりな表現でもくっそ遅い。
単純文字列検索ですら、BM法がアルゴリズムの教科書の定番ネタだったりするくらいだし、
実用の正規表現エンジンが愚直な実装であることを前提とするのは素人もいいところかと。
正規表現は遅いのが当たり前で、そこから各自高速化されているのも当たり前。
そして最終的には「そのエンジンで」高速に処理できないパターンになってるかどうかの問題になる。
特定の構造が遅い速いってのは環境依存のあるTipsかと。
Re: (スコア:0)
コンパイラーが最適化してくれるからってわざわざ非効率なコードを書く必要はないんですよ。
むしろやってくれるかどうかもわからない最適化に期待することこそ素人もいいところだと思うんですが
Re: (スコア:0)
>単純文字列検索ですら、BM法がアルゴリズムの教科書の定番ネタだったりするくらいだし、
単純文字列検索「だから」そういう原始的な高速化技法があるんでしょ。
不特定多数の複雑なパターンマッチにおいては、一般的な最適化技法はないと思う。
仮にあっても、その正規表現を数回しか使用しないのであれば、最適化に
かかる時間の方が、最適化によって短縮される時間より長くなって本末転倒。
正規表現部分を何万回も何十万回も使ってボトルネックになる場合は、一流の
プログラマなら正規表現なんて使わない形に書き直す。
なので不特定多数の正規表現の汎用的な最適化なんて不可能だし実装してないんじゃないだろうか。
JavaのHotSpotVMによって高度な動的最適化が日常的に利用可能になったから、
そこで行われている最適化がどれほど無茶なことか分からない初心者も増えて
しまったのかもしれない。
HotSpotVMは、もはや初心者の理解を超えてるもんね。