脳log[20220218]

2022年02月18日 (金) 「3000ミリ秒近くかかっている。 なお Perl で同じコードを実行してみたところ、5ミリ秒で終わった。 Ruby では 22 秒（ミリ秒ではない！）かかった。 正規表現の実装が、ぜんぜん違いそうである。」 / Twitter」■へー。たしかに Ruby だと 30 秒くらいかかる。よくある * や + を入れ子にしてバックトラックが～というのではなく、単純にマッチ開始位置とマッチ失敗までのスキャンとがともに入力に比例する N^2 時間かかってる雰囲気。マッチテスト開始位置をずらしたときに「おや、ここはもう通った道だ」と気が付ければいいんだろうか。文字列内の位置とエンジンの内部状態が一致するならすでに出ている結論を流用できる、的な。テキトー言ってるけども。シチュエーションを限定しないとどんだけコストがかかるか想像できないけども。■「正規表現の脆弱性 (ReDoS) を JavaScript で学ぶ」