Fixstars高速化コンテスト2024準優勝解法

Transcript

1. Fixstars 高速化コンテスト 2024 準優勝の解法紹介 eijirou

2. 問題 https://fixstars-contest.com/contests/cpu2024/problem • 長さが 𝑁 の配列 𝑎, 𝑏 が与えられる •

   各要素（宝石）は 𝐾 未満の非負整数 • 𝑎 をいくつか巡回シフトし 𝑏 と一致する要素を最大化せよ • 一致する要素の最大値とそのときのシフト数（1つでよい）を求める コンテストサイト https://fixstars-contest.com/contests/cpu2024/problem 2

3. 問題の言い換え • 長さが 𝑁 の配列 𝑎, 𝑏 が与えられる • 各要素（宝石）は

   𝐾 未満の非負整数 • 𝑎 をいくつか巡回シフトし 𝑏 と一致する要素を最大化せよ • 一致する要素の最大値とそのときのシフト数（1つでよい）を求める • 以下の値を求めよ max 𝑘∈[𝑁] # 𝑎𝑖 = 𝑏𝑗 𝑖 + 𝑗 mod 𝑁 = 𝑘 3 𝑎 を逆順にして問題を言い換える

4. 方針 1. 要素（宝石）ごとに各シフトへの寄与を求める • 𝑔𝑎,𝑥 ≔ 𝑖 ∣ 𝑎𝑖 =

   𝑥 とすると、要素 𝑥 のシフト 𝑘 への寄与は # 𝑖, 𝑗 𝑖 ∈ 𝑔𝑎,𝑥 , 𝑗 ∈ 𝑔𝑏,𝑥 , 𝑖 + 𝑗 mod 𝑁 = 𝑘 2. 各シフトへの寄与を加算し、最大値を求める 2種類の解法を紹介する 4

5. インクリメント解法 • 𝑔𝑎,𝑥 ≔ 𝑖 ∣ 𝑎𝑖 = 𝑥 と

   𝑔𝑏,𝑥 ≔ 𝑖 𝑏𝑖 = 𝑥 を求め、二重ループを 回す • 時間計算量は要素1つにつき 𝑂 𝑔𝑎,𝑥 ⋅ 𝑔𝑏,𝑥 • 各要素の出現回数が等しければ 𝑂 𝑁2 𝐾2 、全体で 𝑂 𝑁2 𝐾 5

6. インクリメント解法: キャッシュ効率 • キャッシュヒット率が悪い • 書き込み先の配列（ret）がL1キャッシュに収まらない 書き込み先の配列をL1キャッシュサイズで切る 6 このままだと遅いが、 尺取り法を使うと

   𝑗 ∈ 𝑙 − 𝑖, 𝑟 − 𝑖 を効率よく列挙できる

7. インクリメント解法: 並列化 • 書き込み先を決めるループを並列化する • 書き込み先のメモリをスレッド毎に独立にできる • 実際には配列の長さを 𝑁 にした

   7 ここをスレッド並列化

8. インクリメント解法: 命令数の削減 • ga[x] のループをunrollすると gb[x] の読み込み回数が減る • コンテスト後に @e869120

   さん に教えていただきました 279ms 253ms 8

9. NTT解法 畳み込みに変形し、NTTを使う 𝑓𝑎,𝑝,𝑖 ≔ ቊ 0 (𝑎𝑖 ≠ 𝑝) 1

   (𝑎𝑖 = 𝑝) • 𝑓𝑎,𝑝 (𝑥) ≔ 𝑓𝑎,𝑝,0 𝑥0 + 𝑓𝑎,𝑝,1 𝑥1 + ⋯ + 𝑓𝑎,𝑝,𝑛 −1 𝑥𝑛−1 • σ𝑝=0 𝐾−1 𝑓𝑎,𝑝 𝑥 ⋅ 𝑓𝑏,𝑝 𝑥 を求めればよい • 畳み込みを 𝑂 𝑁 log 𝑁 で計算できるため、全体で 𝑂 𝐾𝑁 log 𝑁 9

10. NTT解法: Nyaan’s Library を使う https://nyaannyaan.github.io/library/ntt/ntt-avx2.hpp • Nyaan’s Library で行われていた高速化 •

    非再帰 • in-place • 4基底 • モンゴメリ乗算による除算の除去 • SIMD • data alignment • × 1 の省略, etc. Nyaan’s Library ntt/ntt-avx2 https://nyaannyaan.github.io/library/ntt/ntt-avx2.hpp 10

11. NTT解法: INTTをまとめる INTTは1回でよい ෍ 𝑝=0 𝐾−1 𝑓𝑎,𝑝 𝑥 ⋅ 𝑓𝑏,𝑝

    𝑥 = ෍ 𝑝=0 𝐾−1 intt ntt 𝑓𝑎,𝑝 𝑥 ⋅ ntt 𝑓𝑏,𝑝 𝑥 = intt ෍ 𝑝=0 𝐾−1 ntt 𝑓𝑎,𝑝 𝑥 ⋅ ntt 𝑓𝑏,𝑝 𝑥 11 多項式の積 要素ごとの積 要素ごとの積 mod 上の加算

12. NTT解法: INTTをまとめる intt 𝐴 + intt 𝐵 = intt(𝐴 +

    𝐵) の正当性 12 𝐴 𝑥 = σ𝐴𝑖 𝑥𝑖 𝐵 𝑥 = σ𝐵𝑖 𝑥𝑖 𝐴 𝑟0 , ⋯ , 𝐴 𝑟𝑁−1 𝐵 𝑟0 , ⋯ , 𝐵 𝑟𝑁−1 𝐶 𝑟0 , ⋯ , 𝐶 𝑟𝑁−1 = 𝐴 𝑟0 𝐵 𝑟0 , ⋯ , 𝐴 𝑟𝑁−1 𝐵 𝑟𝑁−1 𝐶 𝑥 = 𝐴 𝑥 ⋅ 𝐵(𝑥) NTT INTT FFT/NTT で畳み込みを計算する流れ

13. NTT解法: INTTをまとめる intt 𝐴 + intt 𝐵 = intt(𝐴 +

    𝐵) の正当性 13 𝐴 𝑥 = σ𝐴𝑖 𝑥𝑖 𝐵 𝑥 = σ𝐵𝑖 𝑥𝑖 𝐴 𝑟0 , ⋯ , 𝐴 𝑟𝑁−1 𝐵 𝑟0 , ⋯ , 𝐵 𝑟𝑁−1 𝐶 𝑟0 , ⋯ , 𝐶 𝑟𝑁−1 = 𝐴 𝑟0 + 𝐵 𝑟0 , ⋯ , 𝐴 𝑟𝑁−1 + 𝐵 𝑟𝑁−1 𝐶 𝑥 = 𝐴 𝑥 + 𝐵(𝑥) NTT INTT 加算でも成り立つ 離散フーリエ変換は行列積なので 線形性が成り立つという説明も可能

14. NTT解法: その他の高速化 • 最初は要素が0と1しかないため、積を省略できる • 場合によっては2周目も積を省略する • できるだけキャッシュサイズで切る • 速くならないかも

    14 1 2 3 4 7 10 13 5 6 8 9 11 12 14 15 キャッシュサイズ 番号は計算順序 配列のインデックス

15. まとめ • インクリメント解法 • 各要素の出現回数が等しければ 𝑂 𝑁2 𝐾 • 𝐾

    が大きいときに使う • NTT解法 • 𝑂(𝐾𝑁 log 𝑁) • 𝐾 が小さいときに使う • 並列化 • 定数倍高速化 • 実行命令数の削減 • キャッシュヒット率の改善 15