脳log[20221125]

2022年11月25日 (金) 「■DFSを非再帰で書くとTLEになる件 再帰になっているものを非再帰に変えると普通は関数呼び出しのオーバーヘッドがなくなるので処理は速くなるはずだ。ところが、DFSを非再帰に書き換えるとTLEするようになったという心霊現象みたいな話はわりとある。添付画像のような記述だ。 つづく https://t.co/KU7V0jQfni」■非再帰で迂闊な DFS を書くと TLE になることがあるという一連のツイート。書いてある通りだと思うのだけど、結論が投げっぱなしなので補足的なことを書きたい。再帰関数で書いた DFS を非再帰版に書き換えるというのは、関数呼び出しによってスタック上に暗黙的に確保されていたローカル変数および仮引数のスタック(積み重ね)を、配列などを使い自分で明示的に保存、復元する処理を書いてループを回すということ。ループの１回がだいたい再帰関数の呼び出し１回にあたる。TLE になるのは非再帰バージョンに書き換えたときにパラメータが不足していて状態の復元が不十分だから。不十分でも WA にはならないかもしれないけど、状態と状態のあいだが疎らなために手戻りが発生して TLE になることがある(というのが一連のツイートの内容)。このツイートで再帰関数を呼び出す瞬間と戻ってくる瞬間をよく意識してほしい。隣接頂点リストを走査するループの途中で再帰に突入し、ループの途中に戻って来ている。これを非再帰で書き直すのだから、隣接頂点リストのどこまでが処理済みかという情報まで(明示的な)スタックに保存し、状態を復元しなければ等価な書き換えとは言えない。提出 #36771698 (Ruby / 419 ms / 非再帰 / 頂点番号と隣接頂点リストの添字を記録してループ)。提出 #36771423 (Ruby / 409 ms / 非再帰 / 頂点番号だけを記録しているが隣接頂点リストを破壊的に使用して手戻りを防いでいる)。ちなみに迂闊な DFS をあえて再帰で書くとこうなる>提出 #36774583 (TLE)。隣接頂点リストを繰り返し走査する 14 行目を見れば O(N^2) が納得できると思う。再帰↔非再帰を行き来するときに知らずこのような違いが生じているので TLE でなかったものが TLE になったりする。それゆえに「結論 : DFSを非再帰で書くのはわりと難しい」。でも心霊現象ではないと思うの。■再帰→非再帰の書き換えを初めて意識したのはこのとき>脳log[20050929p01] やねう企画2005年度入社試験。見覚えのあるお名前。■■■@2022-12-21 八百倍役に立つ記事があるよ。「それ、非再帰で書けます - Qiita」