最終更新: 2022-02-11T22:02+0900
先日解いていた「JOIG 2021/2022 本選競技課題」(テストケースのダウンロードができる) の F 問題へのこの提出に関して>20220129p01.05。
Hash#shift を意味がある限り繰り返したあとで Hash#clear を呼ぶようにしている(25 行目)。shift は破壊的なメソッドだから shift を十分に呼び出した後の Hash は空になっているはずで、clear を呼ぶ意味はなさそうに思える。それでも呼ぶようにしているのは、これがないとテストケースの in/05-01.txt に限ってスクリプトの応答がなくなって TLE になると思ったから。少なくともローカル Windows 環境では Ruby-2.7 と Ruby-2.5 で止まる。Ruby-1.9 は平気。他のテストケースでは止まらないけど、問題のケースでは必ず止まる。止まるタイミングはバラバラだけど、いずれも Hash への代入で止まっているようだった。
再現スクリプトはこんな感じ(これを見つけたから日記に書いている)。他所で再現するかは、どうでしょうね。
Many = 100 # 10 回では少ない。テキトーに大きく。
Some = 100 # ウチでは 30 回目までは到達しない。
# ウチの Ruby-2.5: ruby 2.5.5p157 (2019-03-15 revision 67260) [x64-mingw32]
# ウチの Ruby-2.7: ruby 2.7.1p83 (2020-03-31 revision a0c7c23c9c) [x64-mingw32]
Some.times{|some|
warn "#{some} begin"
hash = {}
Many.times{
some.times{|j|
k = Random.rand 0..Many
hash[k] = 1 # maybe hang
}
0 while hash.shift
}
warn "#{some} end"
}
warn :exit
Ruby-2.5 と Ruby-2.7 では "N begin" (N は 20 前後) を表示して止まる。2.5 より 2.7 の方が早く止まるという傾向はあるけど、具体的な回数にはバラツキがある。それはまあ乱数を使ってるからだと思うけど、ハッシュのキーを k に代えて j にしたり、シャッフルした順列にしたりすると止まらなくなるので(正常動作)、乱数は外せない。
こういう Issue「Bug #17779: 特定の順序でHashのkeyを削除した場合に Hash#first が遅くなる - Ruby master - Ruby Issue Tracking System」を思い出したけど、全然関係はなさそう？ 全然わからない。
AtCoder のコードテストを使わせてもらったら(目的外失礼)、こういう結果。AtCoder の Ruby も今のバージョンは 2.7。
| 終了コード | 9 |
| 実行時間 | 10501 ms |
| メモリ | 9112 KB |
標準エラー出力は 30 begin で途切れている。完走しても 10 秒もかかるはずないから、ハングして実行を打ち切られたのだと思う。コードテストとジャッジサーバーが同じだとして、ジャッジサーバーのスペックはこう>Linux ip-***-***-***-*** 4.15.0-1041-aws #43-Ubuntu SMP Thu Jun 6 13:39:11 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux*⁑。
Ruby-3.1 が「ウチの Ruby」に今日加わりました。大体ループの 20 から 30 回目で止まるんだけど、弾みで 2 回だけ完走したりもした。
パラメータが２つもあると面倒なので。
改訂するにあたって予想外に止まらなくなったりした(正常動作)のを通して、たぶん直接的な原因もわかった。
# ウチではだいたい 20 から 30 回で "empty?: true" を最後にして止まる。
# ウチの Ruby-2.5: ruby 2.5.5p157 (2019-03-15 revision 67260) [x64-mingw32]
# ウチの Ruby-2.7: ruby 2.7.1p83 (2020-03-31 revision a0c7c23c9c) [x64-mingw32]
# ウチの Ruby-3.1: ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) [x64-mingw-ucrt]
H = {}
100.times{|n|
while H.size < n
k = Random.rand 0..1<<30
H[k] = 1 # たぶんここで止まる。
end
warn "size: #{H.size} before shifting."
H.shift until H.empty?
raise if H.shift # no exception. だけど Hash が空になった後の shift が後でハングをひき起こす？
warn "empty?: #{H.empty?}"
}
warn :exit
Hash を空にする方法として 0 while H.shift を選ぶとその後の Hash#[]= でハングするが、Hash を空にする方法として H.shift until H.empty? を選ぶとハングしなかった。条件を揃えていくと、Hash#empty? が作用してハングを回避しているのではなく、Hash が空になったあとの Hash#shift がハングをひき起こしているようだった。ちなみに Hash#clear にハングを回避する効果があるらしいのは、JOIG の問題への提出で確認済み(とはもう書いた)。
投稿して次に見たときにはすべてが終わっていた。早いぜ。
こういう仕組みだったようです。
メモ：entries_bound は使用中のビン（DELETEDになったビンを含む）の数に（ほぼ）対応していて、これをみてテーブルをリビルドしている（rebuild_table_if_necessary）。空のハッシュに対する Hash#shift はなぜか entries_bound を 0 にしているので、リビルドすべきタイミングを逃し、ビンがすべて使用中になった状態で空きビンを探そうとするので無限ループに陥っていた（find_table_bin_ind）。