脳log[20241218]

2024年12月18日 (水) [AtCoder] 精進。ABC357-F「Two Sequence Queries」。20241201 で初めて実装した区間更新ができるセグメント木のテストを兼ねて挑戦していた。提出 #60878023 (AC / 2167 Byte / 3561 ms)。TLE を回避する高速化にあたっては先達の提出(#54387396、#54497837)を大いに参考にした。最も重要なアイディアは Array ではなくクラスを使うことによる自己書き換えだと思った。これによりオブジェクトの使い捨てが抑制できる。１点更新のセグメント木で凝ったマージをしようとするとすぐに TLE になるのもおそらく原因は同じで、１セグメントあたり配列に３要素も４要素も値を保持し、更新のたびに新しい配列を作成するコストが重すぎるのだろう。具体的な数字やどこで読んだかは忘れたけど、配列のサイズが４つや５つを超えると要素を Array オブジェクト(を表す内部データ)に埋め込む最適化もできなくなるだろうし。■それほど重要ではないけど TLE と AC を分ける細かい選択がいくつもある。hmmnrst さんの複数の提出の差分を調べると、mod の値はインスタンス変数に保持するより定数に保持する方がいいみたい。多重代入は１行ずつ分けるのがいいみたい。多重代入が重いのは知ってるし、仕様の変更でさらにちょっと重くなるらしいのも知ってるけど、冗長なのを嫌って自分は多用するんだよね。だけど多重代入が TLE と AC を分けているのを実際に見ると、好き嫌いではなく選択の余地はないのだなと理解してしまう。多重代入を分解するときは代入前の値を参照しているつもりで代入後の値を参照するバグを仕込みやすいので注意が必要。過去に何度も苦しめられたし、今回も、自分の AC 提出の 93 行目、Seg#apply メソッドで @ab 変数への代入順がイレギュラーなのは、最初からそうだったわけではなく、@a、@b 変数への代入のあとでは値が狂ってしまうというバグとデバッグの結果そうなっている。同じメソッドのことだけど、２つのアクセサを３回ずつ呼び出して値を参照していたのを、１回ずつに減らすためにローカル変数に受け取っている。プロファイラ(ruby-prof)で呼び出し回数と消費時間が上に上がって来ていたから対策した。自分のスクリプトの Seg クラスと Op クラスは扱いから考えて Struct にしたかったのだけど、数百 ms 以上遅くなるみたいだったのでクラスにしている。Seg#concat メソッドの呼び出しはレシーバと第一引数を同じにすることで容易に Seg#from メソッドで置き換えられるのだけど、これもパフォーマンスの劣化が無視できなかったのでスクリプトの冗長さをあえて受け入れている。Seg#from メソッドは引数で自分を完全に上書きするあたりコンストラクタと同じなのでインスタンスではなくクラスに生やしたいメソッドなのだけど、パフォーマンスのために自己書き換えが目的なのでしかたなくインスタンスメソッドにしている。ST#set メソッドと ST#get メソッドは８割が共通なのでマージできなくはないけど、わずかに遅くなるのとそうすべきなのかがわからないので分かれたままにしている。%998244353 をどこに置いてどこに置かないかも制約から計算してよくよく考えた結果のこと。実は自分のスクリプトは１秒以上も差をつけられて遅い状態が１日以上続いていたのだけど、この要不要の見積もりを誤っていたことが原因だった。パフォーマンス特性がこんなにも違うのだから、Bignum を Integer の背後に隠すのはどうかと思うんですよ。理想と現実にギャップがあるとき、現実を隠蔽することに利があるとは思わない(自動的な昇格ではなくクラスについて書いている。デバッグがしにくい)。他にも子要素の添字を計算する際の +1 を省くために内部データを 1-indexed にしたりという、針の穴を通すような細かな積み重ね抜きでは Ruby で AC を取ることができない。正直言ってコンテスト本番ではこの手の問題(遅延セグメント木、N>300 のワーシャルフロイド法、N=5000 の２乗の DP など)はさっさと投げ捨てて他の問題を解いた方が良い。なお、できる人は Ruby を投げ捨てるもよう。■記事を閲覧履歴から発掘した。「Ruby 1.9 では RVALUE に「embed」という考え方が導入され、文字列や配列などデータのうち、サイズの小さいモノは別途 malloc するのではなく RVALUE の中に埋め込んでしまうことで、 malloc & free のオーバーヘッドを削減でき、またキャッシュの局所性を高めることができます。」「ちなみに Array なら 3 つまで embed で扱います。」(Ruby は String をメモリ上でどのように扱っているのか？ | IIJ Engineers Blog)■最初期の提出を見てみると、出力用の第３引数を渡すことで配列を使っていてもオブジェクトの使い捨ては抑制できていたみたい。それでひどい TLE なのだから、クラス化による最大のメリットは [] メソッドを使わないインスタンス変数へのアクセスなのかもね。