【PHP】下らねぇ質問はここに書き込みやがれ 15

【PHP】下らねぇ質問はここに書き込みやがれ 15 (92ﾚｽ)
上下前次1-新
通常表示 512ﾊﾞｲﾄ分割ﾚｽ栞
抽出解除必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞あぼーん

56: デフォルトの名無しさん (ﾜｯﾁｮｲ 2770-RTB+) [sage] 2025/05/08(木) 21:46:41.16 ID:MhxTwPG60

>>29
解決したのはすごいよ。
普通はたどり着けないからね。ラッキーでど命中したというのはあるが、それにしても、だ。

> 速度面での恩恵が大きい (https://agree.5ch.net/test/read.cgi/mango/1715675838/336)
正規表現にもよるが、'/....ABC/'とか書きたければそうね。
(俺の理解が正しければ)O(n^2)が(*FAIL)でO(1)になるのだから爆速だ。
ただ現在は、こういう「頭が決まらない(＝頭が何でもマッチする)正規表現はバックトラックが激しく発生するので駄目、
後読み/(?<=/等使って頑張れ、となってるが、これらについて、つまり正規表現エンジンの進化の方向としては、

α. バックトラックを正しく理解した上で、制御しきる。（＝ホワイトボックス化)
　この為に(*FAIL)や++等追加する。
β. 単純に速い正規表現エンジンとする。バックトラックの理解はしなくていい。（＝ブラックボックス化)
　ただし内部的な最適化を限界まで行うので、動作の曖昧さが残る。結果、
> 　/^(?>s|ss)$/ does not match "ss".  (https://github.com/kkos/oniguruma/issues/290#issuecomment-1825555154)
　等はバージョンによって動作が異なるので、現実的に使えない。
　つまり、頭から検索する前提でバックトラック制御等を行っている正規表現は動作の保証が出来ない。(＝仕様として追加できない)
　言い換えれば、現在onigurumaで導入してる ?> 等は永久に使えない。

の2つの方向があって、見る限り、onigurumaは明らかにα方向だ。
ただ俺は、βが正解だと思ってるんだな。αはMatzの言う「実装が仕様にはみ出している」から。
つまり、今回も、あるいはバックトラックの理解/制御が必要なのも、「遅い」からであって、
十分速ければこの必要もないし、ユーザーもバックトラックなんて理解したいわけではなく、正規表現を使いたいだけだから、と考える。
富豪プログラミング万歳！！！ってところだ。

http://mevius.5ch.net/test/read.cgi/tech/1730202739/56

63: デフォルトの名無しさん (ﾜｯﾁｮｲ 2770-RTB+) [sage] 2025/05/08(木) 21:51:33.26 ID:MhxTwPG60

さて読んでて思ったのだが、これ、仕様が矛盾してて、現実的に実装できない可能性も有るのでは？
これは当人も気づいてて言及してるが、実際に矛盾してるかどうかまでは分からないようだ。
> JS also ensures that /\w/iu is the inverse of /\W/iu. (https://github.com/kkos/oniguruma/issues/351#issuecomment-2818389363)
俺も考えてみたが、よく分からん。
単純には、[\w]!==[^\W]でどうにも実装できないケースがあれば、
どのみちいつか breaking change するしか無いので、後腐れなく出来るのだが。

ところで同様の問題は、多分「濁点」にもある。
(この板がunicode許可してるかは知らんので以下見た目意味不明になるかもだが)
Unicodeには、結合文字用濁点(0x3099)があるので、「あ゙」とかも出来る。(表示系が対応してれば前の字と重ねて表示され、あに濁点がつく)
よって、「が(0x304c)」と「が(0x304b,0x3099)」は見た目区別がつかない。
(0x304b,0x3099を表示するのに、通常は、単純にビットマップを重ねるわけではなく、0x304cのフォントが使用されるから)
おそらくこの辺もonigurumaは対策されてるのではないかと思う。
正直、これはヒットしてくれたほうが助かるのは事実。
というかね、ブラウザ(Ctrl+F)ではヒットするが、JSではヒットしないので、
見た目表示されてるのにJSから検索すると存在せず、あれ？ってなったことがあった。

だから見た目、現行の動作は、「仕様的に正しい」。
これは本当に重要で、先日も言ったが、仕様を追加するのはいつでも楽勝だが、削除するのは基本的に無理なので、
おかしな仕様を追加した時点で将来的に詰むのが確約されるから、これは全力で回避しなければならない。
現行の動作は、確かに正しい。
問題は、その場合に異常に遅くなるケースがある、ということであって、
本来は、仕様変更ではなく、速度対策『だけ』で済ませるべき状況であり、実際に高速化すれば何も問題なくなるはず。
とはいえ高速化はもう出来ません、ということなのだろうが、果たしてそうなのか？とは思う。

http://mevius.5ch.net/test/read.cgi/tech/1730202739/63

64: デフォルトの名無しさん (ﾜｯﾁｮｲ 2770-RTB+) [sage] 2025/05/08(木) 21:51:59.95 ID:MhxTwPG60

例えば典型的な糞ッタレ正規表現、
> a.*b.*c.*d.*e   // --- (a)
についてだが、
> a.*+b.*+c.*+d.*+e   // --- (b)
は確かに一つの解だろう。しかしこれは、最速ではない。
人間がやるときを考えれば分かるが、

$len = strlen($str);   // ---(c)
$e = strrpos($str,'e'); // 最後のe
$d = strrpos($str,'d',$e-$len); // eより前の最後のd
$c = strrpos($str,'c',$d-$len); // dより前の最後のc
$b = strrpos($str,'b',$c-$len); // cより前の最後のb
$a = strpos($str,'a',$b-$len); // 最初のa
if ($a<$b) // check

と後ろから検索するのが速く、正規表現にすると

/(?<=(a.*))(?<=b.*?)(?<=c.*?)(?<=d.*?)(?<=e(.*?))$/ --- (d)

となる。が、まあ、(d)だと得られる結果が微妙に異なってしまうので後処理必要だが、(というより同じ結果を得られる正規表現を書けなかったorz)
内部的に自動的にこの方向で高速化してくれ、となる。
単純には、greedyに対してnon-greedyで右から検索すれば多分最速になる。
この辺、バックトラックの指定を事細かく出来る＝走査順が仕様として規定されてしまう＝左から右に走査、となってしまってるのが問題なので、
「任意の最適化の許可」フラグで、右から左に走査することも許可し、(勿論それ以外にもやっていい)
結果的にクソ速いがバックトラック制御は出来ませんよ、が正しい気がする。
(フラグ指定した場合、どう走査されるかはエンジン任せで、
結果的にバックトラック制御を指定してもどう動くか予想できず、実質使えなくなる。
が、問題は速度が遅いことであり、バックトラック制御をするのが目的ではないのでこれでいいはず)

http://mevius.5ch.net/test/read.cgi/tech/1730202739/64

上下前次1-新書関写板覧索設栞歴

ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 1.790s*